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

Если у меня Mapтакой:

HashMap<Integer, ComparableObject> map;

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

(А)

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

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

(В)

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

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

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

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

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

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

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

Почему бы не использовать лучшее из обоих миров? Если вы больше никогда не будете его использовать, отсортируйте с помощью 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, но его должно быть легко реорганизовать)

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

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

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

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

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

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

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

Таким образом, оба являются одним и тем же алгоритмом большого О.

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

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

Таким образом, общая сложность SortedSet составляет O (n * k), k <log (n) для всех случаев, кроме последнего. Вместо этого общая сложность списка равна O (n * log (n) + n), поэтому O (n * log (n)).

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

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

Отличный вопрос и отличные ответы. Просто подумал, что я бы добавил несколько моментов, которые нужно учесть:

1. Если ваша коллекция для сортировки недолговечна, например, используется в качестве аргумента метода, и вам нужен список, отсортированный внутри метода, используйте Collections.sort (collection). Или если это долгоживущий объект, но сортировать его нужно очень редко.

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

сортировать -> использовать -> забыть

Если вы добавите новый элемент в отсортированную коллекцию, вам придется снова отсортировать коллекцию, поскольку порядок при вставке нового элемента не гарантируется.

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

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

вставить / удалить -> использовать (всегда есть гарантия, что коллекция отсортирована)

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

Обратной стороной использования TreeSet являются ресурсы, необходимые для хранения отсортированной коллекции. Он использует красно-черное дерево и требует затрат времени O (log n) для операций get, put.

Если вы используете простую коллекцию, такую ​​как ArrayList, операции get, add имеют постоянное время O (1).