两个大型稀疏向量上的按位运算符没有循环？
Bitwise operator on two large sparse vectors without looping?
我有三个大的任意稀疏布尔向量，它们的大小都相同 - 比如：pool1、pool2、intersection_of_other_pools。我有兴趣执行按位运算符。如果我能做到，那就太好了：intersection_of_other_pools |= pool1 | pool2，但这似乎不是一个选择 - 据我所知。
由于所有这些向量的大小都非常大，而 pool1 和 pool2 非常稀疏，我会对对这些向量执行按位运算的方法感兴趣 没有循环。我知道 std::vector<bool> 的底层实现只是一个位数组，这让我相信可以在不循环的情况下做到这一点。
我愿意接受以速度为名的奇怪的按位破解解决方案。
当然，如果最快（或唯一）的方法就是循环，那么我也很乐意接受它作为答案。
我已经检查过 valarray 作为矢量的潜在替代品，但我无法判断它是在循环还是在进行一些神奇的按位运算。但理想情况下，我不想更改现有代码库。
实现为 std::vector<uint64_t>，你的 cpu 可能会很快地对这些进行按位 "or"。它们将是 memory-aligned，因此缓存友好。
循环并没有你想象的那么糟糕，因为在不同的数据结构上无论如何都会有一个隐藏的隐式循环。
如果它非常稀疏（<< 1000 个），那么只需将 "set" 位的索引存储在一个（排序的）向量中并使用 std::set_intersection 进行匹配
不要使用 std::vector<bool> 或类似的稀疏数组。
一个真正的稀疏数组应该能够跳过大的部分。
将您的数据编码为块 headers，它说明一个区域的长度（以字节为单位）。使用长度中的所有 1 递归地表示 "the length of the length field is twice as long and follows"。
因此 0xFF0100 表示后面有一个长度为 512 的块。 （你可以通过不允许 0 和 1-254 来做得更好，但这是舍入误差）。
"all 0s" 的交替块与混合 1 和 0 的块。
不要直接读取块headers；使用 memcpy 对齐存储。
一旦你有了这个，你的 | 或 & 操作就更像是一个缝合而不是按位操作。只有在两者都有 non-zero 块的极少数情况下，您才真正进行按位工作。
在完成 & 之后，您可能想检查是否有任何非 0 区域实际上都是 0。
这假定一个极度稀疏的位域。像，每几万个中设置一个位就是一个典型的例子。如果稀疏你的意思是“十分之一”，那么只需使用 uint64_t 或其他东西的矢量。
我有三个大的任意稀疏布尔向量，它们的大小都相同 - 比如：pool1、pool2、intersection_of_other_pools。我有兴趣执行按位运算符。如果我能做到，那就太好了：intersection_of_other_pools |= pool1 | pool2，但这似乎不是一个选择 - 据我所知。
由于所有这些向量的大小都非常大，而 pool1 和 pool2 非常稀疏，我会对对这些向量执行按位运算的方法感兴趣 没有循环。我知道 std::vector<bool> 的底层实现只是一个位数组，这让我相信可以在不循环的情况下做到这一点。
我愿意接受以速度为名的奇怪的按位破解解决方案。
当然，如果最快（或唯一）的方法就是循环，那么我也很乐意接受它作为答案。
我已经检查过 valarray 作为矢量的潜在替代品，但我无法判断它是在循环还是在进行一些神奇的按位运算。但理想情况下，我不想更改现有代码库。
实现为 std::vector<uint64_t>，你的 cpu 可能会很快地对这些进行按位 "or"。它们将是 memory-aligned，因此缓存友好。
循环并没有你想象的那么糟糕，因为在不同的数据结构上无论如何都会有一个隐藏的隐式循环。
如果它非常稀疏（<< 1000 个），那么只需将 "set" 位的索引存储在一个（排序的）向量中并使用 std::set_intersection 进行匹配
不要使用 std::vector<bool> 或类似的稀疏数组。
一个真正的稀疏数组应该能够跳过大的部分。
将您的数据编码为块 headers，它说明一个区域的长度（以字节为单位）。使用长度中的所有 1 递归地表示 "the length of the length field is twice as long and follows"。
因此 0xFF0100 表示后面有一个长度为 512 的块。 （你可以通过不允许 0 和 1-254 来做得更好，但这是舍入误差）。
"all 0s" 的交替块与混合 1 和 0 的块。
不要直接读取块headers；使用 memcpy 对齐存储。
一旦你有了这个，你的 | 或 & 操作就更像是一个缝合而不是按位操作。只有在两者都有 non-zero 块的极少数情况下，您才真正进行按位工作。
在完成 & 之后，您可能想检查是否有任何非 0 区域实际上都是 0。
这假定一个极度稀疏的位域。像，每几万个中设置一个位就是一个典型的例子。如果稀疏你的意思是“十分之一”，那么只需使用 uint64_t 或其他东西的矢量。