构建缓慢的路径列表

我构建了一个代表树中根节点路径的散列列表。我的功能可行，但它们在大型树结构上的速度非常慢 - 有没有更好的方法？我试过在一个函数中构建列表，但我得到了独特的哈希，我不想要它们。构建缓慢的路径列表

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：

马尔钦的建议，使树遍历期间散列给出了错误的答案，但也许这是我做的方式？

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

来源

2009-07-24 Robert

我认为你的主要问题是你正在产生的重复数据量：对于树的每一片叶子，你将制作一个通向该叶片的整个路径的副本并计算该路径的散列值。即如果在一个顶级节点下有50,000张叶子，则该节点的路径名称将被复制50,000次，并且其散列计算50,000次。

如果您可以组织您的数据，以便共享路径前缀被重新用作树叶之间的引用，并且对这些前缀进行散列计算可以被缓存和重用，您可以大幅减少要完成的实际工作量。

来源

2009-07-24 12:20:20

jvisualvm表明性能瓶颈在哪里？

来源

2009-07-24 12:07:33

我不知道如何使用jvisualvm，但我使用100MB XML树计时了这些方法。使得路径... \t做[3614ms] 创建的散列码... \t做[962ms] \t共完成[4576ms] – Robert 2009-07-24 12:13:04

它将无法识别的核心问题在这种情况下，但你真的应该学会如何使用visualvm等分析器。这是攻击性能问题的唯一专业方式。 – 2009-07-24 12:24:20

我强烈建议学习如何使用分析器。 jvisualvm是最低的挂果。 – 2009-07-24 12:32:07

你首先创建一个所有路径的列表，然后一旦你有他们所有你计算哈希。所有这些路径的列表大小是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）一个散列其父母的路径，并以某种方式修改它。

Furhter优化包括： - 并行树遍历 - 使用更加智能散列（即孩子的散列是孩子的功能，并且父路径的散列，而不是整个父路径）。

来源

2009-07-24 12:20:30 Marcin

我觉得复杂性还是一样的。无论你使用内联创建哈希（O（n^2））还是在递归（O（n^2 + n）= O（n^2））之后执行它。寻找快速方法的唯一机会是在另一个地方完成一些工作。例如您可以在插入节点时对散列路径进行散列处理，并仅在其他点收集所有散列。

来源

2009-07-24 14:27:57

构建缓慢的路径列表

回答

相关问题