c++ - 需要在字符串和整数之间进行快速映射

Question

我有一个 string 和 unsigned 的映射，我在其中存储一个词到它的以下形式的频率:

map<string,unsigned> mapWordFrequency; //contains 1 billion such mappings

然后我读取了一个巨大的文件 (100GB)，并只保留文件中频率大于 1000 的单词。我使用以下命令检查文件中单词的频率:mapWordFrequency[word]>1000。然而，事实证明我的 mapWordFrequency 有 10 亿个映射，而且我的文件很大，因此尝试检查文件中每个单词的 mapWordFrequency[word]>1000 非常慢，需要 2 天以上的时间。有人可以建议我如何提高上述代码的效率。

map 不适合我的 RAM，交换会消耗大量时间。

删除所有频率 < 1000 的单词是否有助于使用 map 的删除功能？

Answer 1

我建议您使用 unordered_map 而不是 map。正如评论中已经讨论的那样，前者将为您提供 O(1) 的插入/检索时间，而不是 map< 中的 O(logn)/。

如您所说，内存交换非常耗时。那么如何逐步解决这个问题呢？将最大数据和 unordered_map 加载到内存中，对其进行哈希处理，然后继续。在一个 pass 之后，你应该有很多 unordered_maps，你可以在后续的 pass 中开始组合它们。

您可以通过以分布式方式执行此操作来提高速度。在不同的计算机上处​​理数据片段，然后组合数据(将以无序映射的形式出现。但是，我以前没有分布式计算方面的经验，因此无法提供更多帮助。

另外，如果实现这样的东西太麻烦，我建议你使用外部归并排序。这是一种通过对较小的 block 进行排序并将它们组合来对太大而无法放入内存的文件进行排序的方法。我建议这样做的原因是外部合并排序是一种非常常见的技术，您可能会发现已经实现的解决方案可以满足您的需要。尽管排序的时间复杂度高于您使用 map 的想法，但与 map 相比，它会减少交换的开销。正如评论中指出的那样，linux 中的 sort 实现了外部归并排序。