Разница в производительности добавления элементов в Treeset напрямую по сравнению с передачей из массива?

Я хочу знать разницу в производительности между добавлением элементов в TreeSet один за другим и добавлением элементов в ArrayList, а затем передачей в TreesSet методом .addAll(). Я знаю, что TreeSet использует красно-черное дерево в качестве структуры данных. Просто хочу знать основную внутреннюю работу этих двух процессов. Что из следующего будет быстрее и почему?

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

OR,

   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 (может быть и любой другой). Любая помощь будет глубоко оценена. Заранее спасибо.


java arraylist data-structures treeset
person PRIBAN91    schedule 09.06.2015    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Метод TreeSet.addAll(c) выполняет оптимизацию, только если c является экземпляром SortedSet. В других случаях он просто перебирает коллекцию и добавляет элементы один за другим.

Поэтому не имеет смысла сначала помещать элементы в ArrayList, а потом использовать метод TreeSet.addAll(list). Вы получите худшую производительность и более высокое потребление памяти.

С точки зрения большого O, оба решения имеют сложность n*log(n).

РЕДАКТИРОВАТЬ. TreeSet имеет 2 важных свойства: элементы уникальны и отсортированы. Если вас интересует только свойство уникальных элементов, использование HashSet даст вам сложность n.

person Vilmantas Baranauskas    schedule 09.06.2015
comment
Спасибо за ответ. Я думал, что переупорядочивание узлов в TreeSet будет отличаться в двух разных операциях выше. - person PRIBAN91; 09.06.2015
comment
@Nitin Dandriyal: n вставляет каждый журнал взятия (n) - для меня это звучит как n * log (n). - person Vilmantas Baranauskas; 09.06.2015

arrow_upward
0
arrow_downward

Только в том случае, если Collection передается в addAll(Collection), это instanceof SortedSet и instanceof TreeMap время создания дерева является линейным.

Во втором случае создание ArrayList требует дополнительного времени. Остальное то же самое, так как TreeSet#addAll внутренне вызывает Collection#add() в цикле for

Поэтому лучше звонить add, а затем addAll, если Коллекция уже недоступна.

person Nitin Dandriyal    schedule 09.06.2015
comment
Привет, Нитин, спасибо за ответ, но метод addAll() находится вне цикла for. - person PRIBAN91; 09.06.2015
comment
Я знаю, что addAll находится за пределами цикла for в вашем коде, я упоминаю цикл for, используемый в методе addAll метода java.util.TreeSet, в случае, если Collection не является instanceof SortedSet and TreeMap - person Nitin Dandriyal; 09.06.2015