How to optimize my Trie implementation so that I don't get OutOfMemoryError

Question

I'm implementing text predictions using a very simple Trie implementation, which is a slightly modified version of this code

It performs better than I initially expected, but I'm receiving an OutOfMemoryError frequently. Any ideas how can solve this problem by either:

• increasing the memory designated to my app
• optimizing the implementation to use less memory

or any other suggestions?

I've seen recommendations that the memory limitation problems could be avoided by using a native implementation of a part of the code, but I would prefer to stay in Java, if possible.

Answer 1

You could try turning on largeHeap in your manifest to see if it helps:

http://developer.android.com/guide/topics/manifest/application-element.html#largeHeap

Answer 2

By doing this.next = new Node[R]; the implementation allocates an array with 26 pointers to nodes on level 1, then 26^26 pointers to nodes on level 2, then 26^26^26 on level 3 and so on. That could be one reason you run out of memory.

You can try and change the implementation so that every Node has a HashMap of nodes with a small initial capacity, say 5. The HashMap will grow only when there's a real need - which will save some memory.

Another problem in that code is with the delete:

    // delete a node  
    public void delete(Node node) {  
        for(int i = 0; i < R; i++) {  
            if(node.next != null) {  
                delete(node.next[i]);  
            }  
        }  
        node = null;  // <-- this is not doing anything!
    }

The reason it's not doing anything is that the reference to the node is passed by value in Java - so the real reference remains intact. What you should do instead is:

    // delete a node  
    public void delete(Node node) {  
        for(int i = 0; i < R; i++) {  
            if(node.next != null) {  
                delete(node.next[i]);  
                node.next[i] = null; // <-- here you nullify the actual array item
            }                        // which makes the object a good candidate for 
                                     // the next time GC will run
        }              
    }

So it could also be a memory leak - in case you counted on delete to free space.