Comments 55
Есть такая репа с сортировками: github.com/Morwenn/cpp-sort
Также стоило бы упомянуть такие сортировки как Boost.Sort и pdqsort, которая используется в Rust: они являются очень быстрыми.
А за бенчмарк спасибо — будет полезная ссылка.
Также стоило бы упомянуть такие сортировки как Boost.Sort и pdqsort, которая используется в Rust: они являются очень быстрыми.
А за бенчмарк спасибо — будет полезная ссылка.
Неплохая идея с https://github.com/Morwenn/cpp-sort/wiki/Fixed-size-sorters!
Методика и инструментарий у всех хромает на две ноги.
Почему производилось по 20 запусков на тест?
Что за системные глюки наблюдались?
Как измерялось время?
Имеет ли смысл сделать то же самое под Linux?
Что за системные глюки наблюдались?
Как измерялось время?
Имеет ли смысл сделать то же самое под Linux?
Нужно было сделать столько запусков, чтобы это не заняло слишком много времени, и при этом давало достаточно надежные результаты. 20 — вполне подходящее число.
Пару раз за время тестирования система зависала на несколько минут, почему — не знаю.
Время измерялось встроенной в C++ функцией clock(), можете посмотреть в реализации.
Насчет Linux'а не знаю, у меня его нет.
Пару раз за время тестирования система зависала на несколько минут, почему — не знаю.
Время измерялось встроенной в C++ функцией clock(), можете посмотреть в реализации.
Насчет Linux'а не знаю, у меня его нет.
Представим каждое число в двоичном видеА если в массиве не числа? Предлагаю изменить заголовок.
O-нотация верхний предел его настоящей сложности
для точного и наилучшего используются другие обозначения Θ и Ω(ω)
см Введение в анализ сложности алгоритмов на хабре
для точного и наилучшего используются другие обозначения Θ и Ω(ω)
см Введение в анализ сложности алгоритмов на хабре
Сейджвик как-то в курсе по алгоритмам говорил, что на производительность сильно влияет как хорошо алгоритмы работают с кэшами процессора. Например merge sort хорошо с ними работает, а heap sort наоборот. Поэтому даже с учетом того что merge sort требует больше памяти его предпочитают heap sort.
Heapsort на C++ пишется в 2 строчки:
Heapsort требует O(1) дополнительной памяти.
std::make_heap(l, r);
std::sort_heap(l, r);Heapsort требует O(1) дополнительной памяти.
Да, но это работает гораздо медленнее приведенной реализации.
На самом деле мой вариант даже быстрее из-за линейного времени построения кучи.
pastebin.com/BRRHx0pd
pastebin.com/BRRHx0pd
Странно, если я у Вас это работает быстрее, на моем компьютере все наоборот.
ideone.com/BRV0KK — Heapsort 1e7 случайных элементов [0, 2^30)
Ваш вариант — 2.29, STL-вариант — 2.08
Надеюсь, Вы выбрали конфигурацию Release x64 в MSVC.
Ваш вариант — 2.29, STL-вариант — 2.08
Надеюсь, Вы выбрали конфигурацию Release x64 в MSVC.
Да, практически такой же код (только с заменой заголовочных файлов), работает с release x64 со временем примерно 2.2 и 3.1.
Если добавить в кучу конструктор heap(): h(20000000) { }, то результаты будут такими: 0.108042 — heap, 2.00452 — stl.
ideone.com/FdmsOw
ideone.com/FdmsOw
Оратор выше все правильно говорит. Вы строите кучу не за линейное время, и поэтому сложность вашей сортировки больше, чем O(N*logN).
Рекомендую почитать про двоичную кучу тут: neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%B0%D1%8F_%D0%BA%D1%83%D1%87%D0%B0
В особенности раздел Построение кучи за O(n)
Рекомендую почитать про двоичную кучу тут: neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%B0%D1%8F_%D0%BA%D1%83%D1%87%D0%B0
В особенности раздел Построение кучи за O(n)
Построение кучи в сабже за Θ(N*log(N)), поэтому сложность сортировки такая же.
Нет, потому что извлечение из кучи идет не за линейное время. Извлечение из кучи — это замена верхнего элемента нижним, и просеивание его вниз.
Хотя я тут подумал, да. Сложность конечно логарифмическая. Просто в вашем случае это: O(N*logN + N*logN), а в случае построении кучи за линейное время это O(N*logN + N), т.е. все равно быстрее, о чем изначально и говорилось.
Быстрее и асимптотически быстрее — это разные вещи. Учите матчасть: O нотация.
Про асимптотику я как раз это и написал. Странно видеть в статье построение кучи не через heapify, а наивное. В статье, которая претендует на бенчмарк сортировок.
Спасибо, что обратили внимание на мой недочет. Хотя ничего «странного» я здесь не вижу, просто не знал о существовании такого алгоритма построения. Бесспорно, нужно было перед тем, как решить, что реализация достаточно хороша, прочитать еще раз статью. Но сложно учесть все. А кучей пользуюсь редко (чтоб не сказать никогда), ее вполне заменяет дерево поиска.
Занятно, но ощущение противоречивое…
Во-первых, мне кажется, для одной статьи это слишком большое число алгоритмов. Было бы лучше сгруппировать их в 2-3 группы. Например, по устойчивости (сохранении порядка элементов с одинаковым значением ключа) или по другому критерию.
Во-вторых, не хватает сводной таблички, в которой бы указывались такие характеристики:
1. Устойчивость — сохраняется ли порядок элементов с одинаковыми значениями ключей.
2. Естественность — сортируется ли уже упорядоченный массив быстрее, чем случайный, а случайный быстрее, чем упорядоченный в обратном порядке.
3. Производительность в лучшем, среднем, худшем случаях.
4. Требования к дополнительной памяти (и ее порядок).
5. Области применения (например, для сортировок малых почти упорядоченных массивов и др.).
И еще… Могу, конечно, путать, но, как мне кажется, сортировка слиянием существует в двух вариантах — с дополнительной памятью размера O(n) и без дополнительной памяти — т.е. размера O(1).
И производительность этих сортировок весьма различается.
Во-первых, мне кажется, для одной статьи это слишком большое число алгоритмов. Было бы лучше сгруппировать их в 2-3 группы. Например, по устойчивости (сохранении порядка элементов с одинаковым значением ключа) или по другому критерию.
Во-вторых, не хватает сводной таблички, в которой бы указывались такие характеристики:
1. Устойчивость — сохраняется ли порядок элементов с одинаковыми значениями ключей.
2. Естественность — сортируется ли уже упорядоченный массив быстрее, чем случайный, а случайный быстрее, чем упорядоченный в обратном порядке.
3. Производительность в лучшем, среднем, худшем случаях.
4. Требования к дополнительной памяти (и ее порядок).
5. Области применения (например, для сортировок малых почти упорядоченных массивов и др.).
И еще… Могу, конечно, путать, но, как мне кажется, сортировка слиянием существует в двух вариантах — с дополнительной памятью размера O(n) и без дополнительной памяти — т.е. размера O(1).
И производительность этих сортировок весьма различается.
Кстати, существует ли устойчивая сортировка с временем работы O(n*log(n)) и дополнительной памятью O(1) в наихудшем случае? По-моему где-то я её встречал, но не помню где.
Неужели такое бывает? Я думал, что все устойчивые имеют временную сложность O(n^2)…
Круто :) Но я ничего не понял :D
У этого алгоритма известны 2 практические реализации:
GrailSort (на гитхабе) покойного Mrrl
- WikiSort
Оба этих алгоритма включены в cpp-sort
Почему n^2? Если даже взять наивную реализацию, то можно добавить каждому элементу второй ключ по его порядковому номеру в изначальном массиве [O(n)], а затем отсортировать по двум ключам — выходит O(2*n*log(n) + n) = O(n*log(n)). Merge Sort тоже стабильный.
Доп. память O(n), а надо O(1).
Это несколько неудачный пример.
Что имеется в виду под «затем отсортировать по двум ключам»? Выполнить сортировку в два этапа?
Если делать второй этап только по втолрому ключу, то получим неотсортированный исходный массив.
Если делать второй этап по составному ключу, то смысла в нем нет — можно сразу первым этапом отсортировать по этому составному ключу. Тогда, действительно, получим сохранившийся порядок элементов с одинаковыми первыми ключами.
Только вот к устойчивости алгоритма это не будет иметь абсолютно никакого отношения. Тому как составной ключ будет уникальным. А устойчивость проявляется именно для массивов данных с неуникальными ключами. Причем, проявляется как естественная характеристика алгоритма, не требующая дополнительных телодвижений в виде введения вторичных/составных ключей или сортировки в несколько этапов по этим искусственно введенным ключам.
Что имеется в виду под «затем отсортировать по двум ключам»? Выполнить сортировку в два этапа?
Если делать второй этап только по втолрому ключу, то получим неотсортированный исходный массив.
Если делать второй этап по составному ключу, то смысла в нем нет — можно сразу первым этапом отсортировать по этому составному ключу. Тогда, действительно, получим сохранившийся порядок элементов с одинаковыми первыми ключами.
Только вот к устойчивости алгоритма это не будет иметь абсолютно никакого отношения. Тому как составной ключ будет уникальным. А устойчивость проявляется именно для массивов данных с неуникальными ключами. Причем, проявляется как естественная характеристика алгоритма, не требующая дополнительных телодвижений в виде введения вторичных/составных ключей или сортировки в несколько этапов по этим искусственно введенным ключам.
Алгоритмы и так были сгруппированы, по скорости. Эта характеристика в рамках данной статьи более важна, чем, например, устойчивость, ведь цель определить именно скорости всех сортировок. С помощью этих результатов можно определить и лучшую среди устойчивых. Общая таблица — неплохая идея, наверное, я ее сделаю и выложу позже. Сортировка слиянием без дополнительной памяти есть (статья), но она вроде довольно сложная и не очень известная. Не могу я же я написать все известные человечеству алгоритмы )
Нет, я имел в виду не этот алгоритм. Я читал про него когда то бурное обсуждение. И понял, что его эффективность несколько преувеличена. Во всяком случае, не стоит всех тех сложностей реализации.
Я имел в виду алгоритм Пратта слияния двух предварительно отсортированных частей массива «на месте»: ru.wikipedia.org/wiki/Устойчивая_сортировка
Я имел в виду алгоритм Пратта слияния двух предварительно отсортированных частей массива «на месте»: ru.wikipedia.org/wiki/Устойчивая_сортировка
А что нового внесла статья по сравнению с книгой Д.Кнута?
Ну, кажется у Кнута многих приведенных алгоритмов нет. Может быть в каких-то последних изданиях — исправленных и дополненных, разве что.
Верно, правда, с точностью до наоборот: вы хоть на фото этих кирпичей взгляните :) там есть все сортировки во всех возможных модификациях, доступных человеческому разуму, возможно, актуальные до момента тепловой смерти нашей Вселенной :)
Третий «кирпич» Кнута, посвященный сортировкам и поиску, был издан в 1973 году. Алгоритм сортировки «расческой» был опубликован в 1980 году, а алгоритм TimSort — 2002 году.
Так что, сведения о том, что там перечислены «все сортировки во всех возможных модификациях, доступных человеческому разуму, возможно, актуальные до момента тепловой смерти нашей Вселенной» несколько преувеличены :)
Так что, сведения о том, что там перечислены «все сортировки во всех возможных модификациях, доступных человеческому разуму, возможно, актуальные до момента тепловой смерти нашей Вселенной» несколько преувеличены :)
А что, если в том кирпиче ближе к концу эти алгоритмы уже были, но без модных названий. И ведь что характерно: людей, способных подтвердить или опровергнуть это, все равно уже не сыскать вот написал эту глупость и полез проверять. Жив-здоров дядюшка Дональд и прекрасно себя чувствует.
Обратился к первоисточнику. Среди обменных сортировок у Кнута рассмотрена пузырьковая с модификациями (шейкерная в т.ч.), параллельная Бэтчера, быстрая с разделением Хоара (QuickSort) и поразрядная обменная.
Сортировки расческой там нет. Хотя идея ее проста и просто сама напрашивается. Сам писал программы по похожему алгоритму лет 30 назад, но не такие эффективные, потому что набор дистанций брал каким угодно (числа Фиббоначи, степени двойки — 1, последовательные простые числа и т.д.), а про снижающий коэффициент 1,247331… только сейчас прочитал.
А ведь в этом коэффициенте как раз весь смысл этого алгоритма.
Сортировки расческой там нет. Хотя идея ее проста и просто сама напрашивается. Сам писал программы по похожему алгоритму лет 30 назад, но не такие эффективные, потому что набор дистанций брал каким угодно (числа Фиббоначи, степени двойки — 1, последовательные простые числа и т.д.), а про снижающий коэффициент 1,247331… только сейчас прочитал.
А ведь в этом коэффициенте как раз весь смысл этого алгоритма.
Интересно и хорошо сконцентрировано…
Мне к примеру, надо быстро сортировать 20и битовые данные и их 100 000 000.
Я раньше считал, что самый подходящий способ делёж файла на 30 частей и — Merge Sort.
Сейчас вижу есть другие варианты…
Ну а всё же — что наиболее подходит?
Мне к примеру, надо быстро сортировать 20и битовые данные и их 100 000 000.
Я раньше считал, что самый подходящий способ делёж файла на 30 частей и — Merge Sort.
Сейчас вижу есть другие варианты…
Ну а всё же — что наиболее подходит?
открываете репозиторий cpp-sort, запускаете на Вашем кейсе и смотрите, что показывает себя лучше. Тем и пользуйтесь :-)
Самый быстрый в таком случае вариант — cортировка подсчётом. При линейной сложности потребует 2^20 * 4 байт памяти на счетчики в Вашем случае.
А сортировки n*ln(ln(n)) почему не подставлены?
Для пузырька и шейкера легко пишется модификация с запоминанием места последнего обмена. Очевидно, что дальше предыдущей позиции от запомненной ходить при просмотре нет смысла — фрагмент уже отсортирован.
Спасибо, что включили в сравнение std::sort, хотя найти его сразу непросто.
СУБД умеют собирать статистику, но у них, насколько я в курсе, ограниченный набор алгоритмов, и это не сортировка, а хранение: хеш/дерево/битмап…
UFO just landed and posted this here
Устаревшая основа статьи.
Академические источники какие?
https://github.com/scandum/quadsort
https://github.com/PatwinchIR/ultra-sort
На днях смог таки свою сортировку реализовать, за пару дней сделал на ассемблере. Работает со строками, именно под строки заточена, как называется точно по научному, не могу назвать, но типа поразрядная, ну по байтам. Работает быстро, файл leipzig1M.txt весом 123 МБ и 1000000 строк, от сортировала за ~0.8 сек. Трудно с чём то сравнить, но это довольно быстро, быстрей быстрой сортировки должно быть, но пока соревнований не делал. Алгоритм придумал очень давно, когда у меня и компьютера то не было. Алгоритм конечно довольно простой, да у всех простой, сотня кода максимум. А, ПК Ryzen 5 3600X 3.79 GHz достаточно быстрый, но не самый.
Судя по размеру файла, его сортировка производится полностью в памяти.
А как быть, если в память он не помещается и приходится сортировать по частям, а потом их сливать? В этом случае кроме быстрой сортировки в памяти хотелось бы иметь оптимизацию операций с файлами. Хотя бы уменьшение числа операций чтений/записи.
Передаю привет Картановой А.Д.
Sign up to leave a comment.
Описание алгоритмов сортировки и сравнение их производительности