четверг, 15 октября 2009 г.

Сортировки и сборки...

В http://www.reddit.com/r/programming/comments/9jj5z/vladimir_yaroslavskiys_dualpivot_quicksort/ прочитал об улучшении классического quicksort'а при помощи добавления второго опорного элемента. Автор показывает, что для худшего случая время работы получается на 20% лучше, чем у стандартной реализации.

Меня это заинтересовало. Да и захотелось сравнить с другими сортировками, а то использую в рабочем коде только обощённый метод из стандартной библиотеки C++, а в быстрых поделках на колене - шеловскую сортировку (настолько к этому сочетанию уже привык, что кажется - подними с кровати, напишу использование на полном автомате, не просыпаясь).

Для сравнения были выбраны следующие сортировки: реализация quicksort'а в лоб без каких-либо улучшений, реализация quicksort'а с использованием сортировки вставкой на малых массивах, dual pivot quicksort, sort из стандартной библиотеки C++ (чтобы был наглядней результат), quicksort из C runtime(насколько я понимаю, тут используется реализация из стандартной библиотеки C) и сортировка Шела с шагами 2^n -1.

Измерения проводились на векторе в 5 миллионов int'ов. Использование обощенного контейнера было основано на необходимости использовать в сравнении обобщённый sort из стандартной библиотеки C++. Среди контейнеров же был выбран вектор, т.к. хотелось посмотреть на результат qsort из C Runtime Library.

Измерения выполнялись в MS VC++2005.

Результаты получились, мягко говоря, странными.

Дебаг сборка показала следующее:

Debug.png
Время приведено в миллисекундах.
Быстрее всех qsort из C Runtime Library - я так понимаю, это достигается за счёт того, что количество различных проверок в коде минимально, и функция при перемещении элементов полагается на то, что оные расположены в памяти подряд (для чего и выбирался вектор). Сортировка с двойным опорным элементом быстрее, чем простейшие реализации quicksort'а (с оптимизацией и без неё). Сортировка Шелла выступила ожидаемо - всё таки 5 миллионов элементов, это не то количество, на которых элементарные сортировки будут вести себя эффективно. Но вот провал обобщённого sort'а из стандартной библиотеки C++ был оглушителен - полуторный проигрыш реализации сортировки Шелла и 30-икратный qsort'у C Runtime Library ... Да, можно было ожидать, что обобщённый sort будет медленней чем qsort, всё таки куча проверок, код обобщенный для использования всеми контейнерами и никак не используется тот факт, что элементы идут подряд. Но не проигрыш ни в каком случае не должен был быть таким большим!

А вот результаты для релизной сборки:

release.png

Самописные сортировки выступили ожидаемо (соотношение их по времени выполнения изменилось слабо). А вот о том, как комментировать ситуацию с qsort из C Runtime Library и sort из стандартной библиотеки C++, - даже идей нет. Разве что, упомянуть уже появлявшиеся ранее в сети претензии к Microsoft'у, что они концентрируются на C++, а не на C, что проявляется даже в том, что стандарт С99 до сих пор не полностью реализован их компилятором. Это может хоть как-то объяснить и самый большой относительный прирост эффективности работы sort из стандартной библиотеки C++(почти в 400 раз), и самый малый относительный прирост (меньше чем в 6 раз) эффективности qsort из C Runtime Library.

Урок 1:

Мерять надо в рабочих условиях! Данные и поведение в Debug - не показатель!

Урок 2:

Иногда стоит самому реализовывать алгоритм, особенно, если он лучше, чем использованный в стандартной реализации.(Dual pivot quick sort и qsort из C Runtime Library).

P.S.

на закуску - время тех же сортировок на векторах в 1, 2, 3, 4 и 5 миллионов int.

steps.png

Итого: sort из стандартной библиотеки C++ качественней всех растёт при росте числа элементов в сортируемом массиве. Так что можно продолжать его использовать со спокойной душой.

