Liste de chemins de construction lente

Question

Je construis une liste de hachages qui représentent les chemins de racine à noeud dans un arbre. Mes fonctions fonctionnent mais elles sont incroyablement lentes sur de grandes structures d'arbres - y a-t-il un meilleur moyen? J'ai essayé de construire la liste dans une fonction mais j'ai des hachages uniques où je ne les veux pas.

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

MISE À JOUR:

suggestion de Marcin pour faire le hachage lors de la traversée de l'arbre donne la mauvaise réponse, mais peut-être est la façon dont je l'ai fait?

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

Je pense que votre problème principal est la quantité de données en double que vous produisez: pour chaque feuille de l'arbre, vous allez faire une copie du chemin complet menant à cette feuille et calculer le hachage pour ce chemin. c'est-à-dire que si vous avez 50 000 feuilles sous un nœud de niveau supérieur, le nom de chemin de ce nœud sera copié 50 000 fois et son hachage calculé 50 000 fois.

Si vous pouviez organiser vos données afin que les préfixes de chemins partagés soient réutilisés en tant que références entre les feuilles et les calculs de hachage de ces préfixes sont mis en cache et réutilisés, vous pourriez réduire considérablement la quantité de travail à effectuer.

Answer 2

Où jvisualvm indique-t-il que le goulot d'étranglement de performance est?

Answer 3

Vous créez d'abord une liste de tous les chemins, puis une fois que vous les avez tous, vous calculez des hachages. La taille de la liste de tous ces chemins est O (n^3) (il y a O (n^2) chemins, chaque O (n) étant long) Pourquoi? Pourquoi ne pas simplement calculer les hachages lorsque vous traversez l'arbre? De cette façon, vous prendrez un n hors de votre temps de complexité.

Le code de solution propre (résultat se retrouve dans passé dans la liste des nombres entiers):

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

Ceci est encore O (n^2). C'est à cause du hachage de O (n^2) valeurs de chaînes (chaque nœud a une longueur de chemin proportionnelle à sa profondeur) et vous pouvez l'abaisser même à O (N) si vous aviez un hachage que pour un nœud donné prend seulement un hacher du chemin de ses parents et le modifie d'une certaine manière.

optimisations furhter comprennent: - arbre parallèle traversal - en utilisant le hachage plus intelligent (à savoir de hachage d'un enfant est une fonction de l'enfant et hachage du chemin parent, pas tout le chemin parent).

Answer 4

Je pense que la complexité est toujours la même. Peu importe si vous utilisez une création en ligne de hachages (O (n^2)) ou si vous le faites après récursivité (O (n^2 + n) = O (n^2)). La seule occasion de trouver un moyen rapide est de faire une partie du travail à un autre endroit. par exemple. vous pouvez hacher le chemin tout en insérant un nœud et ne rassembler tous les hashs qu'à un autre point.