我想知道在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 回答
仅当
c
是SortedSet
的实例时,TreeSet.addAll(c)
方法才会执行优化 . 在其他情况下,它只是迭代集合并逐个添加元素 .因此,首先将元素放入
ArrayList
然后使用TreeSet.addAll(list)
方法没有任何意义 . 您将获得更差的性能和更高的内存消耗 .从大O角度来看,这两种解决方案都具有复杂性 .
编辑 . TreeSet有两个重要的属性:元素是唯一的,它们是有序的 . 如果您只对unique-elements属性感兴趣,那么使用HashSet会给您带来
n
的复杂性 .仅在传递给
addAll(Collection)
的Collection
是instanceof SortedSet
和instanceof TreeMap
的情况下,树创建时间是线性的 .在第二种情况下,创建
ArrayList
需要额外的时间 . 由于TreeSet#addAll
内部在for
循环中调用Collection#add()
,因此保持相同所以,如果Collection已经不可用,最好调用
add
然后addAll