Max Home IndustryБольшинство из нас полагает, что все алгоритмы сортировки отработаны. Не осталось ничего нового или интересного, чтобы найти или открыть для себя, но TimSort, используемый как в Python, так и в Java, родился в 2002 году и все еще исследуется.
Обязательный xkcd мультфильм.
Больше мультяшных забав на xkcd, веб-комиксе о романтике, сарказме, математике и языке
Если вы прошли почти любой курс информатики или просто прочитали книгу, то вы поймете, что проблема сортировки вещей по порядку настолько важна, что мы изучаем ее целую вечность. Вы, вероятно, также знаете, что важно то, насколько быстро выполняется сортировка по количеству вещей, которые нужно отсортировать. Самая популярная «теоретическая» сортировка — это быстрая сортировка, потому что она элегантна, сложна и сортирует n элементов во времени, пропорциональном nlogn, что обычно считается хорошим.
Конец истории?
Нет, потому что есть гораздо больше соображений, чем теоретическая производительность. Например, вы можете спросить, какова наихудшая производительность метода сортировки. Другими словами, каков самый медленный алгоритм сортировки, если вы злой и бросаете ему только правильные или, точнее, неправильные данные? В случае Quicksort ответ — O (n2), что в конце концов не так уж и хорошо. Проблемы часто возникают, когда представленный список почти отсортирован, и алгоритм должен избегать дополнительной работы, пытаясь отсортировать то, что уже отсортировано.
На практике алгоритмы сортировки должны были уметь избегать данных, которые подавляют их основной алгоритм, и переключаться на другой алгоритм, если данные им не подходят.
Здесь на сцену выходит TimSort. В 2002 году Тим Петерс разработал алгоритм сортировки для Python. Он был достаточно хорош для Java, чтобы использовать его с некоторыми отличиями чуть позже. Основа алгоритма заключается в том, что входная последовательность сначала сканируется и разлагается на монотонные прогоны, то есть увеличивающие или уменьшающие подпоследовательности. Затем эти последовательности объединяются в отсортированный список. Создателем основной идеи слияния естественных последовательностей, как и в компьютерных науках, является Дональд Кнут.
Это упрощает звучание TimSort, но также включает эвристику о том, что и когда делать, что затрудняет анализ. Короче говоря, это не элегантная логика чистого алгоритма, такого как Quicksort, а практически оптимизированная процедура сортировки с магическими числами и вариантами выбора. Настолько, что предполагалось, что его средняя сложность была O (nlogn) и более того, сложность его наихудшего случая также была O (nlogn). Николя Оже, Сирил Нико и Карин Пивото до 2015 года доказали, что это действительно так. Теперь у них есть новая статья, которая существенно упрощает доказательство и в процессе проливает новый свет на то, как работает алгоритм.
«Основываясь на этом описании, мы также смогли положительно ответить на естественный вопрос, который до сих пор оставался открытым: работает ли TimSort за O (n + n log ρ), где ρ — количество запусков? Мы надеемся, что наша теоретическая работа подчеркивает, что TimSort на самом деле является очень хорошим алгоритмом сортировки. Даже если все его точные эвристики удалены, динамика его слияний, вызванная небольшим количеством локальных правил, приводит к очень эффективному глобальному поведению, особенно хорошо подходит для почти отсортированные входы «.
Что немного больше беспокоит, так это то, что:
«Кроме того, мы хотим подчеркнуть необходимость тщательного анализа алгоритма, чтобы предотвратить ошибки и недоразумения. Как бы очевидно это ни звучало, три последовательные ошибки в высоте стека в Java прекрасно иллюстрируют, как лучшие идеи могут быть испорчены отсутствие надлежащего анализа сложности «.
Да, они обнаружили ошибки в Java-реализации TimSort.
Сортировка по-прежнему важна, и многое еще предстоит сделать. Нам нужно выйти за рамки теоретических алгоритмов, реализованных на теоретических машинах, и посмотреть, что происходит на реальных машинах с такими сложностями, как кэширование и выполнение вне очереди.
Сейчас по-прежнему хорошее время, чтобы стать ученым-компьютерщиком, если не лучшим.