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.

Accepted Answer

I suck at explaining theoretical answers but here we go....

I have made an assumption about your question as it is not entirely clear.

- The memory used to store all the distinct words is 80MB (the entire file is bigger).

- The words could contain non-ascii characters (so we just treat the data as raw bytes).

It is sufficient to read over the file twice storing ~ 40MB of distinct words each time.

```
//  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. 
```

Then repeat the above a second time using `even` instead of `odd`.

Then you have divided the task into 2 and can do each separately. No words from the first set will appear in the second set.

The hash is necessary because the words could (in theory) all end with the same letter.

The solution can be extended to work with different memory constraints. Rather than saying just odd/even we can divide the words into X groups by using `number MOD X`.

How to count string num with limit memory?

Solution

Problem