Увеличивает размер стека, который считается плохой практикой?

Question

Я получил StackOverflowException в своей программе Java, поэтому увеличил размер стека с помощью -Xss100m. Означает ли это, что у меня проблемы с моим кодом? Мне нужно решить следующие задачи:

1. У вас есть н одежда
2. Для каждой пары одежды х, у вы знаете, если х выглядит нормально с у
3. Положите всю одежду в максимальном количестве шкафов, но вы должны убедитесь, что когда вы получите 1 материал из каждого гардероба, он будет выглядеть нормально (так что каждый материал должен выглядеть нормально друг с другом)

Я реализовал это как график, в котором вершины являются одеждой, и есть край между двумя вершины, когда они НЕ выглядят нормально друг с другом. Поэтому в основном мне нужно поставить в один гардероб каждую «группу» связанных вершин. Для этого я использую простой ДФС:

Часть SimpleGraph класса

Map<Integer, List<Integer>> edges; 

    /** 
    * Recursive implementation of DFS algorithm adjusted to SimpleGraph class 
    * 
    * @param vertice    id of vertice we start at 
    * @param visited    array holding info if given vertice was visited or not 
    * @param applyToEachVertice function applied to each vertice we visit 
    * @return      did we marked ANY vertice as visited (if we DFS starting at 
    *        visited vertice it returns false and true otherwise) 
    */ 
    boolean deepFirstSearch(int vertice, boolean[] visited, Consumer<Integer> applyToEachVertice) 
    { 
     if(visited[vertice]) 
      return false; 
     visited[vertice] = true; 
     applyToEachVertice.accept(vertice); 

     // checks if vertice has any neighbours 
     if(!edges.containsKey(vertice)) 
      return true; 

     for(int v : edges.get(vertice)) 
      if(!visited[v]) 
       deepFirstSearch(v, visited, applyToEachVertice); 
     return true; 
    } 

Главной петля

void resolve(SimpleGraph sg) 
    { 
     boolean[] visited = new boolean[sg.getVertNumber()]; 
     final int[] wardrobe = new int[sg.getVertNumber()];   
     for(int i = 0, warNr = 0; i < sg.getVertNumber(); i++) 
     { 
      final int cNr = warNr; 
      if(sg.deepFirstSearch(i, visited, x -> wardrobe[x] = cNr)) 
       warNr++; 
     } 
    } 

Edit: На самом деле реализация DFS в итерационном образом решить эту проблему. Это означает, что я могу запустить приложение без изменения размера стека.

boolean deepFirstSearchNotRecursive(int vertice, boolean[] visited, Consumer<Integer> applyToEachVertice) 
{ 
    if(visited[vertice]) 
     return false; 

    Deque<Integer> stack = new ArrayDeque<>(); 
    stack.push(vertice); 

    while(!stack.isEmpty()) 
    { 
     Integer next = stack.pop(); 
     visited[next] = true; 
     applyToEachVertice.accept(next); 
     if(!edges.containsKey(next)) 
      continue; 
     for(Integer i : edges.get(next)) 
      if(!visited[i]) 
       stack.push(i); 
    } 

    return true; 
} 

Answer 1

Я полагаю, ваши проблемы вызваны не бесконечной рекурсии, как вы будете в состоянии определить проблему с StackOverflowException StackTrace и расширяя размер стека не поможет.

Хотя существуют веские причины увеличить размер трассировки стека, я смею сказать, что глубина вашей цепочки вызовов пропорциональна размеру ввода, переданного вашему приложению. В этом случае вы никогда не сможете сконфигурировать его достаточно большим (если вы не сдерживаете размер o ввода, что может быть сложной задачей для графиков). Переход к алгоритму, где глубина рекурсии не зависит от входных данных, - это путь.

Конечно, если у вас есть предопределенный набор данных или написанный сценарий выброса, который никогда не будет использоваться повторно, то режущие углы предпочтительнее переопределять очаг алгоритма.