我有一个vector<unsigned>大小(90,000 * 9,000).我需要多次查找此向量中是否存在元素？
为此,我使用排序的形式存储了矢量std::sort(),然后使用矢量查找矢量中的元素std::binary_search().但是在使用perf我的分析时,我发现查找元素vector<unsigned>是最慢的操作.
有人建议一些data-structure中C/C++,我可以用它来高效地查找元素的矢量(90,000 * 9,000)元素.
我只执行一次插入(批量插入).剩下的时间我只执行查找,所以这里的主要开销是因为查找.
MSa*_*ers 10
你有40亿个可能的值(假设32位unsigned)中有8.1亿个值.这是总范围的1/5,使用3.2 GB.这意味着你实际上有更好的std::vector<bool>40亿比特.这使您可以在更小的空间(0.5 GB)内进行O(1)查找.
(理论上,unsigned可能是16位.unsigned long是至少 32位,std::uint32_t可能是你想要什么)
| 归档时间： |
|
| 查看次数： |
414 次 |
| 最近记录： |