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

Если у меня есть Map, как это:

HashMap<Integer, ComparableObject> map;

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

(А)

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

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

(B)

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

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

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

Ответ 1

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

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

Ответ 2

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

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

Ответ 3

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

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

EDIT:

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

EDIT: я добавил аспект, который регистрирует вызовы 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, но его легко реорганизовать)

Ответ 4

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

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

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

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

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

Ответ 5

Collections.sort использует mergeSort, который имеет O (nlog n).

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

Таким образом, оба метода одинакового большого O.