直接在 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的一个对象class（也可以是其他任何东西）。任何帮助将不胜感激。提前致谢。

Answer 1

仅当传递给 addAll(Collection) 的 Collection 是 instanceof SortedSet 并且 instanceof TreeMap 树创建时间是线性的。

在您的第二种情况下，创建 ArrayList 需要额外的时间。其余相同，因为 TreeSet#addAll 在 for 循环

内部调用 Collection#add()

因此，如果集合已经不可用，最好先调用 add 然后调用 addAll

Answer 2

TreeSet.addAll(c) 方法仅在 c 是 SortedSet 的实例时才进行优化。在其他情况下，它只是遍历集合并一个一个地添加元素。

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

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

编辑。 TreeSet 有两个重要的属性：元素是唯一的，并且它们是有序的。如果您只对唯一元素属性感兴趣，使用 HashSet 会给您带来 n.

的复杂度

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

Difference in performance of adding elements in Treeset directly vs transferring from arraylist?

java

arraylist

treeset

data-structures