Быстрее добавить в коллекцию, а затем отсортировать или добавить в отсортированную коллекцию?

Question

Если у меня есть Map, например:

HashMap<Integer, ComparableObject> map;

, и я хочу получить коллекцию значений, отсортированных с использованием естественного упорядочения, какой метод самый быстрый?

(A)

Создайте экземпляр сортируемой коллекции, например ArrayList, добавьте значения и затем сортируйте его:

List<ComparableObject> sortedCollection = new ArrayList<ComparableObject>(map.values());
Collections.sort(sortedCollection);

(B)

Создайте экземпляр упорядоченногонапример, TreeSet, затем добавьте значения:

Set<ComparableObject> sortedCollection = new TreeSet<ComparableObject>(map.values());

Обратите внимание, что результирующая коллекция никогда не изменяется, поэтому сортировку необходимо выполнить только один раз.

Answer 1

TreeSet имеет log(n) гарантию временной сложности для add()/remove()/contains() методов. Сортировка ArrayList занимает n*log(n) операций, но add()/get() занимает только 1 операций.

Так что, если вы в основном извлекаете данные и редко сортируете, ArrayList - лучший выбор. Если вы сортируете часто, но не извлекаете столько, TreeSet будет лучшим выбором.

Answer 2

Теоретически сортировка в конце должна быть быстрее. Поддержание отсортированного состояния в процессе может потребовать дополнительного времени процессора.

С точки зрения CS, обе операции являются NlogN, но 1 сортировка должна иметь более низкую константу.

Answer 3

Почему бы не использовать лучшее из обоих миров?Если вы никогда не используете его снова, сортируйте с помощью TreeSet и инициализируйте ArrayList с содержимым

List<ComparableObject> sortedCollection = 
    new ArrayList<ComparableObject>( 
          new TreeSet<ComparableObject>(map.values()));

---

РЕДАКТИРОВАТЬ:

Я создал эталонный тест (вы можете получить к нему доступ в pastebin.com / 5pyPMJav ) для тестирования трех подходов (ArrayList + Collections.sort, TreeSet и мой лучший подход из обоих миров), и мой всегда побеждает.Тестовый файл создает карту с 10000 элементами, значения которых имеют преднамеренно ужасный компаратор, а затем каждая из трех стратегий получает возможность а) сортировать данные и б) выполнять итерацию по ним.Вот пример выходных данных (вы можете проверить это сами):

РЕДАКТИРОВАТЬ: я добавил аспект, который регистрирует вызовы в Thingy.compareTo (Thingy), и я также добавил новую стратегию, основанную на PriorityQueues, которая значительнобыстрее, чем любое из предыдущих решений (по крайней мере, в сортировке).

compareTo() calls:123490
Transformer ArrayListTransformer
    Creation: 255885873 ns (0.255885873 seconds) 
    Iteration: 2582591 ns (0.002582591 seconds) 
    Item count: 10000

compareTo() calls:121665
Transformer TreeSetTransformer
    Creation: 199893004 ns (0.199893004 seconds) 
    Iteration: 4848242 ns (0.004848242 seconds) 
    Item count: 10000

compareTo() calls:121665
Transformer BestOfBothWorldsTransformer
    Creation: 216952504 ns (0.216952504 seconds) 
    Iteration: 1604604 ns (0.001604604 seconds) 
    Item count: 10000

compareTo() calls:18819
Transformer PriorityQueueTransformer
    Creation: 35119198 ns (0.035119198 seconds) 
    Iteration: 2803639 ns (0.002803639 seconds) 
    Item count: 10000

Странно, но мой подход работает лучше всего в итерации (я бы подумал, что не будет различий с подходом ArrayList в итерации, яесть ошибка в моем тесте?)

Отказ от ответственности: я знаю, что это, вероятно, ужасный тест, но он помогает донести до вас точку, и я, конечно, не манипулировал этим, чтобы мой подход победил.

(код зависит от apache commons / lang для компоновщиков equals / hashcode / compareTo, но его легко реорганизовать)

Answer 4

Обязательно прочитайте мой комментарий о TreeSet внизу, если вы решите реализовать B)

Если ваше приложение выполняет только случайные сортировки, но многократно повторяет его, я бы сказал, что вам лучшеиспользуя простой несортированный список.Сортируйте его один раз, а затем воспользуйтесь более быстрой итерацией.Итерация особенно быстро выполняется в списке массивов.

Однако, если вы хотите, чтобы порядок сортировки гарантировался все время, или вы, возможно, часто добавляете / удаляете элементы, используйте отсортированную коллекцию и получите итерацию.

Так что в вашем случае я бы сказал, А) является лучшим вариантом.Список сортируется один раз, не изменяется и, следовательно, имеет преимущество быть массивом.Итерация должна быть очень быстрой, особенно если вы знаете это ArrayList и можете напрямую использовать ArrayList.get () вместо Iterator.

Я бы также добавил, что TreeSet по определениюНабор, который означает, что объекты являются уникальными.TreeSet определяет равенство, используя CompareTo на вашем Comparator / Comparable.Вы можете легко найти недостающие данные, если попытаетесь добавить два объекта, для которых CompareTo возвращает значение 0. Например, добавление «C», «A», «B», «A» в TreeSet вернет «A», «B»."," C "

Answer 5

Collections.sort использует mergeSort с O (nlog n).

TreeSet имеет красно-черное дерево, основные операции имеют O (logn).Следовательно, n элементов также имеет O (nlog n).

То есть оба алгоритма большого О.

Answer 6

Вставка в SortedSet - это O (log (n)) (НО! Текущий n, а не последний n).Вставка в список - 1.

Сортировка в SortedSet уже включена в вставку, поэтому она равна 0. Сортировка в списке - O (n * log (n)).

ИтакОбщая сложность SortedSet составляет O (n * k), k

Итак, SortedSet математически имеет лучшую производительность.Но, в конце концов, у вас есть Set вместо List (потому что SortedList не существует) и Set предоставляет вам меньше возможностей, чем List.Так что, на мой взгляд, лучшее решение для доступных функций и производительности - это то, что предложил Шон Патрик Флойд:

• использовать SortedSet для вставки,
• поместить SortedSet в качестве параметрасоздание списка для возврата.