首页 文章

在Treeset中直接添加元素与从arraylist转移的性能差异?

提问于
浏览
0

我想知道在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类的一个对象(它也可能是其他任何东西) . 任何帮助将深表感谢 . 提前致谢 .

2 回答

  • 2

    仅当 cSortedSet 的实例时, TreeSet.addAll(c) 方法才会执行优化 . 在其他情况下,它只是迭代集合并逐个添加元素 .

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

    从大O角度来看,这两种解决方案都具有复杂性 .

    编辑 . TreeSet有两个重要的属性:元素是唯一的,它们是有序的 . 如果您只对unique-elements属性感兴趣,那么使用HashSet会给您带来 n 的复杂性 .

  • 0

    仅在传递给 addAll(Collection)Collectioninstanceof SortedSetinstanceof TreeMap 的情况下,树创建时间是线性的 .

    在第二种情况下,创建 ArrayList 需要额外的时间 . 由于 TreeSet#addAll 内部在 for 循环中调用 Collection#add() ,因此保持相同

    所以,如果Collection已经不可用,最好调用 add 然后 addAll

相关问题