我正在处理一个非常大的数据集。本质上，我将处理数百万条记录并将值存储到数据集中。
每次存储值时，我必须首先检查以确保该值尚未存在于数据结构中。如果该值在数据结构中，我必须更新(或删除/添加)记录以更新计数。
数据集中有重复，我不想使用糟糕的数据结构并获得 O(n) 的速度，因为我希望能够运行过夜并在早上进入就完成了!
有什么建议吗？
最佳答案
正如其他人所说，哈希表可能是正确的答案，但是哈希表的空间效率不是很高，所以如果你达到了这样的地步:可能会耗尽您的内存，您应该考虑一个排序的键数组和一个并行排序的值数组。基本上，如果您可以预先访问整个键列表，请创建一个数组并对其进行排序。然后创建一个并行的值数组。每次需要存储某些内容时，只需执行二分搜索(O(log N))即可找到键数组中的索引，然后更新值数组中相应的索引。这将比哈希表速度效率低，但几乎保证没有空间开销。
关于data-structures - 效率: What data structure to use. ..？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2284787/