如何用限制内存计算字符串数？

Question

任务是计算输入文件中的字数.

输入文件每行8个字符,有10M行,例如:

aaaaaaaa  
bbbbbbbb  
aaaaaaaa  
abcabcab  
bbbbbbbb  
...

输出是:

aaaaaaaa 2  
abcabcab 1  
bbbbbbbb 2  
...

如果我将所有单词加载到内存中,它将需要80MB内存,但在os系统中只有60MB,我可以用它来执行此任务.那么我该如何解决这个问题呢？

我的算法是使用map<String,Integer>,但jvm在线程"main"中抛出异常java.lang.OutOfMemoryError:Java堆空间.我知道我可以通过设置-Xmx1024m来解决这个问题,但是我想用更少的内存来解决它.

Answer 1

我相信最强大的解决方案是使用磁盘空间.

例如,您可以使用算法对大文件(使用磁盘空间)进行排序,然后对同一个单词的连续出现次数进行排序,从而将文件排序到另一个文件中.

我相信这篇文章可以帮到你.或者自己搜索有关外部排序的信息.

更新1

或者@jordeu建议你可以使用Java嵌入式数据库库:如H2,JavaDB或类似物.

更新2

我想到了另一种可能的解决方案,使用Prefix Tree.但是我还是喜欢第一个,因为我不是他们的专家.

Answer 2

一次读一行,然后有一个HashMap<String,Integer> 例子,你把你的单词作为键,计数作为整数.

如果存在密钥,请增加计数.否则,将键添加到地图中,计数为1.

无需将整个文件保留在内存中.

Answer 3

我不擅长解释理论答案，但我们开始......

我对你的问题做了一个假设，因为它并不完全清楚。

• 用于存储所有不同单词的内存为 80MB（整个文件更大）。
• 这些单词可能包含非 ASCII 字符（因此我们只将数据视为原始字节）。

读取文件两次就足够了，每次存储约 40MB 的不同单词。

//  Loop over the file and for each word:
//
//      Compute a hash of the word. 
//      Convert the hash to a number by some means (skip if possible).
//      If the number is odd then skip to the next word. 
//      Use conventional means to store the distinct word. 
//
//  Do something with all the distinct words. 

even然后使用代替重复上述第二次odd。

然后你将任务分成 2 个，并且可以分别完成每个任务。第一组中的任何单词都不会出现在第二组中。

哈希是必要的，因为这些单词（理论上）可以全部以相同的字母结尾。

该解决方案可以扩展以适应不同的内存限制。我们可以使用 来将单词分为 X 组，而不是仅仅说奇数/偶数number MOD X。