FlashSort – метод сортування за лінійний кількість перестановок

Привіт всім!

У мене є одне хобі – я дуже люблю винаходити велосипеди.
Про винахід одного такого велосипеда хочу вам сьогодні розповісти.

Сортування масиву даних – завдання, яким вже далеко не перший рік. Вона переслідує нас з перших курсів технічних вузів, а кому особливо пощастило, то й зі шкільної лави. Зазвичай це методи сортування «бульбашкою», «розподілом», «швидка», «вставками» та інші.

Сортування бульбашкою
Ось, приміром, подібної реалізації методу сортування «бульбашкою» мене вчили в однієї великої IT-компанії. Цей метод використовувався досвідченими програмістами там повсюдно.

Так ось, мені завжди було цікаво, чому приділяється так мало уваги методам сортування без порівняння (порозрядне, блокова тощо). Адже подібні методи відносяться до класу швидких алгоритмів, що виконуються за О(N) кількість перестановок і при вдало підібраних даних можуть виконуватися за лінійний час. Для сортування якихось абстрактних об'єктів вони, звичайно, слабо підходять, оскільки ці методи, власне, нічого й не порівнюють, а беруть якийсь розряд від значення (хоча при особливому бажанні можна вкорячить та сортування об'єктів). Однак на практиці більшість завдань сортування зводяться до впорядкування масиву звичайних примітивів: рядків, чисел, бітових полів тощо, де порівняння проходить в основному побайтно.
Якщо, приміром, ми будемо говорити про метод кишенькової сортування, то Вікіпедія утверждает, що він погано працює при великій кількості малоотличных елементів або ж на невдалої функції отримання номера корзини по вмісту елемента. Алгоритм вимагає наперед знати природу відсортовані даних. Також додатково потрібно організувати кишені, що від'їдає процесорний час і пам'ять. Однак, незважаючи на всі недоліки, потенційно час виконання алгоритму в теорії прагне до лінійного. Чи можливо вирішити зазначені недоліки і домогтися лінійного часу виконання?

Отже, пропоную вашій увазі алгоритм сортування за O(N) кількістю перестановок і з часом виконання «близьким» до лінійного.
Алгоритм сортує вихідні дані місцем і не використовує додаткової пам'яті. Інакше кажучи, сортування з О(N) переміщеннями і пам'яттю O(1).

Метод сортування заснований на методі кишенькової сортування. Якщо говорити про конкретну реалізації, то для більш ефективного порівняння елементів побайтно кількість кишень вибрано рівним 256. Кількість ітерацій (проходів) залежить від довжини одного елемента в байтах. Тобто загальна кількість перестановок буде дорівнює О(N*K), де K – довжина (кількість байт) одного елемента.
Для сортування нам необхідно використовувати спеціальний буфер – «кишені». Це масив довжиною 256, кожен елемент якого має розмір кишені і посилання на кордон кишені – це покажчик на перший елемент кишені у вихідному масиві. Спочатку буфер ініціалізованим першим нулями.

Отже, алгоритм сортування для кожної i-й ітерації складається з чотирьох етапів.

1 етап. Підрахунок розміру кишень
На першому етапі розраховуються розміри кишень. Ми використовуємо наш буфер, де для кожного кишені буде вестися лічильник кількості елементів. Ми пробегаемся по всім елементам, беремо значення i-го байта і інкрементуємо для відповідного кишені лічильник.


2 етап. Розстановка кордонів
Тепер, знаючи розміри кожної кишені, ми можемо чітко розставити кордону в нашому вихідному масиві для кожного кишені. Ми пробегаемся на нашу буферу і розставляємо кордону – встановлюємо покажчики на елементи для кожного кишені.


3 етап. Перестановка
Другим проходом ми переставляємо елементи у вихідному масиві таким чином, щоб кожен з них опинився на своєму місці, у своїй кишені.
Алгоритм перестановки наступний:
  • Пробегаемся по порядку всіх елементів масиву. Для поточного елемента беремо його i-й байт.
  • Якщо поточний елемент на своєму місці (в своїй кишені), то все ОК – пересуваємося далі, до наступного елемента.
  • Якщо елемент не на своєму місці – відповідний йому кишеню знаходиться далі, то робимо перестановку з тим елементом, який знаходиться в цьому далекому кишені. Повторюємо цю процедуру доти, поки не попадеться відповідний елемент з потрібним кишенею. Кожен раз, роблячи заміну, ми кладемо поточний елемент в свою кишеню і повторно вже не аналізуємо. Таким чином, кількість перестановок ніколи не буде перевищувати N.


