Slow building list of paths

Question

I'm building a list of hashes that represent root to node paths in a tree. My functions work but they are incredibly slow over large tree structures - is there a better way? I've tried building the list in one function but I get unique hashes where I don't want them.

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's suggestion to make the hash during tree traversal gives the wrong answer, but perhaps that is the way I have done it?

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

Where does jvisualvm indicate that the performance bottleneck is?

Answer 2

I think your main problem is the amount of duplicate data you are producing: for every single leaf of the tree, you will make a copy of the entire path leading up to that leaf and compute the hash for that path. i.e. if you have 50,000 leaves under one top-level node, then the path name of that node will be copied 50,000 times and its hash computed 50,000 times.

If you could organize your data so that shared path prefixes are reused as references between leaves and hash calculations for these prefixes are cached and reused, you could drastically reduce the actual amount of work to be done.

Answer 3

You first create a list of all paths and then once you have them all you compute hashes. Size of list of all those paths is O(n^3) (there's O(n^2) paths, each O(n) long) Why? Why not just compute the hashes as you traverse the tree? This way you'll take whole one n out of your time complexity.

The code for proper solution (result ends up in passed in list of integers):

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

This still is O(n^2). That is because of hashing of O(n^2) worth of strings (each node has a path length proportional to its depth) and you could bring it down even to O(N) if you had a hash that for given node takes only a hash of the path of its parents and modifies it in some way.

Furhter optimizations include: - parallel tree traversal - using smarter hashing (i.e. hash of a child is a function of child and hash of the parent path, not whole parent path).

Answer 4

I think complexity is still the same. No matter if you use a inline creation of hashes (O(n^2)) or doing it after recursion (O(n^2 + n) = O(n^2)). The only opportunity to find a fast way is to do some of the work at another place. e.g. you can hash the path while inserting a node and only gather all hashes at another point.