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 не могли ошибаться =).

Минимальный циклический сдвиг

Задача: “Дается строка S. Длина S не превышает 1e5. Необходимо найти минимальный в лексикографическом порядке циклический сдвиг строки S”.

1.Полиномиальные хеш-функции.
По мотивам презентации Александра Скиданова

Рассмотрим строку S = “abcdabb”
h(L) – полиномиальная хеш-функция от префикса строки S длины L.




h(0) = h(“”)        = 0
h(1) = h(“a”)       = a
h(2) = h(“ab”)      = a*x¹ + b
h(3) = h(“abc”)     = a*x² + b*x¹ + c
h(4) = h(“abcd”)    = a*x³ + b*x² + c*x¹ + d
h(5) = h(“abcda”)   = a*x⁴ + b*x³ + c*x² + d*x¹ + a
h(5) = h(“abcdab”)  = a*x⁵ + b*x⁴ + c*x³ + d*x² + a*x¹ + b
h(5) = h(“abcdabb”) = a*x⁶ + b*x⁵ + c*x⁴ + d*x³ + a*x² + b*x¹ + b

Рекурсивно полиномиальную хеш-функцию h(L) можно выразить так:


H(a,b)- полиномиальная хеш-функция от подстроки S в интервале [a,b)

Следовательно можно получать полиномиальные хеш-функции от любой подстроки S за O(1).

Пусть len – длина строки S.
Возвращаемся к первоначальной задачи. Чтобы найти минимальный циклический сдвиг строки S:
1) Модифицируем исходную строчку S = S + S.
2) Считаем полиномиальную хеш-функцию h(L) для всех префиксов строки S.
3) На текущем шаге наилучший ответ на поставленную задачу – это подстрока строки S длины len, начинающаяся c позиции best = 0.
4) Последовательно перебираем все возможные начальные позиции cur в интервале [1,len)
5) Бинарным поиском подбираем длину общего префикса для наилучшего текущего ответа, начинающегося с позиции best, и кандидата на это место, начинающегося с позиции cur.
6) Сравниваем первые различные символы двух образцов. Если у текущего кандидата на этой позиции стоит символ с меньшим кодом, тогда обновляет наилучший ответ.

1. typedef unsigned long long UINT;
2. int min_cycle_shift(char *s, int init_len) {
3.   UINT *hash = new UINT[2*init_len];
4.   hash[0] = 0;
5.   for (int i=1;i<2*init_len;++i)
6.     hash[i] = x * hash[i-1] + s[i-1];
7.  
8.   int bst_pos = 0;
9.   for (int cur_pos = 1; cur_pos < init_len; ++cur_pos) {
10.     int l = 0, r = init_len-1, res = 0;
11.     while (l <= r) {
12.       int len = (l + r) >> 1;
13.       UINT hash_bst = hash[bst_pos + len] - hash[bst_pos] * _pow[len];
14.       UINT hash_cur = hash[cur_pos + len] - hash[cur_pos] * _pow[len];
15.       if (hash_bst == hash_cur) {
16.         res = len;
17.         l = len + 1;
18.       }
19.       else {
20.         r = len - 1;
21.       }
22.     }
23.     if (s[bst_pos + res] > s[cur_pos + res])
24.       bst_pos = cur_pos;
25.   }
26.   delete[] hash;
27.   return bst_pos + 1;
28. }

* This source code was highlighted with Source Code Highlighter.

Сложность данного решения:

P.S: В качестве x нужно использовать небольшое простое число. Например 11.
P.S.S: Все вычисления ведутся без модульной арифметики. Поэтому интервал возможных значений полиномиальной хеш-функции равен 2⁶⁴.

2. Алгоритм Дюваля

Все что нужно - написано на e-maxx’e. Приведу просто фрагмент кода, решающую ту же самую задачу.

1. // s уже равна s+s
2. int min_cycle_shift(char *s, int len) {
3.   int i = 0, ans = 0;
4.   while (i < len/2) {
5.     ans = i;
6.     int k = i, j = i+1;
7.     while (j < len && s[k] <= s[j]) {
8.       if (s[k] < s[j])
9.         k = i;
10.       else
11.         ++k;
12.       ++j;
13.     }
14.     while (i<=k)
15.       i += j - k;
16.   }
17.   return ans + 1;
18. }

* This source code was highlighted with Source Code Highlighter.

Сложность данного решения:

Сортировка большого файла с целыми числами: Генератор тестов (Часть 1)

[Все части]
[Прошлая часть: Вводное слово]

