java - 如何用有限的内存计算字符串数？

Question

任务是计算输入文件中的单词数。

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

aaaaaaaa  
bbbbbbbb  
aaaaaaaa  
abcabcab  
bbbbbbbb  
...

输出是:

aaaaaaaa 2  
abcabcab 1  
bbbbbbbb 2  
...

如果我将所有单词加载到内存中，它将占用 80MB 内存，但 os 系统中只有 60MB 可用于此任务。那么我该如何解决这个问题呢？

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

Answer 1

我认为最可靠的解决方案是使用磁盘空间。

例如，您可以使用对大文件(占用磁盘空间)进行排序的算法，将您的文件放在另一个文件中进行排序，然后计算同一单词的连续出现次数。

我相信这 post能帮你。或者自己搜索关于external sorting的东西.

更新 1

或者如@jordeu 所建议的，您可以使用 Java 嵌入式数据库库:例如 H2、JavaDB 或类似的库。

更新 2

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