java - 有没有办法优化这段代码以避免 outOfMemory 错误？

Question

我的总体项目是创建一棵树并使用 Huffman 编码对给定文件进行编码和解码。我正需要解码我的文件。为此，我必须遍历我的霍夫曼树，直到到达最底部的叶子，然后返回由该叶子表示的字节。我根据给方法的位串遍历树。AKA 如果当前位为 1，我会转到树中的 childOne，依此类推。问题是我不断收到outOfMemory错误。有什么办法可以优化这段代码，使其不会使用太多的内存？

    public static int decode(List<Integer> bitArray, HuffmanNode root, int startingPosition,
                          ArrayList<Byte> finalArray)
    {
    HuffmanNode childOne;
    HuffmanNode childZero;
    int currentBit = bitArray.get(startPosition);
    byte newByte;

            childOne = root.getChildOne();
            childZero = root.getChildZero();
            if(childOne == null && childZero == null)
            {
               finalArray.add(root.getByteRepresented()); 
               return startPosition;
            } 
            else if(currentBit == 1)
            {
                startPosition++;
                startPosition = decode(bitArray,childOne,startPosition,finalArray);
            }
            else
            {
                startPosition++;
                startPosition = decode(bitArray,childZero,startPosition,finalArray);
            }

         return startPosition;

}

我需要知道它结束的位数组中的位置以及将指定的字节放入数组中，这就是为什么我将字节放入方法内的数组中并返回和 int。基本上，有没有更好的方法来完成这项工作？

score 2 · Accepted Answer

就在这里。将递归更改为迭代..

temp = root;
childOne = temp.getChildOne();
childZero = temp.getChildZero();
while(childOne != null && childZero != null) {
  currentBit = bitArray.get(startPosition++);
  if (currentBit == 1) {
    temp = childOne;
  } else {
    temp = childZero;
  }
  childOne = temp.getChildOne();
  childZero = temp.getChildZero();
}

score 0 · Accepted Answer

我不知道事情有多大，但我认为你不需要递归。你不能用这样的循环做你需要的事情：

while (curNode.isNotLeaf())
{
  if (currentBit == 1) curNode = curNode.getChildOne();
  else curNode = curNode.getChildZero();
  currentBit = nextBit;
}

addByte(curNode, bigArray)

所以你在这个循环中遍历你的位，当你离开时添加表示的字节，然后继续 - 不需要所有的堆栈帧递归。

score 0 · Accepted Answer

此外，请考虑使用较低级别的数据结构，例如java.util.BitSet代替List<Integer>和java.io.ByteArrayOutputStream代替ArrayList<Byte>.

score 0 · Accepted Answer

如果递归是您的问题，您很可能会遇到堆栈溢出错误。由于您的内存不足，我建议您查看：

确保在每次通话后丢弃bitArray和。finalArray
使用流输出到。
使用 aBitSet作为位数组。
确保您没有意外在树中制作循环。

score -1 · Accepted Answer

看看像 OpenBitSet (Lucene) 这样的压缩位集实现 http://code.google.com/p/javaewah/ http://www.censhare.com/en/aktuelles/censhare-labs/yet-another-compressed -bitset

java - 有没有办法优化这段代码以避免 outOfMemory 错误？

5 回答 5

Related

Reference