Получение исключения 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()]);
}

Исключение: (Stack.java:23) weblogic.kernel.ThreadLocalStack $ StackInitialValue.initialValue (ThreadLocalStack.java:159) в weblogic.kernel.FinalThreadLocal $ FinalThreadStorage. (FinalThreadLocal.java:208) на weblogic.kernel.AuditableThread. (AuditableThread.java:13) Уса. см. файл журнала для полной трассировки стека

Структура графика аналогична приведенной ниже, с 49 узлами. И из-за возможного множественного пути метод вызывается более 400К раз ..

Answer 1

Спасибо за вашу помощь. Пыталась решить проблему и придумала нижеприведенное решение, которое работает нормально. Выложить ответ ниже. :)

  //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()]);
}

Answer 2

Рекурсия опасна для обхода больших наборов данных, так как память стека практически не находится под вашим контролем. (Другими словами: я выучил рекурсию в школе как «самое элегантное» решение, и как «не делай» в университете - пойди разберись ...)

Чтобы устранить это, используйте подходящую структуру данных для развертывания, например, очередь по этим направлениям:

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());

Если это по-прежнему приводит к ошибкам памяти, вам придется либо увеличить пространство кучи, либо использовать совсем другой подход.

Answer 3

Проблема в этой строке tmpList.get(index).setPolicyTreatmentNodeInfoList(mapPolicySteps(child)); порядок звонков здесь mapPolicySteps(child) вызывается первым, и вызывается только , когда возвращается .setPolicyTreatmentNodeInfoList(/*Whatever returns from mapPolicySteps(child)*/). Это создает МНОГО стековых фреймов, ожидающих завершения функции mapPolicySteps.

Вам нужно найти способ, чтобы функция mapPolicySteps вызывалась последней. (Известный как Хвостовой вызов / Хвостовая рекурсия )

Answer 4

 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