Comments 32
Я болел за Timsort.
Жаль, что mergesort не вошёл в сравнение, а аспект распараллеливания не был затронут.
Всё равно бы тимсорт победил — его суть в сортировке частей, а значит распараллеливание ему только на руку.
Да, из рассмотренных алгоритмов только timsort хоть как-то использует подход «разделяй и властвуй»
Почему же, quicksort параллелится очень просто. Каждая итерация делит массив на две части, знай только да создавай новые треды на них. Только самая долгая, самая первая итерация не параллелится.
Тоже хотелось бы посмотреть результаты в параллельной обработке. И конечный результат и прирост от параллелизма. На 4х-ядернике желательно, или более.
Тоже хотелось бы посмотреть результаты в параллельной обработке. И конечный результат и прирост от параллелизма. На 4х-ядернике желательно, или более.
Это зависит от того, какой процент общего времени занимает слияние массивов. Этот этап тяжело распараллелить.
Из классических алгоритмов выбор пал только на heapsort и quicksort из-за того, что первый идейно близок к smoothsort, а второй является самым быстрым из них. Подозреваю, что «чистый» mergesort находился бы где-то в районе shellsort — heapsort на графиках, хотя точно сказать не могу, не проверял. А распараллеливание — это уже отдельная большая тема для рассмотрения, честно, даже не подумал об этом)
Как насчёт старой-доброй поразрядной сортировки? O(n) при ограниченном диапазоне значений (что на практике всегда выполняется). Было бы интересно погонять его вместе с прочими.
И все таки, сортировка Хоара остается одной из лучших. Хотя Timsort, конечно, выглядит великолепно. Хотел спросить: а распараллеливать алгоритмы не пытались? После этого картина станет немного другой.
Жаль, что на случайных данных Timsort уступает ~30% quicksort'у. Не будь этого, брал бы, не задумываясь.
Еще интересно было бы сравнить алгоритмы неполного упорядочивания данных для поиска медианы (сам таким анализом полностью не занимался: просто сразу взял готовые алгоритмы из Numerical Recipies. Но интересно: вдруг что побыстрей есть).
> Было сгенерировано 10 наборов по 10^8 случайных натуральных чисел, для каждого алгоритма было замерено среднее время работы.
вопрос к автору: не сликом ли маленькая статистика? вроде для получение более или менее адекватных средних нужно прогонять каждый тест раз по 10^4 — 10^5. Или большая размерность входных данных позволяет делать нормальные выводы?
просто если мало прогонов, то в это время мог какой-нибудь бекграунд-таск операционки затесаться, например, — и время выполнения для какого-то алгоритма сильно ухудшится. я не прав?
вопрос к автору: не сликом ли маленькая статистика? вроде для получение более или менее адекватных средних нужно прогонять каждый тест раз по 10^4 — 10^5. Или большая размерность входных данных позволяет делать нормальные выводы?
просто если мало прогонов, то в это время мог какой-нибудь бекграунд-таск операционки затесаться, например, — и время выполнения для какого-то алгоритма сильно ухудшится. я не прав?
Статистика конечно не огромная, но в моем понимании для получения общей картины вполне достаточная. Как я уже писал, на каждом тестовом наборе все алгоритмы запускались по три раза, и выбиралось минимальное время из этих запусков. Собственно так я пытался избавиться от всяких непредусмотренных нагрузок. Плюс все это дело запускалось на ночь, систему я сам дополнительно никак не грузил.
Если бы была возможность, тестировал бы больше, но, к сожалению, чтобы прогнать все представленные тесты и так потребовалось несколько часов.
И вдобавок, на каждом наборе тестовых данных все алгоритмы запускались по очереди, так что долговременные бекграунды не должны были избирательно повлиять на некоторые алгоритмы)
Если бы была возможность, тестировал бы больше, но, к сожалению, чтобы прогнать все представленные тесты и так потребовалось несколько часов.
И вдобавок, на каждом наборе тестовых данных все алгоритмы запускались по очереди, так что долговременные бекграунды не должны были избирательно повлиять на некоторые алгоритмы)
ок, я понял, спасибо)
> И вдобавок, на каждом наборе тестовых данных все алгоритмы запускались по очереди
тут дело больше не в программах, а в окружении. мы не можем запустить тестирование в вакууме, а запускаем исполнение программы в некоторой операционной среде, которая вносит свои помехи в наблюдаемую производительность. (ну, например (сферический пример в вакууме), приспичило операционке во время выполнения теста оптимизировать файловую систему)) ) Поэтому для отсечения таких помех делают много прогонов и усредняют полученное время.
> Если бы была возможность, тестировал бы больше, но, к сожалению, чтобы прогнать все представленные тесты и так потребовалось несколько часов.
несколько часов — это еще хорошо, что не несколько дней
эх, вспоминаю, как мы тестировали МВГ. вот тут понимаешь, как ничтожны все эти мегагерцы и ядра в процессоре ))
> И вдобавок, на каждом наборе тестовых данных все алгоритмы запускались по очереди
тут дело больше не в программах, а в окружении. мы не можем запустить тестирование в вакууме, а запускаем исполнение программы в некоторой операционной среде, которая вносит свои помехи в наблюдаемую производительность. (ну, например (сферический пример в вакууме), приспичило операционке во время выполнения теста оптимизировать файловую систему)) ) Поэтому для отсечения таких помех делают много прогонов и усредняют полученное время.
> Если бы была возможность, тестировал бы больше, но, к сожалению, чтобы прогнать все представленные тесты и так потребовалось несколько часов.
несколько часов — это еще хорошо, что не несколько дней
эх, вспоминаю, как мы тестировали МВГ. вот тут понимаешь, как ничтожны все эти мегагерцы и ядра в процессоре ))
Ну в свою защиту еще могу сказать, что пока все это дело писалось, все алгоритмы запускались большое количество раз, и результаты на ненагруженной системе всегда были почти одинаковыми)
> несколько часов — это еще хорошо, что не несколько дней
Был бы второй комп, можно было бы и больше тестировать) А так, самый большой промежуток что я могу не трогать систему — это время сна)
> несколько часов — это еще хорошо, что не несколько дней
Был бы второй комп, можно было бы и больше тестировать) А так, самый большой промежуток что я могу не трогать систему — это время сна)
Посмотрев на графики я бы выбрал Quick. Даже не знаю почему абсолютным лидером стал Tim :)
Лидером из трех алгоритмов, которые работают за O(n) при упорядоченных данных)
потому что в отличие от быстрой сортировки, TimSort стабилен.
Ну судя по графикам быстрая супер стабильна, стабильнее чем Tim, и очевидно быстра. :)
Посмотрите лучше на определение стабильной (или устойчивой) сортировки.
Первая диаграма меня несколько сконфузила. Называется она «Средняя скорость...», поэтому ожидаешь, что чем выше столбик, тем круче. А нет, на вертикальной оси оказывается отложено затраченное время. Было бы неплохо поправить несоответствие названия и данных.
Ещё есть Dual-Pivot Quicksort.
вопрос такой — я правильно понял, 100млн рандомных интов quicksort сортирует за 35 секунд?
Возможно я что то не понял, но почему на графиках на позициях где количество элементов массива равно 10^1 10^2 скорость сортировки 13 сек. и выше? Почему так много?
А все понятно, просто невнимательно прочитал
Sign up to leave a comment.
И снова про сортировки: выбираем лучший алгоритм