Будь-яке введення або посібник з алгоритмів сортування зазвичай включає стандартні алгоритми — quicksort, merge sort, insertion sort, heap sort тощо — які вважаються підходящими для повсякденного використання. Іншими словами, це категорично не езотеричні алгоритми сортування, які я досліджую, як-от sleep sort або permutation sort.
Кожен алгоритм має свої переваги та недоліки з точки зору простору, часу та стабільності. Однак навіть при наявності широкого вибору алгоритмів, не кожен з них підходить для кожної ситуації, тому часто використовуються гібридні алгоритми. Адаптація та комбінування — це поширена риса програмування, але деякі гібриди достатньо спеціалізовані та цікаві, щоб їх виокремили та дали назву.
Наприклад, Timsort — це стабільний алгоритм сортування, вперше представлений у Python, який поєднує merge sort та insertion sort; introsort, який вперше використовувався в реалізаціях стандартної бібліотеки C++, оптимізує quicksort за допомогою heap sort.
Тепер виникає питання: чи має сенс створювати гібридні езотеричні алгоритми? Можливо, фраза «має сенс» тут занадто категорична, але коротка відповідь — «так».
Як приклад, Thanos sort можна вважати комбінацією як dropsort, так і bogosort:
- Bogosort випадковим чином перемішує значення, поки вони не будуть відсортовані. Хоча ймовірність того, що алгоритм ніколи не досягне відсортованого стану, достатньо мала, щоб суперечити як представленням з плаваючою комою, так і людській уяві, bogosort технічно не гарантує завершення. Ця можливість не завершення з найгіршим варіантом O(∞) є лише частиною неефективності, яку він пропонує.
- Dropsort просто і ефективно усуває будь-яке значення, яке не знаходиться у відсортованому порядку.
Простий, стабільний, ефективний — виконується за лінійний час, і не менше! — але з певними втратами.
Thanos sort має характерну структуру і результат, який поєднує як dropsort, так і bogosort: простий, стабільний, з втратами і випадковий, але гарантовано завершується.
Найкраще з обох
Щоб зрозуміти назву та основний принцип Thanos sort, потрібно знати, що Thanos — це суперлиходій з Marvel Cinematic Universe:
Ттанос був геноцидним полководцем з Титану, чия мета полягала в тому, щоб привести всесвіт до стабільності, знищивши половину всього живого на кожному рівні, оскільки він вірив, що його величезна популяція неминуче використає всі ресурси всесвіту і загине.
Спойлер: він досягнув своєї мети в кінці Avengers: Infinity War.
Він завершив Інфініті Гаунтлет, використавши його, щоб врешті-решт досягти своєї мети через Snap, що призвело до знищення половини всього живого у всесвіті одним рухом його пальців.
Таким чином, маючи послідовність значень, основний принцип Thanos sort полягає в тому, щоб повторно і випадковим чином усувати половину значень, поки решта не буде відсортована.
Залишаючи осторонь важливе питання збереження значень, структура цього алгоритму схожа на permutation sort або (неумисно оптимізований) bogosort. На високому рівні це наводить на наступний JavaScript код:
function thanosSort(values) {
while (!isSorted(values))
snap(values);
}
Підхід поступового розділення — в цьому випадку частина для збереження і частина для відкидання — поки частина не буде відсортована, (дуже умовно) нагадує quicksort. Такий підхід "поділу та знищення" може надихнути на рекурсивну реалізацію:
function thanosSort(values) {
if (!isSorted(values)) {
snap(values);
thanosSort(values);
}
}
У будь-якому разі, усунення відбувається лише тоді, коли початкова послідовність є не відсортованою.
function isSorted(values) {
return values.every(
(value, index) => index === 0 || value >= values[index - 1]);
}
Отже, Thanos sort не має жодного ефекту на вже відсортовані вхідні дані, до яких відносяться порожні і одноелементні послідовності.
Це контрастує з правильно песимізованими реалізаціями bogosort, де спочатку виконується дія сортування, а не перевірка, чи відсортовано. Функція snap є дією сортування для Thanos sort:
function snap(values) {
const survivors = Math.floor(values.length / 2);
while (values.length > survivors) {
const toSnap = Math.floor(Math.random() * values.length);
values.splice(toSnap, 1);
}
}
Тут елементи випадковим чином відкидаються один за одним, поки не досягнеться потрібної кількості «виживших».
Примітив number в JavaScript є числом з плаваючою комою, тому постійно використовуються функції Math.floor, щоб округлити результат ділення довжини до цілого числа, спочатку від ділення довжини, а потім від виразу для випадкового числа.
(Зазначимо, що я зазвичай віддаю перевагу Math.trunc як більш цілеспрямованій операції, що обрізає нецілочислову частину і є більш безпосередньо еквівалентною приведенню до int в інших мовах, але тут я використовую floor, щоб бути послідовним з наступними частинами коду.)
Як нагадування, коли ми кажемо «випадковий», ми маємо на увазі «псевдовипадковий», якщо не вказано інше. Ми повинні ще більше усвідомлювати, що те, що JavaScript пропонує з коробки в цьому відділі, підходить лише для коду, який хоче «потрясти все трохи». У JavaScript немає вибору генератора чи контролю за послідовністю, що робить його непридатним для застосувань, що потребують відомих статистичних властивостей або повторюваності. Це обмеження стосується не тільки криптографії та фізичних симуляцій, але й тестування.
Відсутність (дивовижної та розчаровуючої) функції ініціалізації робить псевдовипадковий генератор чисел у JavaScript ще більш примітивним, ніж можливості PRNG, що зустрічалися в багатьох домашніх комп’ютерних BASIC в 70-х та 80-х роках.
Біас виживших
У цьому коді є тонка упередженість до певних класів вхідних даних. Результат цілоїсчислового ділення (div) для натуральних чисел завжди буде або рівним, або меншим за результат справжнього ділення, тобто x div y ≤ x÷y. Наприклад, 4 div 2 і 4÷2 обидва дорівнюють 2, але 3 div 2 — це 1, в той час як 3÷2 — це 1,5. Тому кількість виживших значень завжди буде меншою за половину для непарної кількості кандидатів. Іншими словами, кількість значень, що відкидаються, в середньому буде половиною або більше, що трохи відходить від заданих умов. Це неприємна деталь.
(А якщо це вас не турбує, ймовірно, ви читаєте не той блог.)
Якщо ми вирішимо округляти вгору замість вниз у таких випадках, тобто використовувати Math.ceil замість Math.floor, це просто спричинить упередженість в інший бік. Випадковий вибір, яку саме реалізацію написати — навіть якщо вибір буде випадковим за допомогою кидання кубика або підкидання монети — залишить його з фіксованим біасом так чи інакше. (Варто зазначити, що «випадковість» і «випадковий» — це не синоніми: випадковість залежить від шансу, в той час як довільність визначається примхою. Наприклад, хоча коли саме сайт або додаток вирішить вийти вас із системи може здаватися випадковим, насправді це довільне рішення.)
Один — це невідомий недетермінований процес, інший — невідомий процес.)
xkcd: Випадкове число
Згідно з духом Thanos sort, рішення наших проблем полягає у випадковому виборі під час виконання програми, замість того, щоб жорстко кодувати рішення на етапі розробки.
function snap(values) {
const round = Math.random() < 0.5 ? Math.floor : Math.ceil;
const survivors = round(values.length / 2);
while (values.length > survivors) {
const toSnap = Math.floor(Math.random() * values.length);
values.splice(toSnap, 1);
}
}
Стратегію округлення (округлення вниз до floor або вгору до ceiling) обирають випадково (пам'ятаючи, що 0 ≤ Math.random() < 1), і потім її застосовують до результату ділення довжини. Це не має значення в разі парного ділення, але для непарного ділення приблизно половина випадків округлятиметься вниз, а інша половина — вгору.
(Зазначте, що використання лише Math.round не забезпечить бажаної поведінки: воно завжди округляє вгору для частин числа, що дорівнюють 0.5 і більше, і вниз в іншому випадку, що означає, що в разі непарного ділення воно завжди поводитиметься як Math.ceil.)
Половина шляху
Приділивши таку увагу деталям, щоб досягти половини шляху, варто також розглянути реалізацію, яка мимоволі пропускає цей момент.
Цей приклад базується на поширеній логічній помилці:
- Це правда: якщо половину елементів потрібно видалити, ймовірність видалення будь-якого елемента становить половину.
- Це не так: якщо ймовірність видалення елемента становить половину, то половина елементів буде видалена.
Різниця між цими формулюваннями проблеми — це різниця між кодом, показаним раніше, і наступним:
function snap(values) {
for (let toSnap = values.length - 1; toSnap \>= 0; --toSnap)
if (Math.random() \< 0.5)
values.splice(toSnap, 1);
}
Цей код проходить по елементах у зворотному порядку, вирішуючи випадковим чином, чи видаляти кожен елемент. Для масиву з парною кількістю елементів, чи буде це видаляти рівно половину елементів? Можливо, але швидше за все, ні.
Використовуючи реалізацію snap з попереднього розділу, ви вже на півдорозі; застосовуючи цю останню, ви живете на молитві.
Існує 4 можливі послідовності, коли ви підкидаєте чесну монету (50% ймовірність орел, 50% ймовірність решка) двічі чесним способом: HH, HT, TH, TT. Ймовірність того, що половина підкидів буде орел (тобто 1 орел) і половина решка (тобто 1 решка) дорівнює 2 з 4 (HT і TH), тобто 50%, а не 100%.
Отже, те, що не є правдою, це що ймовірність половини для окремої події означає, що половина всіх подій також матиме такий результат, будь то орел чи решка, виключення чи збереження.
function toss() {
return Math.round(Math.random()) ? 'H' : 'T';
}
Ймовірність точно рівного розподілу зменшується нижче 50%, коли N збільшується понад 2.
let tosses = [];
for (let flip = 0; flip !== N; ++flip)
tosses.push(toss());
Отже, залишаючи осторонь питання непарних довжин, загальна ймовірність того, що реалізація підкиду монети у функції snap усуне точно половину елементів для довгого масиву, значно менша за 50%, навіть попри те, що ймовірність усунення окремого елемента становить 50%. Ймовірність можна розрахувати як (N!/(½N)! ²)/2ᴺ.
Ви можете дослідити це самостійно експериментально. Навіть коли N буде всього 10, ви побачите, що ймовірність рівного розподілу знизиться до близько 25%.
До того часу, як N досягає 1000, ймовірність становить близько 2.5%.
1000 запусків з 10 монетами за допомогою Virtual Coin Tosser
Це нормально. Літерално. Коли N збільшується, ймовірнісне розподілення наближається до нормального (гаусового) розподілу. Це випливає з центральної теореми про обмеження:
Центральна теорема про обмеження (CLT) стверджує, що розподіл середніх значень вибірки наближається до нормального розподілу, коли розмір вибірки збільшується, незалежно від розподілу популяції.
Snip-snap
Є й інші можливі стратегії випадкового усунення, які все ще задовольняють наші умови та відповідають нашим очікуванням. Наприклад, замість того, щоб випадковим чином усувати елементи, поки ми не зменшимо кількість вдвічі, ми можемо випадковим чином вибирати, чи усунути першу половину, чи другу половину.
У Python цей буквальний підхід до бінарного відсічення можна виразити лаконічно так:
def snapped(values):
pivot = len(values) // 2
return values[:pivot] if choice([False, True]) else values[pivot:]
Дотримуючись стилю сортування за принципом "без зміщення" (out-of-place sorting) вбудованої функції sorted в Python, ми отримуємо наступну реалізацію сортування Thanos:
def thanos_sorted(values):
result = list(values)
while not is_sorted(result):
result = snapped(result)
return result
Хоча цей підхід до поділу на половини значно більш специфічний, ніж Сам "Щелчок", в якому немає поняття впорядкованого чи групованого усунення, він хоча б має прецедент в тому, як Танос "балансував" населення кожного світу, який він захоплював.
Замість лінійно-логарифмічного (linearithmic) найгіршого випадку, ми отримуємо логарифмічний, тобто тепер у нас O(log n) замість O(n log n) викликів до генератора випадкових чисел.
Це може здатися великим досягненням, але почуття балансу та пропорції є доречним, коли враховувати це вдосконалення, що виводить сортування з лінійності: це все ще вроджено неефективний та внутрішньо неповний спосіб сортування. Точно не для роботи (NSFW), тому не варто надто захоплюватися будь-якими очевидними оптимізаціями.
Напевно, немає нічого так безкорисного, як робити з великою ефективністю те, що не слід робити взагалі.
Якщо ми готові розглянути використання більш сталих стратегій для поділу на половини, немає причин залишатися обмеженими лише поділом на сусідні елементи. Наприклад, ми могли б вибирати між видаленням елементів з парних або непарних індексів:
def snapped(values):
return values[::2] if choice([False, True]) else values[1::2]
Звісно, використання більш обмеженої стратегії означає, що певні можливі впорядковані результати не будуть досяжними.
Попри це обмеження, такі підходи все одно зберігають основні характеристики сортування Таноса: (1) вони сортують шляхом поступового видалення половини елементів і (2) ця половина визначається випадковим чином.
Тим не менше, те, що не відповідає вимогам коректної реалізації, — це видалення однакових груп або шаблонів елементів без будь-якої випадковості. Наприклад, якщо код жорстко прописаний на те, щоб завжди видаляти першу половину або завжди видаляти елементи з парними індексами. Ці варіації не є просто більш специфічними реалізаціями алгоритму: це різні алгоритми. Хоча такі приклади і цікаві, накладення та закріплення переваги, яка не є випадковою і не є канонічною, робить їх передбачуваними варіантами dropsort, а не сортуванням Танося.
Випадковість є ключовою та однозначною характеристикою сортування Таноса з моменту його створення.
Плагін і працює
Роздуми про ці алгоритмічні варіації натякають, що ми могли б вивести конкретну стратегію "щипання" з функції та передавати обрану стратегію як параметр.
Це подібно до того, як випадковість можна було б витягти з bogosort, але на більш високому рівні, де весь крок трансформації (тобто дія сортування) алгоритму може бути параметризований, а не лише дані, які його живлять.
def sorted\_by(values, \*, sorter):
result = list(values)
while not is\_sorted(result):
result = sorter(result)
return result
Підхоплюючи раніше зроблену спостереження про структурну схожість сортування Таноса з перестановочним сортуванням і bogosort, функція sorted_by пропонує шаблон для сортування, де не використовується жоден проміжний стан, окрім раніше трансформованого вводу. Її можна викликати з кроком трансформації, sorter, який повторно застосовується до тих пір, поки результат не буде відсортований.
Наприклад, використовуючи будь-яку з варіацій snapped, показаних раніше, сортування Таноса можна реалізувати так:
def thanos\_sorted(values):
return sorted\_by(values, sorter=snapped)
Структура sorted_by не припускає ні випадковості, ні усунення елементів, тому це узагальнене шасі, яке підходить не тільки для сортування Таноса. Ми можемо викликати її з фіксованою стратегією усунення, наприклад, видаленням кожного другого елемента:
sorted\_by(values, sorter=lambda values: values[::2])
Або видаленням другої половини елементів:
sorted\_by(values, sorter=lambda values: values[:len(values) // 2])
Ми також можемо піти іншим шляхом і реалізувати версію з перемішуванням елементів для bogosort:
sorted\_by(values, sorter=lambda values: random.sample(values, len(values)))
Ми також можемо реалізувати перестановочне сортування і передати функцію перестановки як sorter.
Щоб реалізувати це в Python, потрібно вручну створити одноетапну перестановку, яка залежить лише від свого вхідного значення, а не від будь-якого додаткового стану ітерації. Це контрастує з функцією генератора permutations, яка зберігає стан, з якого вона поступово генерує перестановки. Операції next_permutation та prev_permutation в C++, натомість, використовують лексикографічний підхід, який також може бути використаний як основа для аргументу sorter до sorted_by.
Такий відкритий підхід до композиції — не розширення, що іноді плутається з композицією — відкриває багато можливостей… але може вважатися занадто складним і надмірним для езотеричних алгоритмів.
З іншого боку, надмірне ускладнення та перебільшення також можуть вважатися частиною повідомлення.
Право власності
Алгоритми можуть бути езотеричними, але ми маємо знати, що вони працюють. Що ж ми маємо на увазі під "працювати" для алгоритмів сортування? Безвтратне сортування — незалежно від того, чи це сортування бульбашкою чи богосортування — має два основні властивості:
- Результат повинен бути відсортованим.
- Результат повинен бути перестановкою оригінальних значень.
Коли запитують, люди зазвичай пам'ятають вказати першу властивість, але не другу.
Ми можемо використовувати властивості як основу для тверджень проти загальних прикладів — підхід, який застосовується в тестуванні на основі властивостей — але також можемо використовувати прості твердження щодо конкретних прикладів, щоб наочно та лаконічно продемонструвати і підтsorted([]) == []
assert permutation_sorted([42]) == [42]
assert permutation_sorted([42] * 3) == [42] * 3
assert permutation_sorted(range(10, 0, -1)) == list(range(1, 11))
assert permutation_sorted([3, 1, 4, 1, 5, 9]) == [1, 1, 3, 4, 5, 9]
```
Таким чином, списки, які є порожніми, містять одне значення або кілька однакових значень (наприклад, три входи числа 42), не змінюються після сортування. Список, що містить числа в порядку зростання, наприклад від 0 до 9 включно, також вже відсортований і, отже, не змінюється. Список, що містить числа в порядку спаду, наприклад від 10 до 1 включно, буде перевернутий.
Список з мішаними значеннями, включаючи дублікати, буде відсортований у порядку неперервного зростання, при цьому всі значення — а отже, й довжина — зберігаються. Тести для будь-якого безвтратного сортування будуть схожими, незалежно від того, чи є алгоритм естетичним чи ні.
Для чогось з втратою інформації, як у випадку з dropsort, однак, друга властивість не виконується: результат є перестановкою деяких, але не обов'язково всіх оригінальних значень. Значення в результаті визначаються як неперервні наступники. Результат зберігає порядок, в якому ці значення зустрічалися вхідних даних, що легше проілюструвати на прикладах:
assert dropsorted([]) == []
assert dropsorted([42]) == [42]
assert dropsorted([42] * 3) == [42] * 3
assert dropsorted(range(10)) == list(range(10))
assert dropsorted(range(10, 0, -1)) == [10]
assert dropsorted([3, 1, 4, 1, 5, 9]) == [3, 4, 5, 9]
(Відсутність) ефекту є однаковим для випадків, які вже відсортовані. Для не відсортованих початкових випадків результат можна передбачити, хоча й з втратою інформації.
Втрата є детермінованою, тобто її можна визначити за допомогою алгоритму, і вона може бути написана специфічно для конкретного вхідного прикладу.
А як щодо сортування Thanos? Для вже відсортованих випадків сортування все одно є операцією ідентичності, тобто результат буде таким самим, як і вхідні дані, як у випадках інших алгоритмів сортування:
assert thanos_sorted([]) == []
assert thanos_sorted([42]) == [42]
assert thanos_sorted([42] * 3) == [42] * 3
assert thanos_sorted(range(10)) == list(range(10))
Однак для не відсортованих випадків результат не завжди відомий заздалегідь. У випадку, коли дані відсортовані в зворотньому порядку, можна бути впевненим, що результат буде містити лише одне значення, оскільки вхід не має підпослідовностей, що зростають або рівних. Хоча значення і буде взяте з вхідних даних, конкретно яке саме — невідомо.
Це означає, що ми можемо написати
result = thanos_sorted(range(10, 0, -1))
assert len(result) == 1
assert result[0] in range(10, 0, -1)
У загальнішому випадку для змішаних вхідних даних ми можемо очікувати один або кілька елементів у результаті. Елементи в результаті з'являються в тій самій послідовності, в якій вони були у вхідних даних, але які саме елементи? Для будь-якого конкретного прикладу ми можемо лише перевірити властивості результату, а не конкретний результат:
- Результат повинен бути відсортованим.
- Для непорожніх вхідних даних результат також не повинен бути порожнім.
- Послідовність результату містить тільки елементи з вхідних даних, які з'являються не більше одного разу і в тій самій послідовності, в якій вони були у вхідних даних.
Прямий наступник елемента в результаті повинен бути прямим або непрямим наступником цього елемента у вхідних даних.
Припускаючи, що ми маємо функцію containsinsequence для вираження третьої властивості, ми тепер можемо написати
result = thanos_sorted([3, 1, 4, 1, 5, 9])
assert is_sorted(result)
assert len(result) in range(1, 4)
assert contains_in_sequence([3, 1, 4, 1, 5, 9], result)
Зазначте, що, незважаючи на всю свою випадковість, цей рівень перевірки властивостей не вимагається від bogosort, де випадковість впливає на процес, але не на результат.
Точки зору
Перший набір реалізацій, який ми розглядали в JavaScript, є типовим для імперативних мов: вони сортують через побічні ефекти, змінюючи надану популяцію значень на місці.
Другий набір реалізацій на Python є більш типовим для функціональних мов: вони повертають нову колекцію, що містить відсортований результат, залишаючи оригінальну популяцію незмінною.
Є третя можливість, пов’язана з другою опцією: повернути відсортований вигляд оригінальних значень. Теоретично вигляд незмінних значень можна вважати взаємозамінним з їх копією. На практиці, однак, референційна прозорість, яка передбачається такою взаємозамінністю, не підтримується в основних мовах програмування, що робить цю третю опцію відмінною від другої.
Якщо ми хочемо ефективний вигляд оригінальних значень, який не є просто слайсованою копією, ми повинні повертати неперервну підпослідовність значень.
Наш процес швидкої діметрації потребує знаходження відсортованої підпослідовності в межах оригінальної послідовності значень і повернення її початкової та кінцевої точок замість копії.
Використовуючи скорочений синтаксис шаблонної функції C++20 для зручності, але при цьому дотримуючись класичного підходу C++ щодо визначення послідовності через пару ітераторів, Thanos sort виглядатиме так:
auto thanos\_sort(auto begin, auto end)_sorted(lower, upper))
tie(lower, upper) = snap(lower, upper);
return pair(lower, upper);
}
Тут thanos_sort і snap повертають пари ітераторів як результат. Перше значення пари вказує на початок результатної послідовності, а друге — на один елемент після її кінця.
Утиліта tie дозволяє розкласти пару від snap на кілька змінних для ітераторів lower та upper.
Одна з уже розглянутих стратегій може бути реалізована як варіант для snap на основі перегляду: усунути першу або другу половину елементів, повертаючи ітератори, які обмежують залишену половину. Насправді, ми можемо трохи послабити це обмеження: нам не обов'язково, щоб усунута половина елементів була суміжною, лише залишок. Іншими словами, snap може повертати будь-який суміжний перегляд половини переданих елементів, будь-то з початку, середини чи кінця.
auto snap(auto begin, auto end)
{
auto population = end - begin;
auto survivors = population / 2;
auto new\_beginning = begin + rand() % (population - survivors);
return pair(new\_beginning, new\_beginning + survivors);
}
(Зверніть увагу, що цей код написано з припущенням, що begin та end є ітераторами для доступу до елементів за допомогою випадкових індексів.)
Це спрощення є лише для зручності синтаксису і не відображає необхідного обмеження. Щоб код працював з ітераторами для руху вперед (одноступінчастими, односторонніми ітераторами), потрібно замінити арифметичні операції на distance та next, як це належить.)
В деякому сенсі, це snap схожеshuffle](https://en.cppreference.com/w/cpp/algorithm/random_shuffle) в стандартній бібліотеці C++, яка також використовує ненависну функцію C rand. Якщо ми хочемо зробити це більше схожим на операцію shuffle в C++, ми повинні надати генератор випадкових чисел і налаштувати його відповідно до певного розподілу.
У цьому випадку нам не потрібно нічого складного, лише рівномірний розподіл цілих чисел:
auto snap(auto begin, auto end, auto && randomness)
{
auto population = end - begin;
auto survivors = population / 2;
uniform\_int\_distribution<> bounded(0, population - survivors - 1);
auto new\_start = begin + bounded(randomness);
return pair(new\_start, new\_start + survivors);
}
Щоб викликати snap, thanos_sort потрібно передати джерело випадковості, наприклад, генератор Mersenne Twister:
auto thanos\_sort(auto begin, auto end)
{
auto lower = begin, upper = end;
mt19937 randomness;
while (!is\_sorted(lower, upper))
tie(lower, upper) = snap(lower, upper, randomness);
return pair(lower, upper);
}
Якщо ви хочете, щоб це було більш випадковим або по-справжньому випадковим, екземпляр mt19937 можна ініціалізувати вручну.
Однак, як би ми не визначали thanos_sort, використання буде виглядати ось так:
const vector values {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9};
auto result = thanos\_sort(values.begin(), values.end());
Оголосивши початкову популяцію значень як const, ми можемо побачити, що сортування не руйнівне.
Щоб перевірити результат, ми можемо ітерувати від першого до другого ітератора, що зберігаються в отриманій парі.
for (auto examining = result.first; examining != result.second; ++examining)
cout << *examining << "\n";
Приклад того, що може вивести цей код:
1
5
9
Все виглядає добре… хіба що щодо використання. Члени first та second пари не є особливо інформативними, коли ми звикли розглядати діапазони ітераторів як begin та end. Код на C++, який використовує пари на різних рівнях (наприклад, пари пар) і для різних цілей, може бути неймовірно складним для розшифровки, коли потрібно проходити через шари доступів до first і second (існують кодові бази на C++, які б змусили 128-бітне шифрування позаздрити).
Ми також хочемо використовувати результат безпосередньо в ітерабельних контекстах, наприклад:
for (auto value: thanos_sort(values.begin(), values.end()))
cout << value << "\n";
Щоб бути використаним як ітерабельний діапазон, результат thanossort_ має підтримувати операції begin та end. Не дивно, що саме це пропонують інші типи переглядів (views) у C++, наприклад, stringview, _span і initializerlist_. І навіть менш дивно, що це лежить в основі бібліотеки діапазонів (ranges) C++20 (що концептуально схоже на Java Streams API або C# LINQ… але складніше). Саме тут ми будемо шукати охайне рішення для нашого коду.
Ми можемо взяти наш код і обгорнути його в легкий діапазон (range), щоб він як отримував, так і повертав діапазон:
auto thanos_sort(const auto & values)
{
auto [begin, end] = thanos_sort(values.begin(), values.end());
return subrange(begin, end);
}
Перегляд (subrange) знаходиться в просторі імен std::ranges і повертає діапазон, описаний початковою позицією та значенням-сторожем, яким у цьому випадку є ітератор, що вказує на позицію після кінця.
Це означає, що ми можемо написати наступне:
const vector values {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9};
auto result = thanos_sort(values);
for (auto value: result)
cout << value << "\n";
А також ось таке:
for (auto value: thanos_sort(values))
cout << value << "\n";
Подальша інтеграція з використанням діапазонів (ranges) можлива, але ми зупинимося на цьому, щоб не поглинутися в цю складну задачу.
Кінцева мета
Thanos sort — це гібридний алгоритм, який можна оцінити та захоплюватися ним у багатьох аспектах, не зводячи все до простого bogodropsort.
Як і з будь-яким езотеричним алгоритмом, це весело і провокативно, і ставить питання. Але це також підкреслює, наскільки багато нашого сприйняття алгоритму та його характеристик залежить від ряду виборів реалізації, які виходять за межі основної структури самого алгоритму.
Ступінь випадковості в реалізації, наприклад, є точкою реалізації, яку можна варіювати. Ми можемо рухати цей слайдер від випадкового вибору на рівні кожного елемента до обмеженої стратегії групування, яка усуває одну фіксовану половину чи іншу.
З точки зору вірності оригіналам MCU алгоритму, обидва підходи — на основі копії та на основі перегляду — є незнищувальними. Це збереження дозволяє відновити оригінальні елементи. Отже, усунуті значення можна відновити, відновивши їх назад за допомогою обміну змінною або завершення області видимості.
Перекладено з: Oh, Snap!