使用以下递归方法时出现 java.lang.OutOfMemoryError 异常

Question

基本上下面的方法是遍历节点并创建类似结构的图形。创建的对象超过 400K，导致 OutOfMemoryError。有人可以帮助优化以下代码吗？

方法：

    private static PolicyNodeInfo[] mapPolicySteps(PolicyTreatmentNodeInfo fromObj)
 {

    List<PolicyNodeInfo> tmpList = new ArrayList<PolicyNodeInfo>();
    PolicyTreatmentNodeInfo[] childrens = fromObj.getChildrenPolicyInfo(); 
    // Get object policy node children

    if(childrens != null) //if there are no children return empty list
    {
        for(PolicyTreatmentNodeInfo child : childrens) 
        //for each children map the object and recursively go over his children
        {
            if(null!=child)
             {
                if(X3ServerUtil.isStringNotEmptyNotNull(child.getStepName())&& 
                   !child.getStepName().startsWith("Dummy")) 
             //case child is not null (edge) or it's not non operation step (need to ignore)
                    {   
                    int index = tmpList.size();
                    tmpList.add(insertStep(child)); //insert current node

                    tmpList.get(index).setPolicyTreatmentNodeInfoList(mapPolicySteps(child)); 
                    //insert recursively all child nodes
                }
                else
                {
                handleDummyChildNodeInsertion(tmpList, child);
                }
            }
        }
    }
        return tmpList.toArray(new PolicyNodeInfo[tmpList.size()]);
}

Exception : (Stack.java:23) weblogic.kernel.ThreadLocalStack$StackInitialValue.initialValue(ThreadLocalStack.java:159) at weblogic.kernel.FinalThreadLocal$FinalThreadStorage.(FinalThreadLocal.java:208) at weblogic.kernel.AuditableThread.(AuditableThread.java:13) Truncated. see log file for complete stacktrace

图结构与下图类似，有49个节点。并且由于可能有多个路径，方法被调用超过 400K 次..

Answer 1

 I have faced same and resolved by using Garbage collector. There is multiple way to resolve this issue.
 1. Define scope of data members and make sure garbage collector is in picture.
 2. increase java memory for your Environment.
 https://www.wikihow.com/Increase-Java-Memory-in-Windows-7

Answer 2

递归对于遍历大数据集是危险的，因为堆栈内存实际上不受您的控制。（换句话说：我在学校学习递归是一个 "most elegant" 解决方案，在大学里学习 "don't do" - 算了...）

要消除这种情况，请使用合适的数据结构展开，例如按照这些线路排队：

Deque<MyObject> queue = ...
queue.push(rootElement);
while (!queue.isEmpty()) {
    MyObject currentElement = queue.poll();
    // ... process current element
    // and in the end: push children
    currentElement.getChildren().forEach(child -> queue.push(child));
}

对于深度优先遍历，请改用堆栈（即 pop() 而不是 poll()）；

如果仍然出现内存不足错误，您要么必须增加堆space，要么使用其他方法。

Answer 3

问题出在这一行tmpList.get(index).setPolicyTreatmentNodeInfoList(mapPolicySteps(child)); 这里的调用顺序是 mapPolicySteps(child) 首先被调用，只有在 returns .setPolicyTreatmentNodeInfoList(/*Whatever returns from mapPolicySteps(child)*/) 被调用时才被调用。这会创建大量等待 mapPolicySteps 函数结束的堆栈帧。

您需要找到一种方法，使 mapPolicySteps 函数最后被调用。（称为 Tail call / Tail recursion）

Answer 4

感谢您的帮助。一直在努力解决这个问题，并提出了以下解决方案，效果很好。在下面发布答案。 :)

  //Created a class level hashmap
public static Map<String,PolicyNodeInfo> executedElementMap=new HashMap<String,PolicyNodeInfo>();  

// Whichever node is being traversed is stored in the map.
// Before Traversing any node , just checking whether the node has already been traversed , if traversed just add the node and skip the traversing.

private static PolicyNodeInfo[] mapPolicySteps(PolicyTreatmentNodeInfo fromObj)

{
    List<PolicyNodeInfo> tmpList = new ArrayList<PolicyNodeInfo>();
    PolicyTreatmentNodeInfo[] childrens = fromObj.getChildrenPolicyInfo(); // Get object policy node children
    if(childrens != null) //if there are no children return empty list
    {
        for(PolicyTreatmentNodeInfo child : childrens) //for each children map the object and recursively go over his children
        {
            if(null!=child)
                {
                Boolean isNodeTraversed= executedElementMap.containsKey(child.getStepName());
                  if(!isNodeTraversed)
                  {
                    executedElementMap.put(child.getStepName(), child);
                    if(X3ServerUtil.isStringNotEmptyNotNull(child.getStepName())&& !child.getStepName().startsWith(PREFIX_FOR_NON_OPERATION_STEP)) //case child is not null (edge) or it's not non operation step (need to ignore)
                    {   
                        int index = tmpList.size();
                        tmpList.add(insertStep(child)); //insert current node
                        tmpList.get(index).setPolicyTreatmentNodeInfoList(mapPolicySteps(child)); //insert recursively all child nodes
                    }
                    else
                    {
                        handleDummyChildNodeInsertion(tmpList, child);
                    }
                 }  
                 else{
                      tmpList.add(insertStep(child));  
                     }
              }
        }
    }
    return tmpList.toArray(new PolicyNodeInfo[tmpList.size()]);
}

使用以下递归方法时出现 java.lang.OutOfMemoryError 异常

Getting java.lang.OutOfMemoryError exception while using the below Recursive method

java

recursion

out-of-memory