java - 直接在 Treeset 中添加元素与从 arraylist 传输元素的性能有何差异？

Question

我想知道在 TreeSet 中逐一添加元素与在 ArrayList 中添加元素然后通过 .addAll() 方法传输到 TreesSet 的性能差异。我知道TreeSet使用红黑树作为其数据结构。只是想知道这两个过程的基本内部工作原理。以下哪一项会更快，为什么？

    TreeSet<Integer> ts = new TreeSet<Integer>();   
    for(int i=0;i<n;i++)
        ts.add(sc.nextInt());

或者，

   TreeSet<Integer> ts = new TreeSet<Integer>();    
   ArrayList<Integer> ar = new ArrayList<Integer>();
        for(int i=0;i<n;i++)
            ts.add(sc.nextInt());

            ts.addAll(ar);

这里 sc 是 Scanner 类的一个对象(也可以是其他任何对象)。任何帮助将不胜感激。提前致谢。

Answer 1

仅当 c 是 SortedSet 的实例时，

TreeSet.addAll(c) 方法才会进行优化。在其他情况下，它只是迭代集合并逐个添加元素。

因此，先将元素放入ArrayList然后再使用TreeSet.addAll(list)方法是没有任何意义的。您将获得更差的性能和更高的内存消耗。

从大 O 的角度来看，两种解决方案都有 n*log(n) 复杂性。

编辑。 TreeSet 有两个重要的属性:元素是唯一的并且它们是排序的。如果您只对 unique-elements 属性感兴趣，那么使用 HashSet 的复杂度将为 n。