如何有效地扩展一个大型JTree

There are several related questions, about auto-expanding a JTree when a new TreeModel is set, or about expanding a JTree in general, and some of them are also aiming at the performance of expanding many paths in a JTree.

有几个相关的问题，关于在设置一个新的TreeModel时自动扩展一个JTree，或者关于一般地扩展一个JTree，其中一些还针对扩展一个JTree中的许多路径的性能。

However, none of the proposed solutions seems to cover what one could consider a "simple" application case: I have a large tree (that is, a tree that is either very deep, very broad, or both), and I want to fully expand it programmatically.

然而，所提出的解决方案中似乎没有一个能够涵盖“简单”的应用案例:我有一个大树(也就是说，一个树要么非常深，要么非常宽，要么两者都有)，我想以编程的方式全面扩展它。

The following is a MCVE that shows the problem: It creates a tree model with 100k nodes. Pressing the button triggers a call to expandAll, which tries to expand all nodes using an approach that was derived from the answers to the related questions.

下面是一个MCVE，它显示了这个问题:它创建了一个有100k个节点的树模型。按下按钮将触发对expandAll的调用，该调用试图使用从相关问题的答案派生的方法扩展所有节点。

The problem is that expanding these 100k nodes takes approximately 13 seconds (on an average machine, with a recent JVM).

问题是，扩展这些100k节点大约需要13秒(在一台普通的机器上，使用最近的JVM)。

import java.awt.BorderLayout;
import java.awt.GridLayout;
import java.util.function.Consumer;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JScrollPane;
import javax.swing.JTree;
import javax.swing.SwingUtilities;
import javax.swing.tree.DefaultMutableTreeNode;
import javax.swing.tree.DefaultTreeModel;
import javax.swing.tree.TreeModel;


public class TreeExpansionPerformanceProblem
{
    public static void main(String[] args)
    {
        SwingUtilities.invokeLater(
            () -> createAndShowGUI());
    }

    private static void createAndShowGUI()
    {
        JFrame f = new JFrame();
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        f.getContentPane().setLayout(new GridLayout(1,0));

        f.getContentPane().add(createTestPanel(
            TreeExpansionPerformanceProblem::expandAll));

        f.setSize(800,600);
        f.setLocationRelativeTo(null);
        f.setVisible(true);
    }

    private static JPanel createTestPanel(Consumer<JTree> expansionMethod)
    {
        JPanel panel = new JPanel(new BorderLayout());
        JTree tree = new JTree(createTestTreeModel());
        panel.add(new JScrollPane(tree), BorderLayout.CENTER);

        JPanel buttonPanel = new JPanel();
        JButton expandAllButton = new JButton("Expand all");
        expandAllButton.addActionListener( e -> 
        {
            System.out.println("Expanding...");
            long before = System.nanoTime();
            expansionMethod.accept(tree);
            long after = System.nanoTime();
            System.out.println("Expanding took "+(after-before)/1e6);

        });
        buttonPanel.add(expandAllButton);
        panel.add(buttonPanel, BorderLayout.SOUTH);
        return panel;
    }

    private static void expandAll(JTree tree)
    {
        int r = 0;
        while (r < tree.getRowCount())
        {
            tree.expandRow(r);
            r++;
        }
    }

    private static TreeModel createTestTreeModel() 
    {
        DefaultMutableTreeNode root = new DefaultMutableTreeNode("JTree");
        addNodes(root, 0, 6, 6, 10);
        return new DefaultTreeModel(root);
    }

    private static void addNodes(DefaultMutableTreeNode node, 
        int depth, int maxDepth, int count, int leafCount)
    {
        if (depth == maxDepth)
        {
            return;
        }
        for (int i=0; i<leafCount; i++)
        {
            DefaultMutableTreeNode leaf = 
                new DefaultMutableTreeNode("depth_"+depth+"_leaf_"+i);
            node.add(leaf);
        }
        if (depth < maxDepth - 1)
        {
            for (int i=0; i<count; i++)
            {
                DefaultMutableTreeNode child = 
                    new DefaultMutableTreeNode("depth_"+depth+"_node_"+i);
                node.add(child);
                addNodes(child, depth+1, maxDepth, count, leafCount);
            }
        }

    }
}

Are there any options that allow expanding many nodes more efficiently?

有什么方法可以更有效地扩展多个节点吗?

2 个解决方案

#1

There are various bottlenecks when fully expanding a large tree, and different ways to circumvent these.

当完全扩展一个大的树时，有各种各样的瓶颈，并且有不同的方法来绕过这些瓶颈。

Interestingly, collecting the TreePath objects for the expansion and traversing the tree in general is not the most expensive part. According to profiler runs in the VisualVM and in the Java Flight Recorder, most of the time is spent when computing the "mapping" between the model state (the TreeModel) and the view (the JTree). This mainly refers to

有趣的是，收集TreePath对象进行扩展和遍历树通常不是最昂贵的部分。根据profiler在VisualVM和Java飞行记录器中运行，大多数时间都花在计算模型状态(TreeModel)和视图(JTree)之间的“映射”上。这主要是指

