How to count string num with limit memory?

Question

The task is to count the num of words from a input file.

the input file is 8 chars per line, and there are 10M lines, for example:

aaaaaaaa  
bbbbbbbb  
aaaaaaaa  
abcabcab  
bbbbbbbb  
...

the output is:

aaaaaaaa 2  
abcabcab 1  
bbbbbbbb 2  
...

It'll takes 80MB memory if I load all of words into memory, but there are only 60MB in os system, which I can use for this task. So how can I solve this problem?

My algorithm is to use map<String,Integer>, but jvm throw Exception in thread "main" java.lang.OutOfMemoryError: Java heap space. I know I can solve this by setting -Xmx1024m, for example, but I want to use less memory to solve it.

Answer 1

I believe that the most robust solution is to use the disk space.

For example you can sort your file in another file, using an algorithm for sorting large files (that use disk space), and then count the consecutive occurrences of the same word.

I believe that this post can help you. Or search by yourself something about external sorting.

Update 1

Or as @jordeu suggest you can use a Java embedded database library: like H2, JavaDB, or similars.

Update 2

I thought about another possible solution, using Prefix Tree. However I still prefer the first one, because I'm not an expert on them.

Answer 2

Read one line at a time and then have e.g. a HashMap<String,Integer> where you put your words as key and the count as integer.

If a key exists, increase the count. Otherwise add the key to the map with a count of 1.

There is no need to keep the whole file in memory.