Зовнішнє сортування

Зовнішнє сортування — це клас алгоритмів сортування, який може обробляти величезну кількість даних. Зовнішнє сортування потрібне, коли сортовані дані не входять у основну пам'ять обчислювального пристрою (RAM), а замість цього вони повинні знаходитися в повільній зовнішній пам'яті, як правило, на жорсткому диску. Зовнішнє сортування зазвичай використовує гібридну стратегію сортування-злиття. У фазі сортування, шматки даних, достатньо малих для розміщення в основній пам'яті, прочитуються, сортуються та виводяться до тимчасового файлу. У фазі злиття сортовані субфайли об'єднуються в один великий файл.

Зовнішнє сортування злиттям

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

1. Прочитати 100 МБ даних у основній пам'яті та сортувати за допомогою деякого звичайного методу, наприклад quicksort.
2. Зберегти відсортовані дані на диск.
3. Повторити кроки 1 і 2 до тих пір, поки всі дані не будуть відсортовані по 100 MB (є 900 МБ / 100 МБ = 9 разів), Які тепер потрібно об'єднати в один вихідний файл.
4. Прочитати перші 10 МБ (= 100 МБ / (9 шт. + 1)) кожного відсортованого шматка у вхідні буфери в основній пам'яті і виділіть залишкові 10 МБ для вихідного буфера. (На практиці це може забезпечити кращу продуктивність, щоб зробити вихідний буфер більшим, а вхідні буфери трохи меншими.)
5. Виконати сортування злиттям 9-ти відсортованих частин і зберегти результат у вихідному буфері. Кожного разу, коли заповнюється вихідний буфер, записувати його до останнього відсортованого файлу та очистити його. Кожного разу, коли будь-яка з 9 вхідних частин очищується, заповнити його наступними 10 МБ з с відповідних 100 МБ відсортованого фрагмента, доки не буде використано всі 10 фрагментів. Це ключовий крок, оскільки алгоритм злиття робить лише один прохід послідовно через кожну частину, кожний шматок даних не повинен бути повністю завантажений.

Особливості методу

Попередній приклад — це сортування в два кроки: спочатку сортування, а потім об'єднання. Сортування закінчується одиничним злиттям 9-ти частин, а не серією двосторонніх процесів злиття, як у типовому сортуванні злиття в пам'яті. Це відбувається тому, що кожене злиття передбачає читання та запис значення з диска і на нього.

Обмеження для одиничного злиття полягає в тому, що при збільшенні кількості фрагментів пам'ять буде розділена на більшу кількість частин, тому кожна з них буде меншою. Це спричиняє велику кількість процесів читання малих частин даних, ніж меншу кількість більших. Таким чином, для сортування, скажімо, 50 Гб у 100 МБ оперативної пам'яті, використовуючи одиничне злиття неефективно: пошук на диску необхідний для заповнення вхідних фрагментів даних кожного з 500 шт. займаює більшу частину часу. Використання двох злиттів дозволяє вирішити проблему. Тоді процес сортування може виглядати так:

1. Запуск початкового протоколу сортування.
2. Запуск першого злиття, яке об'єднує 25 шматків одночасно, в результаті чого виділяються 20 більших відсортованих фрагментів.
3. Запуск другого злиття, щоб об'єднати 20 нових фрагментів.

Як і у звичайному сортуванні, ефективний метод зовнішнього сортування вимагає часу O ( n log n ): експоненціальне збільшення розміру даних зумовдює лінійного збільшення кількості проходів. Використовуючи велику кількість пам'яті, надану сучасними комп'ютерами, логарифмічний фактор росте дуже повільно. До 500 Гб даних можна сортувати за допомогою 1 Гб основної пам'яті, перш ніж третє злиття стане вигідним, і значно більші об'єми даних, перш ніж в пригоді стане четверте злиття. Припустимо, що маємо диск з 200 MB / s читання/запису, час пошуку 20 мс, 1 Гб пам'яті, 500 Гб для сортування. Фаза злиття буде складатися з 500 частин по 2 МB, кожна з них витрачає по 250 мс на пошук, а потім читання та запис 500 ГБ. Буде витрачено 5000 секунд на пошук та 5000 секунд на перезапис. Використання двох пропусків, як описано вище, майже усунуло б час пошуку, але додасть ще 5000 секунд читання та запису, тому це приблизно точка беззбитковості між дво- і трипропускними віріантами сортування. Такі засоби, як твердотірні накопичувачі (SSD) також збільшують об'єм даних, які можна сортувати до того, як додаткові злиття стають вигідними.

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

Інші алгоритми

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

See also

• Mainframe sort merge

Посилання

• STXXL, an algorithm toolkit including external mergesort [Архівовано 24 листопада 2011 у Wayback Machine.]
• An external mergesort example [Архівовано 1 листопада 2015 у Wayback Machine.]
• A K-Way Merge Implementation [Архівовано 8 жовтня 2015 у Wayback Machine.]
• External-Memory Sorting in Java [Архівовано 24 грудня 2014 у Wayback Machine.]
• A sample pennysort implementation using Judy Arrays [Архівовано 27 лютого 2017 у Wayback Machine.]
• Sort Benchmark [Архівовано 13 січня 2012 у Wayback Machine.]