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

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;
}

ОБНОВЛЕНИЕ:

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

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

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

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), если у вас есть хеш, который для данного узла занимает только хеш пути его родителей и каким-то образом его изменяет.

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

Answer 4

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