*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

четверг, 18 июня 2009 г.

Как реализована сортировка в STL

Все началось с того, что я почему-то написал свою реализацию классического алгоритма быстрой сортировки QuickSort. И все бы хорошо, но я, конечно, решил померяться достоинством с STL'ой реализацией. Результат был очевиден, и я даже не хочу приводить цифры.

Вобщем, я открыл файл algorithm из STL'я в Visual Studio 2008 и часок покопался в нем. Вот результаты моих "исследований".

Начнем с нестабильной сортировки std::sort().
  • основа: алгоритм быстрой сортировки QuickSort (почти как у меня)
  • выбор опорного элемента — центральный по индексу элемент в сортируемом фрагменте
  • после каждого выбора опорного элемента:
    • начальный, опорный и последний элементы сортируются между собой (их всего три, так что тут это делается тремя последовательными if'ами)
    • если длина сортируемого фрагмента менее более 40, то отрезок делится 8 частeй (длина каждой части S = 1/8*N) и для троиц элементов (1, S, 2*S), (N/2 - S, N/2, N/2 + S) и (N - 2*S, N - S, N) делается такая же минисортировка, как и на предыдущем шаге (где число элементов было меньше 40)
    • далее происходит обычная для QuickSort процедура деления фрагмента на две части с использованием опорного элемента (цикл по перебрасыванию элементов, меньших опорного направо, а больших — налево)
  • затем вся процедура рекурсивно повторяется для левой и правой частей
Количество рекурсивных операций не идет до победного конца, как в чистом QuickSort. Если количество итераций (процедур разделения массива) превысило 1.5*log2(N), где N длина всего массива, то рекурсивные операции прекращаются. Если количество оставшихся недосортированных элементов меньше 32-х, то фрагмент досортируется методом вставки InsertionSort (этот метод имеет общую сложность O(N2) и для больших массивов не используется, но на малых длинах он быстрее всех из-за простоты). Если же остается более 32-х элементов, то досортировка происходит пирамидальным методом HeapSort в чистом его виде.

Видимо все эти ухищрения для уменьшения накладных расходов QuickSort на малых массивах.

Вот такая вот далеко непрямолинейная реализация.

Далее.

Стабильная сортировка std::stable_sort() реализована алгоримом слияния MergeSort. Особых ухищрений по сравнению с чистным алгоритмом я не нашел. Разве что малые фрагменты (короче 32-х элементов) досортировываются методом вставки InsertionSort, как и в случае с QuickSort.

Частичая сортировка std::partial_sort() реализована в чистом виде пирамидальным методом HeapSort.

Вывод:
Читать исходники очень интересно. Особенно хорошие исходники.

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

  1. Я так понимаю что рассмотрена версия STL из поставки VC9 ?
    Просто много раз сталкивался, что реализации для GCC и VC значительно отличаются, так же как и STLPort отличается от них всех (отличается именно во внутреннем представлении т.к. внешний интерфейс стандартен)

    ОтветитьУдалить
  2. Да, студия 2008 - это VC9 по имени.

    Надо будет заглянуть еще в борландовую версию.

    ОтветитьУдалить
  3. Относительно stl правильней говорить все-таки о introsort (O(n log n) в худшем случае), нежели о quicksort (непозволительные O(n^2) в худшем случае).

    ОтветитьУдалить
  4. Ваша правда. Все что я описал, прямяком является Introsort'ом. Вот так и узнаешь для себя много интересного.

    ОтветитьУдалить
  5. Как-то ради фана писал алгоритмы сортировки. Для быстрой померял производительность с std::sort(). Догнать не получилось, как не пытался.

    А ещё говорят, что STL сакс...

    PS. Кстати догнать сишный qsort() тоже не получилось, там какие-то хитрые оптимизации.

    ОтветитьУдалить
  6. После этой статьи решил посмотреть как дело обстоит в java (Arrays.sort) - всё то же самое (только местами в профиль, характерным для java) - а перед самим методом такой javadoc:

    The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993).
    This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

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