我在 D 维中有 N 个点,假设 N 是 100 万,D 是 100。我所有的点都有二进制坐标,即 {0, 1}^D,我只对速度感兴趣。
目前我的实现使用 std::vector<int>
.我想知道是否可以通过更改我的 data-structure 来加快执行速度.我只进行插入和搜索(我不更改位)。
我发现的所有相关问题都提到了 std::vector<char>
, std::vector<bool>
和 std::bitset
, 但所有人都提到了使用这种结构应该获得的空间优势。
当速度是主要关注点时,对于 C++ 中的二进制数据,什么是合适的数据结构?
我打算用二进制数据填充我的数据结构,然后进行大量连续搜索(我的意思是我并不真正关心一个点的第 i 个坐标,如果我正在访问一个点我会连续访问其所有坐标)。我将计算彼此之间的汉明距离。
最佳答案
如果值是独立、均匀分布的,并且您想要找到两个独立、随机选择的点之间的汉明距离,最有效的布局是位压缩数组。
理想情况下,这个打包数组将被分块为您的 popcnt
指令工作的最大块大小:64 位。汉明距离是 popcnt(x_blocks[i] ^ y_blocks[i])
的总和。在具有高效未对齐访问的处理器上,未对齐读取的字节对齐可能是最有效的。在未对齐读取会导致损失的处理器上,应该考虑对齐行的内存开销是否值得更快的逻辑。
关于c++ - 当您只关心速度时如何存储二进制数据?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40773463/