c++ - 当您只关心速度时如何存储二进制数据？

Question

我在 D 维中有 N 个点，假设 N 是 100 万，D 是 100。我所有的点都有二进制坐标，即 {0, 1}^D，我只对速度感兴趣。

目前我的实现使用 std::vector<int> .我想知道是否可以通过更改我的 data-structure 来加快执行速度.我只进行插入和搜索(我不更改位)。

我发现的所有相关问题都提到了 std::vector<char> , std::vector<bool>和 std::bitset , 但所有人都提到了使用这种结构应该获得的空间优势。

当速度是主要关注点时，对于 C++ 中的二进制数据，什么是合适的数据结构？

---

我打算用二进制数据填充我的数据结构，然后进行大量连续搜索(我的意思是我并不真正关心一个点的第 i 个坐标，如果我正在访问一个点我会连续访问其所有坐标)。我将计算彼此之间的汉明距离。

Answer 1

如果值是独立、均匀分布的，并且您想要找到两个独立、随机选择的点之间的汉明距离，最有效的布局是位压缩数组。

理想情况下，这个打包数组将被分块为您的 popcnt 指令工作的最大块大小:64 位。汉明距离是 popcnt(x_blocks[i] ^ y_blocks[i]) 的总和。在具有高效未对齐访问的处理器上，未对齐读取的字节对齐可能是最有效的。在未对齐读取会导致损失的处理器上，应该考虑对齐行的内存开销是否值得更快的逻辑。