java - 如何优化我的 Trie 实现，以免出现 OutOfMemoryError

Question

我正在使用一个非常简单的 Trie 实现来实现文本预测，这是此代码的略微修改版本

它的性能比我最初预期的要好，但我OutOfMemoryError经常收到。任何想法如何通过以下方式解决此问题：

• 增加指定给我的应用程序的内存
• 优化实现以使用更少的内存

或任何其他建议？

我已经看到一些建议，通过使用部分代码的本机实现可以避免内存限制问题，但如果可能的话，我更愿意留在 Java 中。

Answer 1

您可以尝试在清单中打开 largeHeap 以查看是否有帮助：

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

Answer 2

通过this.next = new Node[R];执行分配一个数组，其中包含 26 个指向第 1 级节点的指针，然后是 26^26 个指向第 2 级节点的指针，然后是 26^26^26 指向第 3 级节点的指针，依此类推。这可能是您内存不足的原因之一。

您可以尝试更改实现，以便每个节点都有一个初始容量较小的节点的 HashMap，例如 5。只有在真正需要时 HashMap 才会增长 - 这将节省一些内存。

该代码中的另一个问题是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!
    }

它不做任何事情的原因是对节点的引用是by value在 Java 中传递的——所以真正的引用保持不变。你应该做的是：

    // 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
        }              
    }

所以它也可能是内存泄漏 - 如果你指望delete释放空间。