Java - производительность Collections.sort ()

Question

Я использую Collections.sort () для сортировки LinkedList, элементы которого реализуют интерфейс Comparable, поэтому они сортируются в естественном порядке. В документации javadoc сказано, что этот метод использует алгоритм mergesort , который имеет производительность n * log (n).

У меня вопрос: есть ли более эффективный алгоритм сортировки моего LinkedList?

Размер этого списка может быть очень большим, и сортировка также будет очень частой.

Спасибо!

Answer 1

O(N log N) очень хорошо асимптотически.Тем не менее, есть линейное время O(N) сортировка, не основанная на сравнении, например, сортировка по счетам и сортировка по сегментам.Это полезно, например, когда вы сортируете миллионы и миллионы целых чисел, но они находятся между 1..10.

Кроме того, если список «почти отсортирован», сообщается о квадратичной сортировке вставки.чтобы быть действительно лучше в некоторых сценариях.

Будет ли это применимо или даже целесообразно реализовать, зависит от ваших результатов профилирования.Я бы сказал, что, если это не показывает, что сортировка является узким местом, не беспокойтесь об этом.

См. Также

• Википедия / Подсчет сортировки
• Wikipedia / Bucket sort

Смежные вопросы

• Существует ли O (n) алгоритм целочисленной сортировки?

Answer 2

Если вы говорите, что список будет отсортирован «очень часто», вам следует рассмотреть возможность постоянного хранения списка в отсортированном виде, например, использовать дерево вместо LinkedList. Может быть, , вы даже можете использовать SortedSet вместо List, если у вас нет дублированных значений и вам не нужны никакие операции со списком (так как вы все равно их сортируете) , Проверьте класс TreeSet реализации SortedSet.

Эта реализация обеспечивает гарантированную стоимость журнала (n) для основных операций (добавление, удаление и содержание).

Если вы хотите перебрать этот «список» (который на самом деле является множеством), вы можете использовать итератор класса.

Возвращает итератор для элементов этого набора в порядке возрастания.

Если у вас есть повторяющиеся значения внутри Списка, вы должны использовать некоторые приемы (например, поместить значение в новый класс, который также получил некоторую дельту для сортировки равных объектов)

Answer 3

Я экспериментирую с большими наборами данных (ГБ данных) и внедрил сортировку слиянием (есть хороший пример @ googlecode). Тем не менее, я использую Collection.sort () для предварительной сортировки моих временных буферов, и в моем опыте Collection.sort () смехотворно медленно работает при определенном пороге данных. Со вспомогательным буфером в 96 МБ я могу отсортировать один из этих буферов примерно за 30 секунд (примечание: это сильно зависит от используемых компараторов - я использую настраиваемый макет столбца с довольно сложным анализатором столбцов), однако увеличив его до размера фрагмента 128 МБ время превышает 3 минуты. Это никак не связано с линейным (или почти линейным) поведением, которое я могу наблюдать для небольших кусков. Это имеет такое большое влияние, что сортировка слиянием с меньшими буферами почти (?) Во всех случаях быстрее, чем сортировка в памяти с использованием буфера 128 МБ. Для краткости: сортировка слиянием - это путь для больших наборов данных за пределами 100 МБ. Я не могу ответить, почему это так, и эти цифры могут даже зависеть от машины (у меня OS-X на 2,6 ГГц i7 и 16 ГБ памяти).

Answer 4

Нет общего алгоритма сортировки лучше, чем n*log(n). И это довольно быстро. Я имею в виду, что ваши данные не имеют специальных свойств.

Answer 5

С точки зрения сортировки списка, нет, все сортировки на основе сравнения на общих данных - O (N log (N)).

Если вы прибегаете к помощи из-за вставок, то вы можете попробовать пакетно вставить свои вставки и затем объединить сортировку с основным списком - если у вас есть B новых элементов, вы сортируете их в O (B log (B)), а затем выполните одноуровневое слияние двух списков, которое O (N + B).

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

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