среда, 21 декабря 2011 г.

Tim Sort

[Все сортировки]

Теория:
habrahabr.ru, код реальных мужиков на С (зеркало)

Практика:
informatics.mccme.ru

Немного размышлений:
1) Не так давно общественность была взбудоражена малоизвестной сортировкой Tim Sort, которая творит чудеса. Поэтому возникло желание попробовать сделать ее реализацию. Когда разбирался в описании, представленном на хабре и в wikipedia, как в русской, так и в английской, возникли вопросы, на которые я не смог найти ответы. Больше всего вызывала вопросов та часть, в которой происходит эффективное слияние подмассивов, примерно равной длины. Т.к. я писал сортировку для случайного набора данных, поэтому хотелось избежать непоняток с волшебными длинами X,Y и Z, а именно просто сливать два последних подмассива, если они имеют одинаковую длину. Как показала практика в оригинальном алгоритме преследовалась та же идея.

Разбираясь в реализации на С(см. теория), было выведено правило грамотного слияния подмассивов с поддержанием баланса длин. Пусть X,Y,Z  - длины верхних трех интервалов, которые лежат в стеке. Причем X – это последний элемент стека.
Правило следующее:
1. Повторяем пока выражение (Z > X + Y && Y > X) не станет истинным
2. Если количество элементов в стеке не меньше 3 и Z <= X + Y – сливаем Y c min(X,Z).
   Иначе Если Y<=X – сливаем X c Y
3. Возвращаемся в п.1.

В wikipedia и на habr’e написано другое правило, в котором X и Z поменены местами, и по которому ничего путного сделать у меня не получилось.

2) В оригинальной идее предполагалось, что во временный массив помещается меньший из сливаемых подмассивов. При этом, если это левый подмассив, то формирование результирующего массива идет слева направо + используется бинарный поиск по не убыванию. В противном случае, когда правый подмассив имеет размер меньше чем левый, ответ формируется справа налево + используется бинарный поиск по не возрастанию. Скажу честно, мне было лень замачиваться на такие вещи, поэтому в приведенной реализации всегда копируется левый подмассив.

3) Для меня осталась загадкой, откуда у автора алгоритма Тима Петерсона такая любовь к сортировке вставками, которая требует в худшем случае n(n-1)/2 обменов. Хотя конечно, для худшего случая, когда массив упорядочен в обратном порядке, стоят нужные механизмы, которые реверснут массив за n/2 обменов, но все равно вопрос для меня остался открытым. В этом плане мне больше импонирует сортировка выбором, которая требует не более n обменов, которая и была приведена в реализации.