• computing the row heights for the JTree
• 计算JTree的行高度
• computing the bounds of the labels in the TreeCellRenderer
• 计算树状渲染器中标签的界限

Not all of these computations may be avoided. However, expanding the tree can be made significantly faster by

并不是所有的计算都可以避免。但是，扩展树的速度可以大大加快

• setting a fixed row height, with JTree#setRowHeight
• 使用JTree# setrowh8设置一个固定的行高度
• temporarily disabling the TreeExpansionListeners of the tree
• 暂时禁用树的树状扩张器。

The following is an MCVE that compares the "naïve" approach from the question, which takes 13 seconds for expanding a tree with 100k nodes, to a slightly faster approach, that only takes 1 second for expanding the same tree.

下面是一个MCVE，它比较了这个问题的“幼稚”方法，它用了13秒的时间来扩展一个有100k个节点的树，这个方法稍微快一点，只需要1秒就可以扩展相同的树。

import java.awt.BorderLayout;
import java.awt.Component;
import java.awt.GridLayout;
import java.util.Arrays;
import java.util.List;
import java.util.function.Consumer;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JScrollPane;
import javax.swing.JTree;
import javax.swing.SwingUtilities;
import javax.swing.event.TreeExpansionListener;
import javax.swing.tree.DefaultMutableTreeNode;
import javax.swing.tree.DefaultTreeModel;
import javax.swing.tree.TreeCellRenderer;
import javax.swing.tree.TreeModel;
import javax.swing.tree.TreePath;


public class TreeExpansionPerformanceSolution
{
    public static void main(String[] args)
    {
        SwingUtilities.invokeLater(
            () -> createAndShowGUI());
    }

    private static void createAndShowGUI()
    {
        JFrame f = new JFrame();
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        f.getContentPane().setLayout(new GridLayout(1,0));

        f.getContentPane().add(createTestPanel(
            TreeExpansionPerformanceSolution::expandAll));

        f.getContentPane().add(createTestPanel(
            TreeExpansionPerformanceSolution::expandAllFaster));

        f.setSize(800,600);
        f.setLocationRelativeTo(null);
        f.setVisible(true);
    }

    private static JPanel createTestPanel(Consumer<JTree> expansionMethod)
    {
        JPanel panel = new JPanel(new BorderLayout());
        JTree tree = new JTree(createTestTreeModel());
        panel.add(new JScrollPane(tree), BorderLayout.CENTER);

        JPanel buttonPanel = new JPanel();
        JButton expandAllButton = new JButton("Expand all");
        expandAllButton.addActionListener( e -> 
        {
            System.out.println("Expanding...");
            long before = System.nanoTime();
            expansionMethod.accept(tree);
            long after = System.nanoTime();
            System.out.println("Expanding took "+(after-before)/1e6);

        });
        buttonPanel.add(expandAllButton);
        panel.add(buttonPanel, BorderLayout.SOUTH);
        return panel;
    }

    private static void expandAll(JTree tree)
    {
        int r = 0;
        while (r < tree.getRowCount())
        {
            tree.expandRow(r);
            r++;
        }
    }

    private static void expandAllFaster(JTree tree)
    {
        // Determine a suitable row height for the tree, based on the 
        // size of the component that is used for rendering the root 
        TreeCellRenderer cellRenderer = tree.getCellRenderer();
        Component treeCellRendererComponent = 
            cellRenderer.getTreeCellRendererComponent(
                tree, tree.getModel().getRoot(), false, false, false, 1, false);
        int rowHeight = treeCellRendererComponent.getPreferredSize().height + 2;
        tree.setRowHeight(rowHeight);

        // Temporarily remove all listeners that would otherwise
        // be flooded with TreeExpansionEvents
        List<TreeExpansionListener> expansionListeners =
            Arrays.asList(tree.getTreeExpansionListeners());
        for (TreeExpansionListener expansionListener : expansionListeners)
        {
            tree.removeTreeExpansionListener(expansionListener);
        }

        // Recursively expand all nodes of the tree
        TreePath rootPath = new TreePath(tree.getModel().getRoot());
        expandAllRecursively(tree, rootPath);

        // Restore the listeners that the tree originally had
        for (TreeExpansionListener expansionListener : expansionListeners)
        {
            tree.addTreeExpansionListener(expansionListener);
        }

        // Trigger an update for the TreeExpansionListeners
        tree.collapsePath(rootPath);
        tree.expandPath(rootPath);
    }

    // Recursively expand the given path and its child paths in the given tree
    private static void expandAllRecursively(JTree tree, TreePath treePath)
    {
        TreeModel model = tree.getModel();
        Object lastPathComponent = treePath.getLastPathComponent();
        int childCount = model.getChildCount(lastPathComponent);
        if (childCount == 0)
        {
            return;
        }
        tree.expandPath(treePath);
        for (int i=0; i<childCount; i++)
        {
            Object child = model.getChild(lastPathComponent, i);
            int grandChildCount = model.getChildCount(child);
            if (grandChildCount > 0)
            {
                class LocalTreePath extends TreePath
                {
                    private static final long serialVersionUID = 0;
                    public LocalTreePath(
                        TreePath parent, Object lastPathComponent)
                    {
                        super(parent, lastPathComponent);
                    }
                }
                TreePath nextTreePath = new LocalTreePath(treePath, child);
                expandAllRecursively(tree, nextTreePath);
            }
        }
    }


