需要字符串和整数之间的快速映射

Question

我有一个字符串和无符号的映射,其中我将一个单词存储到以下形式的频率:

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

然后我读了一个巨大的文件(100GB),只保留文件中频率大于1000的单词.我使用mapWordFrequency [word]> 1000检查文件中单词的频率.然而,结果是我的mapWordFrequency有10亿个映射而且我的文件很大,因此尝试检查mapWordFrequency [word]> 1000,文件中的每个单词都非常慢,需要2天以上.有人可以建议我如何提高上述代码的效率.

地图不适合我的RAM并且交换耗费了大量时间.

擦除频率<1000的所有单词是否有助于使用地图的擦除功能？

Answer 1

您可以使用哈希映射，其中哈希字符串将是键，出现次数将是值。会更快。您可以根据您的要求选择一个好的字符串哈希。这是一些好的哈希函数的链接：

http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx

您也可以使用一些第三方库来实现此目的。

编辑：伪代码

int mapWordFrequency[MAX_SIZE] = {0} ;// if MAX_SIZE is large go with dynamic memory location
int someHashMethod(string input);

loop: currString in ListOfString
          int key = someHashMethod(currString);
          ++mapWordFrequency[key];
          if(mapWordFrequency[key] > 1000)
              doSomeThing();

更新：正如 @Jens 指出的，在某些情况下， someHashMethod() 可能会为两个不同的字符串返回相同的 int （哈希）。在这种情况下，我们必须解决冲突，然后查找时间将不再是常数。此外，由于输入大小非常大，因此创建该大小的单个数组可能是不可能的。在这种情况下，我们可以使用分布式计算概念，但与单机相比，实际查找时间将再次增加。