Sort words within memory constraint

Question

Interview prep qn: Given a long list of words, return a list of distinct words along with the count of how many occurred using only 16gb of memory.

I am thinking of using a HashMap which stores only one copy of the word and then subsequently increments the value if the same word is encountered again. This is the only approach I can think of. Overall complexity would be O(n) as I need to traverse through the entire list of words once to populate my hashmap with the word and/or increment its count.

What I am unsure about is how to factor in the 16GB of memory fact into my answer?

If each word is 100 bytes (which likely is not as word length can vary), then my hashmap can be of x number of words long, so what? How can I logically arrive at the limit of my solution? I'm a little unsure of how to proceed here..

Answer 1

Firstly, this is not a sorting problem. At a fundamental level it is a collating problem.

I can think of three approaches to solving it ... depending on the number of distinct words you have.

• If the number of words is small enough that you can hold each distinct word and a count in some kind of map (e.g. a TreeMap<String, Integer>) then the solution is simple and obvious. This requires space (in memory) that is proportional to the number of distinct words. (A TreeMap gives you the counts in word order ...)

• If you can't do that, then there are two approaches:

  • The sort-merge approach:

    1. Divide the input file into N sub-files.
    2. Sort the words in each sub-file (in memory) and wrote out.
    3. Open the N sorted sub-files, and read-and-count the words, each time selecting and counting the smallest word presented on the N files.

    The last step can be performed with space that is proportional to N, and the list of counts can be written straight out to a file. Unless N (the number of subfiles) is huge, you can easily accommodate an input file with "too many" distinct words.

  • The partitioning approach:

    1. Choose N words that partition the "space" of the words into N roughly equal parts.
    2. Then read the input file N times, selecting words between word_i and word_i+1, collate / count them (using a TreeMap as above).
    3. After each collate / count, append the lists of counts to the output file.

The three approaches have roughly the same runtime complexity (O(MlogM)) assuming that TreeMap is used. If you use HashMap, you get O(M) complexity, but the output list is not ordered ... and it doesn't work for the "complicated" approaches.

Answer 2

Below will work with O(n)

Class WordStore
{
    private static HashSet<String> words;
    private int count;
    private long byte;
    //Singleton approach
    public static int addWord(String word)
    {
        if(byte!=17179869184 || (byte+word.length()<17179869184) //checking if the words size is upto 16GB 
        {
            words.add(word);
            count++;
            byte+=byte+word.length();
            return 0;
        }
        else
        {
            System.out.println("Word Count in 16GB :"+count);
            return 1;
        }
    }
}
Class Loader
{
    public static void main(String[] a)
    {
        while(1)
        {       
            String a=readWordOneByOne();
            if(WordStore.addWord(a))
            {
                break;
            }
        }
    }
}

Answer 3

Read in the list and transform the words like word -> (word, 1). Then you collect all the pairs with the same word in a collector an sum the counter like (word,1) + (word,1) = (word,2). A hashmap performs well here.

If the collector grows over a specific limit, write the tuples to disk (a good point for tuning, like writing only some of the less frequent words). The output of the collector is ((word1, count1,) ... (wordN,countN)). When writing you should split the tuples by a hash-key(word) into some files that will be smaller than the memory, say filename= "split" + numwrites + (key%5) where numwrites is just a counter for the splits.

As each word will be in a specific split-suffix (key%5), you now just read and sum all the split with the same ending.

Note, that this hash-based approach will work only, if you have an idea about the amount of splits. If you do not have any, the collector can sort the tuples for each of its output files and you merge them in a last phase. Merge-Sort does not have any bigger memory constraints but has complexity O(n*log(n))

See MapReduce for the description of the general approach.

Answer 4

There are three possible approaches depending on the size of list :-

1. If size of list fits in the memory : Then load the entire list and sort it using quick sort and do running count and store it in output file.

2. If size of list too big for memory but no. of unique words can fit in memory : maintain a TreeSet or HashMap with count and read words one by one and add the count in HashMap.

3. Even Unique words cannot fit in memory :

1. divide the memory in two parts: one for fetching and processing words, second for maintaining counts.
2. read input till it fills part one
3. sort the input.
4. in second part maintain TreeSet and array.
5. TreeSet maps word to index in array
6. traverse sorted array in sequential manner
7. after counting word add its count to array and name to TreeSet.
8. As the input ends , reload next set of words till part one is filled.
9. If second part is full then you need to replace an entry and save it to disk
10. The replacement candidate can be carefully chosen as word which is lexicographically farthest from current word, in this way the number of replacement needed would be reduced.
11. check if word has been already encountered by checking if its file name exists.
12. If file name present load the count from file name and add one in the array

Answer 5

Just use disk/files since you have memory constraints. Let's say you have a 48GB file of words. Load the first 1/3 of the file into the memory (16GB). As you are iterating through words, if a file by the word name does not exist, create a file by the word name and write 1 into it. If a file by the name exists, increment the value in the file by 1 and save it. Then, repeat this process for the 2nd half of the file and the 3rd half of the file. In the end, you will have a file per unique word and the contents of the file will be number of times the word was encountered.

Answer 6

The best approach (that is known) is to use threads (with consumer and producer capabilities and semiphores), stores via a hash, and reads in chunks. Number of threads and chunk size should be dependent on the size of the file.

This way, the only limitation is how much can be written. Thus, a character count would suffice and let the program pick back up where it left off once more memory is obtained.