Медленный список путей построения

Question

Я строю список хешей, которые представляют корневые пути узлов в дереве. Мои функции работают, но они невероятно медленны над большими древовидными структурами - есть ли лучший способ? Я попытался создать список в одной функции, но я получаю уникальные хэши, где я их не хочу.

public ArrayList<Integer> makePathList(AbstractTree<String> tree){ 
    StringBuilder buffer = new StringBuilder(); 
    ArrayList<Integer> pl = new ArrayList<Integer>(); 
    ArrayList<StringBuilder> paths = getPaths(tree, buffer); 
    for(StringBuilder sb : paths){ 
     pl.add(sb.toString().hashCode()); 
    } 

    return pl; 
} 

public ArrayList<StringBuilder> getPaths(AbstractTree<String> tree, StringBuilder parent){ 
     ArrayList<StringBuilder> list = new ArrayList<StringBuilder>(); 
     parent.append("/"); 
     parent.append(tree.getNodeName()); 
     list.add(new StringBuilder(parent)); 

     if (!tree.isLeaf()){  
      int i = 0; 
      Iterator<AbstractTree<String>> child = tree.getChildren().iterator(); 
      while (i < tree.getChildren().size()){ 
       list.addAll(getPaths(child.next(), new StringBuilder(parent))); 
       i++; 
      } 
     } 
     return list; 
} 

UPDATE: предложение

Marcin, чтобы сделать хэш во время обхода дерева дает неправильный ответ, но, возможно, это так, как я сделал это?

public ArrayList<Integer> getPaths(AbstractTree<String> tree, StringBuilder parent){ 
    ArrayList<Integer> list = new ArrayList<Integer>(); 

    parent.append("/"); 
    parent.append(tree.getNodeName()); 
    list.add(new StringBuilder(parent).toString().hashCode()); 

    if (!tree.isLeaf()){  
     int i = 0; 
     Iterator<AbstractTree<String>> child = tree.getChildren().iterator(); 
     while (i < tree.getChildren().size()){ 

      list.addAll(getPaths(child.next(), new StringBuilder(parent))); 
      i++; 
     } 
    } 
    return list; 
} 

Answer 1

Я думаю, что ваша основная проблема заключается в количестве дублирующихся данных, которые вы производите: для каждого отдельного листа дерева вы сделаете копию всего пути, ведущего к этому листу, и вычислите хэш для этого пути. то есть если у вас есть 50 000 листов под одним узлом верхнего уровня, то имя пути этого узла будет скопировано 50 000 раз, а его хэш вычислено 50 000 раз.

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

Answer 2

Где указывает jvisualvm, что узкое место производительности?

Answer 3

Сначала вы создадите список всех путей, а затем, когда у вас есть все, что вы вычислили хеши. Размер списка всех этих путей равен O (n^3) (есть O (n^2) пути, каждый O (n) длинный) Почему? Почему бы просто не вычислить хеши при прохождении дерева? Таким образом, вы возьмете целый n из-за сложности вашего времени.

Код для правильного решения (результат заканчивается в принятом в списке целых чисел):

public void getPaths(AbstractTree<String> tree, StringBuilder parentPath, 
    List<Integer> list) 
    StringBuilder newPath = parentPath.clone(); 
    newPath.append("/"); 
    newPath.append(tree.getNodeName()); 
    list.add(newPath.toString().hashCode()); 
    if (!tree.isLeaf()){  
    Iterator<AbstractTree<String>> child = tree.getChildren().iterator(); 
    for (AbstractTree<String> child : tree.getChildren()){ 
     getPaths(child, newPath, list) 
    } 
    } 
} 

Это до сих пор является O (N^2). Это происходит из-за хэширования строк строки O (n^2) (каждый узел имеет длину пути, пропорциональную его глубине), и вы можете свести его даже до O (N), если у вас есть хэш, который для данного узла принимает только a hash пути его родителей и каким-то образом его модифицирует.

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

Answer 4

Я считаю, что сложность остается прежней. Независимо от того, используете ли вы встроенное создание хешей (O (n^2)) или делаете это после рекурсии (O (n^2 + n) = O (n^2)). Единственная возможность найти быстрый способ - это выполнить часть работы в другом месте. например вы можете хэш-путь при вставке узла и только собрать все хэши в другой точке.