3

对于树结构如下

public class Node implements Comparable<Node> {
    private List<Node> nodes=new ArrayList<Node>();
    private String name="";
    private List<String> leaves=new ArrayList<String>();
    private Node parent=null;

    public List<Node> getNodes() {
        return nodes;
    }

    public void setNodes(List<Node> nodes) {
        this.nodes = nodes;
    }

    public List<String> getLeaves() {
        return leaves;
    }

    public void setLeaves(List<String> leaves) {
        this.leaves = leaves;
    }

    @Override
    public int compareTo(Node o) {
        return this.getName().compareTo(o.getName());
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Node getParent() {
        return parent;
    }

    public void setParent(Node parent) {
        this.parent = parent;
    }

    public int getDepth() {
        int depth = 0;
        Node parent = this.getParent();
        while (parent != null) {
            depth++;
            parent = parent.getParent();
        }
        return depth;
    }
}

从一个节点，我希望有一个方法可以返回所有不同的直接和间接叶子（在上述情况下，字符串leaves 将是叶子），用于该节点按排序顺序。

上面是一个高度分解的数据结构，便于测试和演示。我尝试了以下3种方法，

方法 A 当深度很大时非常慢~20，因为最深的叶子被遍历了几次，每个祖先一次，因此多次遍历相同的路径。

    public List<String> getLeavesDeep1() {
        Set<String> leaves = new TreeSet<String>();
        leaves.addAll(getLeaves());
        for (Node node : getNodes()) {
            leaves.addAll(node.getLeavesDeep1());
        }
        return new ArrayList<String>(leaves);
    }

平均：12694 毫秒/无排序/区别>平均：471 毫秒

方法 B 比 A 快一点，因为节点的数量相对比叶子少得多，所以使用方法 A 但是对于节点，然后对于每个节点，只获得直接叶子。

    private List<Node> getNodesDeep2() {
        Set<Node> nodes = new TreeSet<Node>();
        nodes.addAll(getNodes());
        for (Node node : getNodes()) {
            nodes.addAll(node.getNodesDeep2());
        }
        return new ArrayList<Node>(nodes);
    }

    public List<String> getLeavesDeep2() {
        Set<String> leaves = new TreeSet<String>();
        leaves.addAll(getLeaves());
        for (Node node : getNodesDeep2()) {
            leaves.addAll(node.getLeaves());
        }
        return new ArrayList<String>(leaves);
    }

平均：4355 毫秒/没有排序/区别>平均：2406 毫秒

方法 C 在返回之前避免使用 TreeSet，使用 ArrayList 并排序和过滤（虽然不是排序/区分的最佳方式）

    private List<Node> getNodesDeep3() {
        List<Node> nodes = new ArrayList<Node>();
        nodes.addAll(getNodes());
        for (Node node : getNodes()) {
            nodes.addAll(node.getNodesDeep3());
        }
        return new ArrayList<Node>(new TreeSet<Node>(nodes));
    }

    public List<String> getLeavesDeep3() {
        List<String> leaves = new ArrayList<String>();
        leaves.addAll(getLeaves());
        for (Node node : getNodesDeep3()) {
            leaves.addAll(node.getLeaves());
        }
        return new ArrayList<String>(new TreeSet<String>(leaves));
    }

平均：4400

寻找更快的东西，我知道可以使用某些树遍历，但如果存在，我更喜欢更简单的东西。PS 这些目前没有用于搜索的用例。在我的真实课堂中，时间比上述情况高出大约 3 倍，因为结构要复杂得多，叶子不是简单的字符串，而是 POJO

以下是我用来获取时间的测试

private static final int NODES = 5;
private static final int LEAVES = 25;
private static final int DEPTH = 8;

public void addChildren(Node parent) {
    List<Node> nodes = new ArrayList<Node>();
    List<String> leaves = new ArrayList<String>();
    for (int i = 0; i < LEAVES; i++) {
        leaves.add(String.format("%s_leaf_%s", parent.getName(), i));
    }
    for (int i = 0; i < NODES; i++) {
        Node child = new Node();
        child.setParent(parent);
        child.setName(String.format("%s_%s", parent.getName(), i));
        nodes.add(child);
        if (child.getDepth() < DEPTH) {
            addChildren(child);
        }
    }
    parent.setNodes(nodes);
    parent.setLeaves(leaves);
}

@Test
public void testCase() {
    long start, tot=0;
    long t = 0;
    List<String> leaves;
    Node target = new Node();
    target.setName("Root");
    addChildren(target);
    for (int i = 0; i < 10; i++) {
        start = System.currentTimeMillis();
        leaves = target.getLeavesDeep5();
        t = System.currentTimeMillis() - start;
        tot += t;
        System.out.println(leaves.size() + " " + t);
    }

    System.out.println("Avg: " + (tot / 10));
}

任何语言的答案都是可以接受的，包括伪代码，只要它没有将解决方案与该语言紧密联系起来（例外：纯 java 代码被禁止使用第二个子句）

4

1 回答 1

1

我运行了您的测试，它给了我以下结果（我使用了您的版本 3，一个稍作修改的版本 3 和一个新版本）

2441400 8038
...
2441400 7890
Avg: 7872

2441400 4850
...
2441400 3990
Avg: 4165

2441400 980
...
2441400 710
Avg: 786

我第一次改变

return new ArrayList<String>(new TreeSet<String>(leaves));

至

Collections.sort(leaves);
return leaves;

请参阅添加到集合然后对其进行排序或添加到已排序的集合是否更快？

这使执行时间减少了近 50%。注意：TreeSet 将删除重复项，排序不会。

然后，我编写了一个新的迭代器方法，将您的 2 个方法合二为一，并一起消除了递归。我还摆脱了 ArrayLists 以避免我们不需要的大小调整和复制，因为我们只迭代并且从不通过索引访问。

编辑：使用 ArrayList 存储叶子将时间从 800 毫秒增加到大约 1400 毫秒。

public List<String> getLeavesDeepX()
{
    final Deque<Node> nodes = new LinkedList<Node>();
    final Collection<String> leaves = new LinkedList<String>();
    //final Collection<String> leaves = new LinkedHashSet<String>(); -- use for removing dupes
    nodes.add(this);
    do
    {
        final Node current = nodes.pop();
        leaves.addAll(current.getLeaves());
        nodes.addAll(current.getTreeNodes());
    }
    while(nodes.isEmpty() == false);

    final ArrayList<String> result = new ArrayList<String>(leaves);
    Collections.sort(result);
    return result;
}

我将所有结果放入不同的列表中，并在最后进行了比较。

    System.out.println(Arrays.equals(leaves1.toArray(), leaves2.toArray()));
    System.out.println(Arrays.equals(leaves1.toArray(), leaves3.toArray()));
    System.out.println(Arrays.equals(leaves2.toArray(), leaves3.toArray()));

输出：

true
true
true

所以至少在我的系统上它的速度提高了大约 10 倍。

Edit2：在案例 3 中跳过排序使其达到 140 毫秒。所以 600ms 用于比较和排序。任何进一步的重大改进都需要在那里进行。

Edit3：消除递归还有一个好处是树的深度对性能的影响较小。将 TestTree 更改为 2/2/20 (N/L/D) 会产生大约相同数量的叶子 (2m)，但在使用递归 (>70k) 时性能要差得多，但没有慢很多（从 1200 到 2500）。

于 2012-10-08T16:31:56.990 回答