    private static TreeModel createTestTreeModel() 
    {
        DefaultMutableTreeNode root = new DefaultMutableTreeNode("JTree");
        addNodes(root, 0, 6, 6, 10);
        return new DefaultTreeModel(root);
    }

    private static void addNodes(DefaultMutableTreeNode node, 
        int depth, int maxDepth, int count, int leafCount)
    {
        if (depth == maxDepth)
        {
            return;
        }
        for (int i=0; i<leafCount; i++)
        {
            DefaultMutableTreeNode leaf = 
                new DefaultMutableTreeNode("depth_"+depth+"_leaf_"+i);
            node.add(leaf);
        }
        if (depth < maxDepth - 1)
        {
            for (int i=0; i<count; i++)
            {
                DefaultMutableTreeNode child = 
                    new DefaultMutableTreeNode("depth_"+depth+"_node_"+i);
                node.add(child);
                addNodes(child, depth+1, maxDepth, count, leafCount);
            }
        }

    }
}

---

Notes:

注:

• This is a self-answered question, and I hope that this answer may be helpful for others. Nevertheless, 1 second is still rather slow. I tried some other things as well, e.g. setting tree.setLargeModel(true), but this did not have a positive effect (in fact, it was even slower!). Most of the time is still spent in the final update of the visual state of the tree, and I'd be happy to see further improvements here.

  这是一个自我回答的问题，我希望这个答案能对其他人有所帮助。然而，1秒仍然相当缓慢。我也尝试了一些其他的东西，比如设置树。大多数时间仍然花在最终更新树的视觉状态上，我很高兴看到这里有进一步的改进。

• The expandAllRecursively method could be replaced by few lines involving DefaultMutableTreeNode#breadthFirstEnumeration and DefaultTreeModel#getPathToRoot, without sacrificing much of the performance. But in the current form, the code solely operates on the TreeModel interface, and should work with any kind of nodes.

  扩展递归方法可以被包含DefaultMutableTreeNode#breadthFirstEnumeration和DefaultTreeModel#getPathToRoot的几行替换，而不会牺牲大部分性能。但是在当前的形式中，代码只对TreeModel接口进行操作，并且应该与任何类型的节点一起工作。

#2

As discussed here, JTree already uses the flyweight pattern to optimize rendering. I'd argue that your approach in expandAllFaster() is sufficient. Expanding all of >10⁵ leaves is unwieldy at best. The resulting tree is difficult to browse meaningfully, although suitable search controls may mitigate this.

正如这里讨论的，JTree已经使用flyweight模式来优化渲染。我认为您在expandAllFaster()中的方法是足够的。将>105的叶子全部展开，充其量也只是个笨拙的动作。生成的树很难有意义地浏览，尽管适当的搜索控件可以减轻这一点。

An interesting compromise is seen in the Mac OS X TreeUI delegate, com.apple.laf.AquaTreeUI. It recursively expands the selected node and its children when the option key is pressed, as determined by MouseEvent::isAltDown(). See the Action named "aquaFullyExpandNode" for details.

Mac OS X TreeUI委托com.apple.lafatreeui就是一个有趣的妥协。它在按下选项键时递归地展开所选节点及其子节点，这是由MouseEvent: isAltDown()决定的。详细信息请参见“aquaFullyExpandNode”操作。

Finally, saving the user's expansion as a preference might be worthwhile, for example.

最后，将用户的扩展保存为首选项可能是值得的，例如。

I'm working on…filtering a >100k-node-JTree on the fly.

我正在研究…在动态中过滤一个>100k-node-JTree。

Focusing on a model-based approach, as suggested here, move the search to a separate, perhaps modeless, dialog. In outline,

如本文所建议的，关注基于模型的方法，将搜索转移到一个单独的(可能是无模型的)对话框中。在大纲,

• Construct a prefix tree based on the tree model to be used as a dictionary, perhaps using one of the approaches suggested here.

  基于要用作字典的树模型构建一个前缀树，可能使用本文建议的一种方法。

• Let a DocumentListener monitor the search field and condition a custom TableModel to display matches as the user types.

  让一个DocumentListener监视搜索字段，并设置一个自定义的TableModel，以显示用户类型的匹配。

• Display no matches until some minimum number of characters has been typed; three is a common choice for large models.

  在输入一些最少的字符之前不显示匹配项;三是大型模型的常见选择。

• Let a TableModelListener expand tree nodes corresponding to selected rows; alternatively, expand selected rows in an Expand button handler; in a modeless context, fire a suitable PropertyChangeEvent for which the tree should listen.

  让TableModelListener展开与所选行对应的树节点;或者，在展开按钮处理程序中展开选定的行;在无模型的上下文中，触发树应该侦听的合适的PropertyChangeEvent。