Java - Collections.sort () производительность
Я использую Collections.sort () для сортировки LinkedList, элементы которого реализует интерфейс Comparable, таким образом, они отсортированы в естественном порядке. В документации Javadoc ее сказанный этот метод использует алгоритм сортировки с объединением, который имеет n*log (n) производительность.
Мой вопрос состоит в том, если существует более эффективный алгоритм для сортировки моего LinkedList?
Размер того списка мог быть очень высоким, и вид будет также очень частым.
Спасибо!
4 ответа
O (N log N) очень хорошо асимптотически. Тем не менее, существует линейное время O (N) сортировка, не основанная на сравнении, например счетная сортировка и ковшовая сортировка. Это полезно, например, когда вы сортируете миллионы и миллионы целых чисел, но они находятся в диапазоне от 1 до 10.
Кроме того, если список «почти отсортирован», то в некоторых случаях считается, что сортировка с квадратичной вставкой на самом деле лучше.
Применимо ли это или даже стоит ли применять, зависит от результатов вашего профилирования. Я бы сказал, что не беспокойтесь об этом, если только он не покажет, что сорт является узким местом.
См. Также
Связанные вопросы
Что касается сортировки списка, нет, все сортировки на основе сравнения по общим данным равны O (N log (N)).
Если вы прибегаете к вставке из-за вставок, вы можете попробовать группировать вставки, а затем объединить сортировку с основным списком - если у вас есть B новых элементов, вы сортируете их в O (журнал B (B)), затем выполните одноуровневое слияние двух списков, которое составляет O (N + B).
Если обращение происходит из-за изменений в значениях элементов, вы можете выполнить аналогичную пакетную обработку, если измените изменяемые значения на неизменяемые и обработайте изменения как пакет вставок и удалений. В противном случае вам не избежать сортировки всего списка.
Если ваши требования позволяют это, тогда доступны различные структуры несвязанного списка, такие как TreeSet, которые поддерживают отсортированный порядок более эффективно, но не работают, если значения изменяются.
Если вы говорите, что список будет сортироваться "очень часто", вам следует подумать о том, чтобы все время держать список в отсортированном виде, например, использовать дерево вместо LinkedList. Возможно вы даже можете использовать какой-нибудь SortedSet вместо List, если у вас нет дублирующихся значений и вам не нужны операции со списком (поскольку вы все равно все время сортируете их). Проверьте класс TreeSet реализации SortedSet.
Эта реализация обеспечивает гарантированные затраты времени log(n) для основных операций (add, remove и contains).
Если вы хотите выполнить итерацию по этому "списку" (который на самом деле является множеством), вы можете использовать итератор класса.
Возвращает итератор по элементам этого множества в порядке возрастания.
Если у вас есть дублирующиеся значения внутри списка, вам придется использовать некоторые трюки (например, поместить значение в новый класс, который также получил некоторую дельту для сортировки одинаковых объектов)
Не существует алгоритма общей сортировки лучше, чем n*log(n). И это довольно быстро. Под общим я подразумеваю, что ваши данные не обладают особыми свойствами.