Реализация:

  1. struct segment {
  2.   int beg; // индекс первого элемента
  3.   int len; // длина интервала
  4.   segment(){}
  5.   segment(int b, int l) : beg(b), len(l){}
  6. };
  7. // ответ должен быть в диапазоне (32,64]
  8. inline int get_min_size(int n) {
  9.   int r = 0;
  10.   while (n >= 64) {
  11.     n >>= 1;
  12.     r |= n &1;
  13.   }
  14.   return n + r;
  15. }
  16. // Да простит меня Тим Петерсон, но вместо сортировки вставками
  17. // я использую сортировку выбором
  18. void selection_sort(vector<int> &mas, int beg, int last) {
  19.   for (int i=beg; i<last;++i) {
  20.     int min_pos = i;
  21.     for (int j=i+1; j<last; ++j) {
  22.       if (mas[j] < mas[min_pos])
  23.         min_pos = j;
  24.     }
  25.     swap(mas[i],mas[min_pos]);
  26.   }
  27. }
  28. const int dx = 1, dy = 2, dz = 3;
  29. void merge(vector<int> &mas, vector<segment> &seg, bool isXY, vector<int> &tmp) {
  30.   segment f = seg[seg.size() - dy];
  31.   segment s = isXY ? seg[seg.size() - dx] : seg[seg.size() - dz];
  32.   if (f.beg > s.beg) swap(f,s);
  33.   int posF = 0, posS = s.beg, pos = f.beg-1;
  34.   int lstF = f.len, lstS = s.beg + s.len;
  35.   copy(mas.begin() + f.beg + posF, mas.begin() + f.beg + lstF, tmp.begin());
  36.   int fAmount = 0, sAmount = 0;
  37.   while (posF < lstF && posS < lstS) {
  38.     if (tmp[posF] < mas[posS]) {
  39.       mas[++pos] = tmp[posF++];
  40.       ++fAmount; sAmount=0;
  41.       if (fAmount == 7) {
  42.         vector<int>::iterator it = upper_bound(tmp.begin() + posF, tmp.begin() + lstF, mas[posS]);
  43.         copy(tmp.begin() + posF, it, mas.begin() + pos + 1);
  44.         pos += it - (tmp.begin() + posF);
  45.         posF += it - (tmp.begin() + posF);
  46.       }
  47.     }
  48.     else {
  49.       mas[++pos] = mas[posS++];
  50.       fAmount=0; ++sAmount;
  51.       if (sAmount == 7) {
  52.         vector<int>::iterator it = upper_bound(mas.begin() + posS, mas.begin() + lstS, tmp[posF]);
  53.         copy(mas.begin() + posS, it, mas.begin() + pos + 1);
  54.         pos += it - (mas.begin() + posS);
  55.         posS += it - (mas.begin() + posS);
  56.       }
  57.     }
  58.   }
  59.   copy(tmp.begin() + posF, tmp.begin() + lstF, mas.begin() + pos + 1);
  60. }
  61. void try_merge(vector<int> &mas, vector<segment> &seg, vector<int> &tmp, bool is_merge = false) {
  62.   while (seg.size() > 1) {
  63.     int x = seg[seg.size() - dx].len;
  64.     int y = seg.size() < 2 ? 0 : seg[seg.size() - dy].len;
  65.     int z = seg.size() < 3 ? 0 : seg[seg.size() - dz].len;
  66.     if (seg.size() >= 3 && z <= x + y) {
  67.       if (z < x) {
  68.         merge(mas,seg,false,tmp);
  69.         seg[seg.size() - dz].len += seg[seg.size() - dy].len;
  70.         seg[seg.size()- dy] = seg[seg.size()- dx];
  71.         goto POP_BACK;
  72.       }
  73.       else {
  74.         merge(mas,seg,true,tmp);     
  75.         seg[seg.size() - dy].len += seg[seg.size() - dx].len;
  76.         goto POP_BACK;
  77.       }
  78.     }
  79.     else if (is_merge || y <= x) {
  80.       merge(mas,seg,true,tmp);
  81.       seg[seg.size() - dy].len += seg[seg.size() - dx].len;
  82.       goto POP_BACK;
  83.     }
  84.     else
  85.       break;
  86. POP_BACK: seg.pop_back();
  87.   }
  88. }
  89. void tim_sort(vector<int> &mas) {
  90.   int n = mas.size();
  91.   vector<int> tmp(n);
  92.   int min_size = get_min_size(n);
  93.   int beg = 0, size = min_size;
  94.   vector<segment> seg;
  95.   seg.reserve((n-1)/min_size + 1);
  96.  
  97.   for (int i=0;i<n;i+=min_size) {
  98.     size = min(min_size,n-i);
  99.     selection_sort(mas,i,i+size); 
  100.     seg.push_back(segment(i,size));
  101.     try_merge(mas, seg, tmp);
  102.   }
  103.   while (seg.size() != 1) {
  104.     try_merge(mas, seg, tmp, true);
  105.   }
  106. }
* This source code was highlighted with Source Code Highlighter.

P.S: Признаюсь я изначально не возлагал больших надежд на эту сортировку(особенно на свою эффективную реализацию), но должен признать, что был не прав. Данная реализация зашла за 0.061 с, в то время, когда быстрая работал за 0.059 с. Учитывая, что в данную реализацию можно добавить копирование меньшего подмассива + дописать бинарный поиск по не возрастанию, данная сортировка становится пожалуй лучшей для сортировки случайного набора данных. Разработчики Python не могли ошибаться =).

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

  1. >> Для меня осталась загадкой, откуда у автора алгоритма Тима Петерсона такая любовь к сортировке вставками.

    Ответ очевиден. Операция сравнения в Python медленная (ради нее бедной весь сыр-бор и затевался), поэтому для сортировки маленького массива и используется сортировка вставками.

    Если приглядется к коду мужЫков, то видно, что для поиска места для встаки используется бинарный поиск.
    Цена копирования даже в худшем случае - ничто по сравнению с медленным сравнением.

    ОтветитьУдалить
    Ответы
    1. Все же основная причина использования сортировки вставками кроется в его плюсах и основной идее Tim Sort.

      Плюсы сортировки вставками:
      - эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;
      - эффективен на наборах данных, которые уже частично отсортированы;

      А учитывая то, что основная фишка Tim Sort в том, что сортируемый массив данных часто содержит в себе упорядоченные подмассивы, получается совершенно логичным использование в нем сортировки вставками.

      Удалить
    2. Сортировка выбором тоже хорошо работает на небольших массивах.
      Куда большее значение имеет тот факт, что сортировка выбором всегда работает не более чем за O(N) swap'ов, с использованием O(N^2) сравнений.
      Сортировка вставками использует большее количество swap'ов, но меньше количество сравнений по сравнению с сортировкой выбором.

      Удалить
    3. Возможно, но в любом случае использование сортировки вставками в Tim Sort более уместно, ибо на частично отсортированных массивах небольшого размера он наиболее эффективен. Что легко проверить, попробовав скормить упорядоченный массив обоим алгоритмам.

      Удалить
  2. Картина становится ясней. Спасибо за ценную справку про Python.

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