Під час кожної перестановки лічильники в буфері для відповідного кишені будуть назад декрементироваться, і до кінця пробігу наш буфер буде знову заповнений нулями і готовий до використання на інших ітераціях.
Процес перестановки, як і перший етап, теоретично буде виконуватися за лінійний час, оскільки кількість перестановок ніколи не буде перевищувати N – кількість елементів.

4 етап. Рекурсивний спуск
І останній етап. Тепер ми рекурсивно сортуємо елементи всередині кожного сформованого кишені. Для кожної внутрішньої ітерації необхідно лише знати межу поточного кишені. Оскільки ми не використовуємо додаткової пам'яті (інформації про довжину поточного кишені у нас ніде не збереглася), ми, перед тим як перейти до внутрішньої ітерації, знову пробегаемся за елементами і обчислюємо довжину поточного кишені.



При бажанні цього можна уникнути, додатково оптимізувавши алгоритм і не видаляючи інформацію про довжинах кишень. Однак це потребує використання додаткової пам'яті. Зокрема O(log(K) * M), де M – кількість кишень (у нашому випадку це завжди 256), K – довжина одного елемента (в байтах).

Відмінною особливістю алгоритму є те, що при першому проході (етап №1) додатково запам'ятовується номер першого та останнього не порожньої кишені (покажчики pBucketLow, pBucketHigh). Надалі це дозволить заощадити час на 2-му і 3-му етапах. Подібна оптимізація передбачає, що більшість даних зосереджено в певному діапазоні даних і часто має деякі задані межі. Наприклад, рядкові дані часто починаються з символу A-Z. Числа (наприклад ID) також зазвичай обмежені якимось діапазоном.
Додаткову оптимізацію можна провести також і в разі, якщо номери нижнього і верхнього не порожньої кишені збігаються (pBucketLow == pBucketHigh). Це говорить про те, що всі елементи на i-му рівні мають однаковий байт, і всі елементи потрапляють в одну кишеню. В цьому випадку ми можемо тут же перервати ітерацію (пропустити 2,3,4 етапи) і перейти до наступного.
В алгоритмі використовується ще одна досить поширена оптимізація. Перед початком виконання будь-якої ітерації, у разі коли кількість об'єктів невелика (зокрема, менше 8), оптимальніше проводити яку-небудь дуже просту сортування (наприклад, bubble-sort).

Реалізація
З реалізацією вышепредставленного алгоритму на мові Сі можна ознайомитися на github: github.com/denisskin/flashsort

Для сортування даних слід скористатися функцією flash_sort, яка в якості параметра приймає покажчик на функцію get_byte(void*, int) – функцію отримання i-го байта елемента.
Наприклад, сортуємо рядки:
// sort array of strings
char *names[10] = {
"Hunter",
"Isaac",
"Christopher",
"Bob",
"Faith",
"Alice",
"Gabriel",
"Denis",
"****",
"Ethan",
};

static const char* get_char(const void *value, unsigned pos) {
return *((char*)value + pos)? (char*)value + pos : NULL;
}

flashsort((void**)names, 10, get_char);


Також в розпорядженні є функція flashsort_const для сортування даних строго заданої довжини.
Наприклад, чисел:
// sort integer values
int nums[10] = {9, 6, 7, 0, 3, 1, 3, 2, 5, 8};
flashsort_const(nums, 10, sizeof(int), sizeof(int));


Цю ж функцію можна з успіхом використовувати і для сортування масиву структур по ключу.
Наприклад:
// sort key-value array by key
typedef struct {
int key;
char *value;
} KeyValue;

KeyValue names[10] = {
{8, "Hunter"},
{9, "Isaac"},
{3, "Christopher"},
{2, "Bob"},
{6, "Faith"},
{1, "Alice"},
{7, "Gabriel"},
{4, "Denis"},
{0, "ні"},
{5, "Ethan"},
};

flashsort_const(names, 10, sizeof(KeyValue), sizeof(names->key));


Функція flashsort_const зрозумілих причин буде працювати трохи повільніше її аналога – функції, яка була оголошена за допомогою спеціального макросу. У цьому випадку перестановка елементів і отримання i-го байта елемента буде відбуватися значно швидше.
Наприклад, оголосити функцію сортування чисел за допомогою макросу можна наступним чином:
// define function flashsort_int by macro
#define FLASH_SORT_NAME flashsort_int
#define FLASH_SORT_TYPE int
#include "src/flashsort_macro.h"

