Алгоритми зовнішнього сортування за Д
Методи зовнішнього сортування за Д. Кнутом
Цікаві завдання виникають, якщо число записів, що сортуються, перевищує обсяг швидкодіючої ОЗУ. Зовнішнє сортування докорінно відмінна від внутрішньої (хоча в обох випадках необхідно розташувати записи даного файлу в зазначеному порядку), і пояснюється це тим, що час доступу до файлів на зовнішніх носіях нас дуже лімітує. Структура даних повинна бути такою, щоб порівняно повільні периферійні пристрої могли впоратися з потребами алгоритмів сортування. Тому більшість методів внутрішнього сортування (вставка, обмін, вибір тощо) фактично марна для зовнішнього сортування; необхідно розглянути всю проблему наново.
Припустимо, наприклад, що призначений для сортування файл складається з 5000 записів R 1, R2, …, R5000 довжиною по 20 слів (ключі R i можуть бути не такої довжини). Як бути, якщо у внутрішній пам'яті машини міститься одночасно лише 1000 із цих записів?
Відразу напрошується таке рішення: почати із сортування кожного з 5 підфайлів R 1 - R1000, R1001 - R2000, … , R4001 - R5000 окремо і потім злити отримані підфайли. На щастя, злиття оперує тільки дуже простими структурами даних, а саме лінійними списками, пройти які можна послідовним чином, як, наприклад, стеки або черги. Тому для злиття годяться найдешевші пристрої, що запам'ятовують.
Щойно описаний процес - внутрішнє сортування з наступним "зовнішнім злиттям" - дуже популярний, і, ймовірно, досить інтуїтивний, щоб пояснювати його.
Багатоколійне злиття та вибір із заміщенням
Нехай є Р зростаючих відрізків, тобто. послідовність записів, ключі яких розташовані в неубутньому порядку. Очевиднимспособом їхнього злиття буде наступний: подивитися на перші записи кожного відрізка і вибрати з них ту, якій відповідає мінімальний ключ; цей запис передається на вихід і виключається із вхідних даних, потім процес повторюється.
Поки Р не надто велике, цей вибір зручно здійснювати, просто виконуючи (Р-1) порівнянь для знаходження найменшого з поточних ключів. Але якщо, скажімо, Р і 8, то можна скоротити роботу, використовуючидерево вибору(докладніше про це - у розділі "Методи внутрішнього сортування" того ж видання),тоді щоразу потрібно » log2 P порівнянь (після початкового форматування дерева). Розглянемо, наприклад, чотириколійне злиття з дворівневим деревом вибору:
У цьому прикладі наприкінці кожного відрізка поміщений додатковий ключ Ґ, щоб злиття закінчувалося природно. Так як зовнішнє злиття зазвичай має справу з дуже довгими відрізками, то цей додатковий запис з ключем Ґ суттєво не збільшить довжину даних або обсяг роботи при злитті; крім того, такий "кінцевий" запис часто служить зручним способом поділу записів файлу.
У аналізованому процесі (рис. 1) кожен крок, крім першого, складається із заміщення найменшого елемента наступним елементом з цього ж відрізка та зміни відповідного шляху дерева вибору. Так, на кроці 2 змінюється вузла 3, які містили 087 на кроці 1; на кроці 3 змінюється вузла 3, що містили 15 4 на кроці 2, і т.д. Процес заміщення у дереві вибору одного ключа іншим називаєтьсявибором із заміщенням.
Ми можемо по-різному розглядати наведене чотириколійне злиття. З одного погляду воно еквівалентно двом двоколійним злиттям, виконуваним спільно, як співпрограми; кожен вузол дерева зображує одну з послідовностей, що використовуються у процесах злиття.Дерево вибору, по суті, використовується як пріоритетна черга з дисципліною "найменшим із включених першим виключається".
Рис.2 Турнір, у якому вибирається найменший ключ; використовується повне бінарне дерево, вузли якого пронумеровані від 1 до 23
Дерево програли. На малюнку 2 зображено повне бінарне дерево з 12 листками (квадратними) та 11 вузлами (круглими); у листі записані ключі, у вузлах - "переможці", якщо дерево розглядатиме як турнір для вибору найменшого ключа. Числа меншого розміру над кожним вузлом показують традиційний спосіб розподілу послідовних позицій пам'яті повного бінарного дерева.
Щоб визначити нове стан дерева вибору, зображеного на рис. 2, коли найменший ключ 061 буде замінений на інший ключ, потрібно розглянути тільки ключі 512, 084 і 154, і ніякі інші. Якщо інтерпретувати дерево як турнір, останні три ключі являтимуть собою тих, хто програв у матчах з гравцем 061. Це наводить на думку, що ми насправді маємо записати у внутрішні вузлипрограв у кожному матчі, а не переможця, тоді інформація , необхідна для зміни дерева, буде доступною.
Рис 3 Той же турнір, що і на рис.2, але показані переможці, що програли, а не; чемпіон знаходиться на самому верху
На рис. 3 зображено те саме дерево, що і на рис. 2, але замість переможців у ньому представлені переможені. Додатковий вузол із номером "0" доданий на вершині дерева для вказівки чемпіона турніру.
Насправді зовнішнім вузлам у нижній частині рис. 3 відповідатимуть дуже довгі записи, які у пам'яті ПК, а внутрішнім вузлам - покажчики ці записи. Зауважимо, що Р-шляхове злиття вимагає рівно Р зовнішніх і Р внутрішніх вузлів по одному в сусідніх групах, щонаводить на думку про більш ефективні методи розподілу пам'яті. Неважко бачити, як можна використовувати дерево програли для вибору із заміщенням.
Припустимо, що у нашому розпорядженні є три зовнішні пристрої Т1, Т2 та Т3. Тепер можна скористатися збалансованим злиттям, описаним вище Р=2 і Т=3. Воно набуває наступного вигляду:
Ш1: Розподілити початкові відрізки поперемінно на Т1, Т2 та Т3
Ш2: Злити відрізки з пристроїв Т1 та Т2 на Т3; потім зупинитися, якщо Т3 містить лише один відрізок.
Ш3: Скопіювати відрізки з Т3 поперемінно на Т1 і Т2 потім повернутися до кроку Ш2.
Перший прохід злиття приведе до S/2 відрізків (якщо спочатку їх було S) на Т3, другий - S/4 і т.д. Проходи копіювання в цій процедурі є небажаними, оскільки вони не зменшують кількості відрізків. Можна обійтися половиною копіювань, використовуючи двофазну процедуру:
А3: скопіюватиполовинувідрізків з Т3 на Т1
А4: Злити відрізки зі стрічок Т1 та Т3 на Т2; зупинитися, якщо Т2 містить лише один відрізок.
А5: Скопіюватиполовинувідрізків з Т2 на Т1. Повернутись до кроку А2.
Число проходів за всіма даними скоротилося з 2log 2 S до 3/2(log 2 S) + 1/2, тому що в кроках А3 та А5 виконується лише "половина проходу", тобто економиться близько 25% часу.
Цю ідею можна узагальнити на випадок Т стрічок за будь-якого Т і 3, використовуючи (Т-1)-шляхове злиття. Тоді у випадку чотирьох пристроїв, наприклад, потрібно близько 0.703log 2 S + 0.96 проходів за даними. Узагальнена схема використовує узагальнені числа Фібоначчі. Тепер потрібно вирішити кілька питань:
Яке правило приховано за точними фінобачівськими розподілами?
Що робити, якщо S не відповідає точному фінобачевськомурозподілу?
Як побудувати початковий прохід розподілу, щоб породжував потрібне розташування відрізків на пристроях?
Скільки проходів вимагатиме Т-стрічкове багатофазне злиття як функція від числа початкових відрізків?
Точні фінобаччі розподіли можна отримати, "прокручуючи" розглянуту схему у зворотний бік, циклічно переставляючи вміст пристроїв. У випадку, якщо покласти Р = Т - 1, розподілу в багатофазному злитті для Т пристроїв буде аналогічно відповідати числам Фінобаччі Р-го порядку. У точному розподілі n-го рівня на k-му пристрої буде:
Початкових відрізків для 1 K k P, а загальна кількість початкових відрізків на всіх пристроях буде, отже, дорівнює
Це вирішує питання про "точний фібоначчієвий розподіл". Але що ми повинні робити, якщо S не дорівнює точності t n за жодного n? Як спочатку помістити відрізки на пристрої?
Рис.4 Схема багатофазного злиття
Якщо S не є точним числом Фібоначчі (а чисел Фібоначчі не так і багато), то можна діяти, як у збалансованому Р-шляховому злитті, додаючи "фіктивні відрізки"; тому вважатимуться, що S, нарешті, буде точним. Способів додавання фіктивних відрізків декілька.
Інша основна схема, яка називається каскадним злиттям, насправді була відкрита раніше багатофазною. Зроблено це було Б. К. Бетцом та У. К. Катте у 1956 році.
На перший погляд може здатися, що каскадна схема - досить поганий варіант у порівнянні з багатофазною, так як стандартна багатофазна схема використовує весь час (Т - 1)-шляхове злиття, в той час, як каскадна використовує (Т - 1)-шляхове, (Т - 2)-шляховий, (Т - 3)-шляховий і т.д. Але насправді вона асимптотично краща,чим багатофазна, для 6 і більше пристроїв! Як ми бачили у п.2, високий порядок злиття не є гарантією ефективності. У таблиці 1 показано характеристики виконання каскадного злиття. Неважко вивести "точний розподіл" для каскадного злиття. Для шести пристроїв маємо такий порядок:
Таблиця 1. Характер поведінки каскадного злиття
Проходи (без копіювання)
Зазначимо цікаву властивість цих чисел: їх відносні величини є також довжинами діагоналей правильного (2Т-1)-кутника. Наприклад, п'ять діагоналей одинадцятикутника мають відносні довжини, дуже близькі до 190, 175, 146, 105 та 55! Крім того, відносні часи, що витрачаються на (Т-1)-шляхове злиття, (Т-2)-шляхове злиття, …, одноколійне злиття приблизно пропорційні квадратам довжин цих діагоналей.
Мал. 5 Каскадне злиття зі спеціальним розподілом
Припустимо, наприклад, що злиття використовується п'ять стрічок. Цей метод починає з запису по одному початковому відрізку на кожну з чотирьох стрічок і зливає їх (читаючи у зворотному напрямку) на п'яту стрічку. Знову відновлюється розподіл, цього разу циклічно зрушений на 1 вправо по відношенню до стрічок, і друге злиття дає ще один відрізок. Коли цим способом сформовано чотири відрізки, додаткове злиття створює відрізки А. Процес можна продовжувати, створюючи ще три відрізки А, зливаючи їх у чергові і т.д. доти, доки вичерпуються вихідні дані. Довжину вихідних даних наперед знати не потрібно.
Якщо число початкових відрізків є 4 m , то неважко бачити, що цей метод обробляє кожен запис рівно m+1 разів (один раз під час розподілу та m разів під час злиття). Якщо S лежить між 4 m-1 і 4 m, то можна за допомогою фіктивнихвідрізків збільшити S до 4 m; отже, загальний час сортування визначатиметься як log 4 S + 1 проходами за всіма даними. Це саме те, що досягається при збалансованому сортуванні навосьмистрічках; у загальному випадку осцилююча сортування з Т робочими стрічками еквівалентна збалансованого злиття з 2(Т - 1) стрічками. Якщо S виявляється ступенем Т - 1, то це найкращий варіант, який можна отримати при будь-якому методі з Т стрічками, так як тут досягається нижня оцінка. Але якщо S більше цього ступеня хоча б на одиницю, цей метод втрачає майже цілий прохід.
Деяке удосконалення методу було запропоновано в 1966 Деннісом Л. Бенчером, який назвав свою процедуру перехресним злиттям. Основна мета його полягає в тому, щоб відкласти злиття до тих пір, поки не буде накопичено більше відомостей про S.
Точний опис алгоритму Бенчера наводиться нижче на рис. 6. На жаль, відповідну процедуру складніше зрозуміти, ніж запрограмувати; Легше пояснити цей метод ПК, ніж програмісту! Частково це відбувається з тієї причини, що рекурсивний метод виражений в ітеративному вигляді і потім підданий певній оптимізації: часом необхідно кілька разів простежити за роботою алгоритму, щоб зрозуміти, що відбувається.
Рис.6 Осцилююче сортування з перехресним розподілом