Kev*_*vin 1 c++ algorithm hash data-structures
我有200像素x 200像素的2D光栅我想将其细分为每个10x10像素的400"桶".
然后我有一个点(大约200k)的列表,我想在上述结构中映射.因此,如果该点落入10x10区域,请将其添加到存储桶中.
现在,在我看来哈希表可以做得很好.我想知道这是否可以使用STL？
我尝试使用stl :: unordered_map并指定桶的数量,但这不起作用,它'忽略'该请求.(因为太多的项目被映射到我认为的相同区域,但在我的情况下,这不是问题,相反,这就是整个问题).
用STL有没有办法做到这一点？
我认为你混淆了两个术语.哈希表意义上存在"桶",这是用于均匀分布元素的一些内部实现细节,因此查找往往不会扫描太多无用的元素.在空间意义上还存在"桶",它们是空间到区域的分区,因此元素恰好属于一个桶.通常情况下,您可以自己控制空间分段系统(您可以选择分割所有内容的位置),但哈希表不会让您非常精确地控制存储区.您可能会选择初始大小,但如果哈希表认为增加该大小以提高性能是个好主意,那么它几乎肯定会这样做.如果没有,查找时间会更糟.
如果你想将空间分成网格,然后将点分配到网格中,最好的方法是创建一个二维数组(使用原始数组或使用一些网格线性化)std::unordered_maps,每个数组都只保存在一个特定的空间区域中的点.这样,如果你想查找一个元素,你会转到地图上的那个存储点,然后让地图查找该值,然后查询它自己的内部存储系统以找到你的点.想.这意味着如果你想分割点以便你可以对空间区域进行有趣的查询,那么这些点存储在专门用于这些区域的存储桶中,但是在这些存储桶中它们存储在哈希表中以进行制作查找这些点需要更少的时间.
或者,您可能需要考虑使用四叉树或kd树等空间数据结构,它可以有效地存储元素,并让您有效地查询空间桶中的每个点.
希望这可以帮助!
| 归档时间： |
|
| 查看次数： |
391 次 |
| 最近记录： |