int A[10] = {9, 6, 7, 0, 3, 1, 3, 2, 5, 8};
flashsort_int(A, 10);


Бенчмарки
В цьому ж репозиторії можна знайти і бенчмарки, де для порівняння додано сортування методом qsort.
cd benchmarks
gcc ../src/*.c benchmarks.c -o benchmarks.o && ./benchmarks.o


В результаті, метод flash_sort добре показує себе порівняно з qsort в роботі з випадково розподіленими даними. Наприклад, сортування масиву з 500К чисел типу int працює в 2.5 рази швидше quick-sort. Як видно з бенчмарку, середній час сортування, поділена на N, із зростанням кількості елементів практично не змінюється.

Benchmarks sorting of integers
-------------------------------------------------------------------------------------------
Count Flash-sort | Quick-sort |
elements Total time | Total time |
N Tf Tf / N | Тq Тq / N | Δ
-------------------------------------------------------------------------------------------
100 0.000012 sec 1.225 μs | 0.000004 sec 0.428 μs | -65.10 %
194 0.000016 sec 0.814 μs | 0.000009 sec 0.439 μs | -46.04 %
374 0.000026 sec 0.690 μs | 0.000023 sec 0.604 μs | -12.40 %
724 0.000043 sec 0.592 μs | 0.000058 sec 0.795 μs | +34.29 %
1398 0.000099 sec 0.707 μs | 0.000155 sec 1.112 μs | +57.28 %
2702 0.000204 sec 0.753 μs | 0.000300 sec 1.111 μs | +47.44 %
5220 0.000410 sec 0.786 μs | 0.000620 sec 1.187 μs | +51.02 %
10085 0.000845 sec 0.838 μs | 0.001254 sec 1.243 μs | +48.41 %
19483 0.002205 sec 1.132 μs | 0.002672 sec 1.372 μs | +21.21 %
37640 0.004242 sec 1.127 μs | 0.005436 sec 1.444 μs | +28.15 %
72716 0.006886 sec 0.947 μs | 0.011171 sec 1.536 μs | +62.23 %
140479 0.011156 sec 0.794 μs | 0.022899 sec 1.630 μs | +105.26%
271388 0.018773 sec 0.692 μs | 0.045749 sec 1.686 μs | +143.70%
524288 0.037429 sec 0.714 μs | 0.093858 sec 1.790 μs | +150.76%


Аналогічні результати видає і сортування випадкових рядків заданої довжини. Наприклад, список випадкових хешів, кодованих в base64.

benchmark Sorting of hashes base64
---------------------------------------------------------------------------------------------
Count Flash-sort | Quick-sort | 
elements Total time | Total time | 
N Tf Tf / N | Тq Тq / N | Δ 
---------------------------------------------------------------------------------------------
147 0.000009 sec 0.609 μs | 0.000010 sec 0.694 μs | +13.97 %
274 0.000025 sec 0.918 μs | 0.000027 sec 0.991 μs | +7.95 %
512 0.000053 sec 1.036 μs | 0.000061 sec 1.195 μs | +15.37 %
955 0.000098 sec 1.024 μs | 0.000135 sec 1.416 μs | +38.32 %
1782 0.000164 sec 0.921 μs | 0.000279 sec 1.566 μs | +70.04 %
3326 0.000315 sec 0.947 μs | 0.000581 sec 1.745 μs | +84.31 %
6208 0.000629 sec 1.013 μs | 0.001210 sec 1.949 μs | +92.39 %
11585 0.001325 sec 1.144 μs | 0.002378 sec 2.053 μs | +79.50 %
21618 0.002904 sec 1.343 μs | 0.004712 sec 2.180 μs | +62.26 %
40342 0.006132 sec 1.520 μs | 0.009752 sec 2.417 μs | +59.03 %
75281 0.010780 sec 1.432 μs | 0.019778 sec 2.627 μs | +83.47 %
140479 0.023484 sec 1.672 μs | 0.043534 sec 3.099 μs | +85.37 %
262144 0.044967 sec 1.715 μs | 0.082878 sec 3.162 μs | +84.31 %


Однак метод працює без явної переваги: лише трохи спритніше, ніж quick-sort під час сортування випадково перемішаних англійських слів.

benchmark Sorting of english words
---------------------------------------------------------------------------------------------
Count Flash-sort | Quick-sort | 
elements Total time | Total time | 
N Tf Tf / N | Тq Тq / N | Δ 
---------------------------------------------------------------------------------------------
140 0.000016 sec 1.166 μs | 0.000014 sec 0.993 μs | -14.85 %
261 0.000030 sec 1.168 μs | 0.000029 sec 1.114 μs | -4.59 %
485 0.000055 sec 1.139 μs | 0.000061 sec 1.259 μs | +10.59 %
901 0.000141 sec 1.565 μs | 0.000158 sec 1.750 μs | +11.82 %
1673 0.000269 sec 1.608 μs | 0.000315 sec 1.884 μs | +17.17 %
3106 0.000536 sec 1.726 μs | 0.000655 sec 2.110 μs | +22.27 %
5766 0.001013 sec 1.756 μs | 0.001263 sec 2.191 μs | +24.76 %
10703 0.002007 sec 1.875 μs | 0.002525 sec 2.359 μs | +25.85 %
19868 0.004152 sec 2.090 μs | 0.005150 sec 2.592 μs | +24.04 %
36880 0.008459 sec 2.294 μs | 0.010266 sec 2.784 μs | +21.36 %
68458 0.017460 sec 2.550 μs | 0.021423 sec 3.129 μs | +22.70 %
127076 0.035615 sec 2.803 μs | 0.041683 sec 3.280 μs | +17.04 %
235885 0.075747 sec 3.211 μs | 0.086523 sec 3.668 μs | +14.23 %


Непогано метод показує себе в роботі з часто повторюваними даними. Наприклад, сортування логів півмільйона IP-адрес (взятих з реального життя) методом flash-sort працює в 5 разів швидше, ніж швидка сортування.

benchmark Sorting of IP addresses log
---------------------------------------------------------------------------------------------
Count Flash-sort | Quick-sort |
elements Total time | Total time |
N Tf Tf / N | Тq Тq / N | Δ
---------------------------------------------------------------------------------------------
107 0.000010 sec 0.953 μs | 0.000011 sec 1.056 μs | +10.78 %
208 0.000013 sec 0.639 μs | 0.000010 sec 0.480 μs | -25.00 %
407 0.000024 sec 0.584 μs | 0.000033 sec 0.812 μs | +39.01 %
793 0.000039 sec 0.493 μs | 0.000073 sec 0.915 μs | +85.61 %
1547 0.000080 sec 0.517 μs | 0.000211 sec 1.367 μs | +164.15%
3016 0.000169 sec 0.560 μs | 0.000512 sec 1.697 μs | +202.80%
5881 0.000308 sec 0.523 μs | 0.000962 sec 1.636 μs | +212.67%
11466 0.000548 sec 0.478 μs | 0.001812 sec 1.581 μs | +230.48%
22354 0.001034 sec 0.463 μs | 0.004191 sec 1.875 μs | +305.26%
43584 0.002109 sec 0.484 μs | 0.008693 sec 1.994 μs | +312.26%
84974 0.004411 sec 0.519 μs | 0.016003 sec 1.883 μs | +262.81%
165670 0.008837 sec 0.533 μs | 0.037358 sec 2.255 μs | +322.75%
323000 0.016046 sec 0.497 μs | 0.081251 sec 2.516 μs | +406.36%
629739 0.030895 sec 0.491 μs | 0.164283 sec 2.609 μs | +431.75%


Причому на подібних даних час сортування зростає строго лінійно від кількості відсортовані елементів.

висновок
Незважаючи на те що представлений тут метод сортування завжди робить строго O(N) перестановок, все ж наївно було б очікувати, що для всіх типів даних у всіх випадках алгоритм буде працювати за лінійний час. Цілком очевидно, що на практиці швидкість його роботи буде залежати і від характеру відсортовані даних.
Виконання алгоритму в загальному випадку буде відбуватися за нелінійне час хоча б тільки тому, що на етапі перестановки елементів йому необхідно звертатися до випадковим ділянок пам'яті.
Однак вважаю, що все ж ще є простір для оптимізації описаного тут методу. Наприклад, на першому етапі алгоритму, крім підрахунку кількості елементів, які потрапляють у кошик, можливо вести ще якусь складнішу статистику і вже на її підставі вибирати різні методи для сортування елементів усередині кошика. Упевнений, що в кінцевому рахунку хорошим рішенням могла б стати розробка такого гібридного алгоритму, що поєднує в собі підходи різних методів сортування, а також оптимізацію під конкретне фізичне представлення даних в пам'яті або на диску.
Однак ці питання виходять за рамки статті, метою якої було лише показати можливості методів сортування «не порівнянням» в чистому їх вигляді. У будь-якому випадку вважаю, що в питаннях сортування даних поки ще рано ставити крапку.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.