Итак, чтобы удобнее было готовится к нашему состязанию, была разработана небольшая утилита для генерации тестов.
При запуске утилиты big_sort_tests_gen.exe мы видим следующую таблицу.

После того, как все настройки выставлены, вводим команду –start.

Общий механизм работы утилиты:
На первом этапе все числа равномерно распределяются между между временными файлами. После чего запускаются независимые потоки, в которых генерируются временные файлы с тем количеством чисел, которые файл получил во время распределения:
На втором этапе все временные файлы сливаются в один:
После выполнения первых двух этапов мы получаем информацию о времени, которое было затрачено на их выполнение:
Корректность сгенерированного файла можно проверить с помощью команды –check:
Если файл сгенерирован, согласно требованиям условия задачи(см. Прошлый пост: Вводное слово), то появится “OK!”. В противном случае будет выведено описание ошибки.

Все сгенерированные файлы записывают в директорию test, расположенную вместе с исполняемым файлом утилиты.

О настройках генератор довольно популярно изложено в следующем видео:

Исходник генератора (проект MS VS 2008, Win32, C++): http://tinyurl.com/cvm6s3a
Бинарники генератора + окружение(Win32): http://tinyurl.com/c9qch5v
Откомпилированный генератор под Linux ждем от Сагунова Данила.

Если у Вас возникли вопросы, предложения, замечания. Будем рады их услышать

Сортировка большого файла с целыми числами: Вводное слово (Часть 0)

[Все части]
[Следующая часть: Генератор тестов]

Не так давно родилась идея организовать небольшое состязание на самое быстрое решение следующей задачи.

Условие задачи:
Входной текстовый файл input.txt содержит набор из N 32-ух битных знаковых чисел, разделенных между собой ровно одним пробелом. Необходимо отсортировать числа из входного файла и записать их во выходной файл output.txt. 1<=N<=1e9.

Регламент:
0. Приглашаются к участию все желающие. Вне зависимости от города проживания и возрастной группы.

1. Решение участника должно быть представлено в виде exe файла, скомпилированного под Windows. Файлы input.txt и output.txt будут находиться в той же директории, что и исполняемый файл. Допускается наличие любых сторонних файлов(библиотеки, конфиги и пр.) вместе и исполняемым файлом.

2. Программа может рассчитывать на:
1) HDD: 10 GB
2) RAM: 128 MB

3. Проверяться решение будет на ноутбуке со следующими параметрами:
1) Процессор: Intel Core2Duo T5250 1.5GHz (Параметры железа могут измениться)
2) Платформа: Windows 7 (x86)
3) Файловая система: NTFS

4. Решение считается зачтенным, если оно успешно прошло все заготовленные тесты и не выкинуло ни одного исключения. На каждом тесте программа будет запускаться 10 раз. Результатом работы программы будет усредненное время. Если программа во время своей работы использовала лишнеее место на жестком диске или лишнюю оперативную память, то оно штрафуется. Зачтенные решения ранжируются по времени работы. Побеждает самое быстрое решение.

5. Решения можно реализовывать на любом языке программирования, использовать любые сторонние библиотеки. Главное, чтобы с исполняемым файлом шел весь набор библиотек. Если будет замечено вредительство со стороны программы: –10 к карме автора решения.

6. Максимальный срок подачи решения 15 января 2012 (Возможно продление этого срока по желанию участников, т.к. в это время будет проходить сессия у студентов и подготовка к областной олимпиаде по информатике у школьников).

Главный приз: 1 Euro и признание со стороны товарищей(бесценно).
По итогу состязания будет разбор общих подходов к решению подобных задач(о нем будет сказано в последующих частях).

Все вопросы и пожелания пишите здесь в комментариях или в группе: http://vkontakte.ru/club13315512

[Следующая часть: Генератор тестов]

Сортировка большого файла с целыми числами

Текущий список участников:
1. Беляев Игорь     (г. Астрахань – АГТУ - аспирант)
2. Бородин Виталий  (г. Астрахань – АГТУ - студент)
3. Елизаров Дмитрий (г. Астрахань – АГТУ - аспирант)
4. Сагунов Данил    (г. Астрахань – АТЛ  - школьник)
5. Степанов Павел   (г. Астрахань – АГТУ - студент)
6. Чаплыгин Андрей  (г. Астрахань - разработчик)

Часть 0: Вводное слово.
Описывается регламент состязания: условие задачи, параметры железа и критерии правильности решения.

Часть 1: Генератор тестов
Представлена утилита, генерирующая тесты, согласно описанной задаче. Можно задавать диапазон генерируемых чисел.