c++ - 在 C++ 中存储和访问 N 维位数组中单个位的最快方法是什么？

Question

我有一个代码，我需要在其中以随机方式从一个大的位数组(总共几兆字节)读取和写入单个数据位。类似于用N维数组玩战舰的东西。

我怀疑紧凑型数组会更快，因为它会将一些数组保留在缓存中。另一方面，我知道访问作为数组对象可用的数组元素的时间等效于通过编译时指针值进行访问，而在 std::vector 的典型实现中，元素访问时间与元素访问相同通过运行时指针值(较慢)。我不知道位集和位域如何适应所有这些。

我不需要此代码具有可移植性，只需要非常快 (x86)。

Answer 1

没有单一的答案，因为它取决于处理器架构(和编译器)。

也就是说，位数组非常快。您只需将其创建为 int 的数组即可s，然后通过选择正确的 int 来访问这些位并提取正确的位。只要你的int，它就会紧凑，快速具有两位数的幂(32、64 等)——否则您可能必须在紧凑性和速度之间进行权衡(例如，在 36 位处理器上，您可以选择速度并且每个 int 仅使用 32 位)。

紧凑情况下的代码变为(p[idx / BITS_PER_INT] >> (idx % BITS_PER_INT)) .对于 BITS_PER_INT = 2 << SHIFT 的快速情况这与 (p[idx >> SHIFT] >> (idx & (BITS_PER_INT-1))) & 1 相同.

如果您需要更多地控制数据存储，您可以自定义布局以满足您的要求(尽管如果可移植性没有问题，这也可能不是问题)。

同样，因为它也是特定于实现的，所以我应该提一下最快的 std::vector<bool>虽然不能保证尽可能快或尽可能紧凑，但很可能它至少是其中之一，并且如果需要的话可能是它们之间的一个很好的权衡。