7 комментариев:

  1. Чтобы тягаться с std::sort нужна ещё одна оптимизация - когда размер сортируемого становится достаточно маленьким (т.е. порядка десятка элементов) - сортировать его не quick-sort-ом а банальным insertion sort-ом. По крайней мере, std::sort делает именно так. Да, а quick sort будет проигрывать std::sort-у всегда за счёт того что он не может заинлайнить функцию сравнения.

    ОтветитьУдалить
  2. 2Left:
    Пара вопросов:
    1) а вы реализацию быстрой сортировки с 2-я опорными элементами по ссылке смотрели? В реализации Ярославского есть все перечисленные Вами улучшения, и есть даже несколько не упомянутых Вами связанных с минимизацией количества сравнений и минимизацией расхода памяти. Надо понять в чём причина выигрыша...
    2) в последнем предложении под "quick sort" Вы какую реализацию понимаете ? Судя по контексту из C Runtime Library, но не уверен.

    2All:
    не встречал ли кто исследования эффективности для какого размера следует начинать применять сортировку вставкой при оптимизации быстрой сортировки?

    А вообще хотелось бы ещё понять: почему std::sort повёл себя так безобразно в отладочной сборке?

    ОтветитьУдалить
  3. Не-а, реализацию так чтобы подробно не смотрел. Как-нить на досуге гляну, может будут какие-то идеи.

    Под quick sort я понимал qsort из старого доброго C, прошу прощения что туманно выразился.

    А на отладочную сборку смотреть вообще не стОит. В числе прочих проверок она ещё и делает проверку корректности реализации предиката - т.е. если к примеру предикат не удовлятворяет требованиям (к примеру возвращает true и для (a,b) и для (b,a) то отладочная версия ругнётся ассертом. Т.е. как минимум число проверок вдвое больше чем реально нужно.

    ОтветитьУдалить
  4. Кстати, в реализации Ярославского лично я не нашёл оптимизации которая перестаёт сортировать quick-sort-ом и сортирует heap-sort-ом если массив "почти отсортирован" (т.е. если случай представляет из себя худший случай для quick-sort-а). Это может быть причиной по которой реализация Ярославского проиграла std::sort-у

    ОтветитьУдалить
  5. 2Left
    За объяснение с предикатом - спасибо. Но всё равно очень большой скачок происходит, если переключить с дабага на релиз, - что-то смущает, должны быть ещё причины, кроме предиката.
    По поводу heap sort - я, каюсь, при выборе опирался на обзор сортировок от Google Education, в котором рассмотрены сортировки и рекомендации по их оптимизации. По непонятной причине Гугл забыл о heap sort, что привело к результатам выше...
    Реализую быструю сортировку с 2-м опрным элементом с использованием heap sort - вернусь с результатами.

    ОтветитьУдалить
  6. 2Left
    За объяснение с предикатом - спасибо. Но всё равно очень большой скачок происходит, если переключить с дабага на релиз, - что-то смущает, должны быть ещё причины, кроме предиката.
    По поводу heap sort - я, каюсь, при выборе опирался на обзор сортировок от Google Education, в котором рассмотрены сортировки и рекомендации по их оптимизации. По непонятной причине Гугл забыл о heap sort, что привело к результатам выше...
    Реализую быструю сортировку с 2-м опрным элементом с использованием heap sort - вернусь с результатами.

    ОтветитьУдалить
  7. Не-а, реализацию так чтобы подробно не смотрел. Как-нить на досуге гляну, может будут какие-то идеи.

    Под quick sort я понимал qsort из старого доброго C, прошу прощения что туманно выразился.

    А на отладочную сборку смотреть вообще не стОит. В числе прочих проверок она ещё и делает проверку корректности реализации предиката - т.е. если к примеру предикат не удовлятворяет требованиям (к примеру возвращает true и для (a,b) и для (b,a) то отладочная версия ругнётся ассертом. Т.е. как минимум число проверок вдвое больше чем реально нужно.

    ОтветитьУдалить