Многофазная сортировка слиянием

Если ты знаешь, почему при трёх файлах прогоны раскладывают по числам Фибоначчи, что такое фиктивные прогоны и когда многофазное слияние проигрывает, листай до «Теперь сам».

Как думаешь, куда девается проход

У тебя 21 отсортированный прогон и три файла, которые можно читать и писать только подряд, от начала к концу. Слияние по два: берёшь по прогону из двух файлов и пишешь результат в третий. Схема «разложить поровну, слить, разложить результат снова поровну» требует после каждого слияния ещё и переписать файл на два. Сколько раз данные пройдут через диск?

Ответь себе до чтения. Пять уровней слияния (⌈log₂ 21⌉ = 5) плюс четыре копирования между ними - девять проходов по всем данным. Многофазная схема на тех же трёх файлах обходится 4,57 прохода: она обходится без отдельного полного перераспределения данных между каждой парой фаз, сливая за фазу только часть серий. Само слияние всё равно читает и записывает данные; фиктивная серия может вызвать переписывание одной настоящей.

На что это похоже

Две колоды карт и пустое место на столе, третьей колоде больше лечь некуда. Если колоды равные, после слияния пар у тебя одна колода и пустые два места - чтобы слить снова, её придётся разложить обратно на две. А если колоды неравные - в одной 13 стопок, в другой 8, - сливаешь 8 пар на свободное место, и у тебя снова две колоды (5 стопок и 8 стопок) и одно пустое место. Раскладывать ничего не надо: остаток большей колоды сам становится вторым входом.

Механизм: фаза идёт до первого пустого входа

Модель из книги Макконнелла о внешней сортировке - файлы, доступные только подряд: создать прогоны, разложить их по файлам, а потом сливать пары прогонов, читая их одновременно из двух файлов. У него файлов четыре: два входа и два выхода, и выходы на следующем проходе меняются ролями со входами. Каждый проход читает все данные, проходов ⌈log₂ R⌉ при R прогонах.

Если файлов три, выход у слияния один. Фаза многофазного слияния: два непустых файла - входы, пустой - выход; сливаем по прогону из каждого входа, пока один из входов не опустеет. Опустевший файл становится выходом следующей фазы, а входами - вчерашний выход и остаток второго входа. Фаза читает не все данные, а только то, что успело слиться.

Когда это заканчивается одним прогоном? Последняя фаза сливает (1, 1) в один прогон. Пусть перед фазой во входах a ≥ b прогонов. Она сливает b пар: на выходе получается b слитых, в остатке большего - a−b. Как пара «больше, меньше» результат равен (max(b, a−b), min(b, a−b)); например, (7,3) переходит в (4,3).

Для простого обратного расписания выбираем шаги, у которых прежний выход не меньше остатка, то есть b ≥ a−b. Тогда пара уже упорядочена как (b,a−b), и один способ идти назад - (x,y) → (x+y,x): (1,1) ← (2,1) ← (3,2) ← (5,3) ← (8,5) ← (13,8). Это конкретное удобное расписание; произвольная раскладка может менять порядок файлов иначе.

Числа Фибоначчи - ряд 1, 1, 2, 3, 5, 8, 13, 21, 34, …, где каждое число - сумма двух предыдущих. Здесь они появляются не из любви к красивым рядам: обратный шаг (x, y) → (x + y, x) и есть правило «следующее - сумма двух предыдущих». Поэтому прогоны раскладывают по двум соседним числам Фибоначчи, а общее число прогонов в этой идеальной раскладке тоже выбирают числом Фибоначчи. Это удобное расписание, а не необходимое условие завершения: раскладка 7 и 3 тоже дойдёт до одного прогона, хотя 10 не число Фибоначчи. Ниже используем именно расписание Фибоначчи. Если прогонов меньше выбранной суммы, недостачу добирают фиктивными прогонами - пустыми, которые только числятся в файле.

При T файлах сливают по T − 1, и раскладка идёт по обобщённым числам Фибоначчи, где каждое - сумма T − 1 предыдущих; ниже мы разбираем три файла.

Правило

Многофазное слияние сливает прогоны из всех файлов, кроме одного, в оставшийся, пока не опустеет один из входов; опустевший файл становится выходом следующей фазы. Отдельного полного перераспределения между каждой парой фаз не требуется. В описанном расписании три файла используют соседние числа Фибоначчи и при необходимости фиктивные прогоны. Другую раскладку можно использовать, отдельно проверив её завершение одним прогоном.

Разбор: 21 прогон по фазам

Раскладка 13 и 8, третий файл пуст. В скобках - сколько исходных прогонов слилось в каждый прогон файла.

            файл A        файл B        файл C      прочитано
начало      13 × (1)      8 × (1)       -
фаза 1      5 × (1)       -             8 × (2)       16
фаза 2      -             5 × (3)       3 × (2)       15
фаза 3      3 × (5)       2 × (3)       -             15
фаза 4      1 × (5)       -             2 × (8)       16
фаза 5      -             1 × (13)      1 × (8)       13
фаза 6      1 × (21)      -             -             21
                                               всего  96

Фаза 1 сливает восемь пар (1) + (1) и оставляет в A пять прогонов. Фаза 2 сливает эти пять с пятью прогонами (2) из C, и в C остаются три. После первой фазы вчерашний выход C содержит восемь прогонов и становится большим входом следующей; остаток A с пятью прогонами - меньшим. Размер выхода определяется меньшим входом текущей фазы, а не следующей. Всего прочитано 96 исходных прогонов из 21 - данные прошли через диск 96 / 21 ≈ 4,57 раза. Это отношение объёмов верно для исходных прогонов одинаковой длины, как в программе ниже. Для разных длин надо складывать число действительно прочитанных элементов и делить на общий объём входа, а не считать прогоны одинаковыми единицами. Шесть фаз, но фазы короткие: ни одна, кроме последней, не трогает все данные.

Разбор: наивные схемы и прогоны не по Фибоначчи

Программа сортирует по-настоящему: 100 случайных чисел на прогон, файлы - списки прогонов, читаемые только с начала. Считает, сколько раз через слияние и копирование прошли данные (запись прогонов в начале у всех схем одинакова и не считается).

import random
from heapq import merge


def mnogofaznoe(runs):
    # три файла; серии раскладываются по двум соседним числам
    # Фибоначчи, недостающие - пустые «фиктивные» серии
    a, b = 1, 0
    while a + b < len(runs):
        a, b = a + b, a
    fikt = a + b - len(runs)
    f = [[[]] * fikt + runs[:a - fikt], runs[a - fikt:], []]
    prochitano = fazy = 0
    while sum(len(x) for x in f) > 1:
        vyh = [i for i in range(3) if not f[i]][0]
        x, y = [f[i] for i in range(3) if i != vyh]
        while x and y:              # сливаем, пока один вход не опустел
            s = list(merge(x.pop(0), y.pop(0)))
            prochitano += len(s)
            f[vyh].append(s)
        fazy += 1
    return [s for s in f if s][0][0], fazy, prochitano


def po_dva(runs, faylov):
    # 4 файла: два входа, два выхода; 3 файла: слить в один и
    # переписать его серии обратно на два - лишний проход копирования
    a, b = runs[0::2], runs[1::2]
    prochitano = prohody = 0
    while len(a) + len(b) > 1:
        slito = [list(merge(*p)) for p in zip(a, b)] + a[len(b):]
        prochitano += sum(len(s) for s in slito)
        prohody += 1
        a, b = slito[0::2], slito[1::2]
        if faylov == 3 and len(slito) > 1:
            prochitano += sum(len(s) for s in slito)
    return (a + b)[0], prohody, prochitano


rng = random.Random(5)
for R in [21, 20, 22, 23, 34, 35]:
    x = [rng.randint(0, 10 ** 6) for _ in range(R * 100)]
    runs = [sorted(x[s:s + 100]) for s in range(0, len(x), 100)]
    print("серий", R)
    vse = [["4 файла, по два", po_dva(runs, 4)],
           ["3 файла, по два", po_dva(runs, 3)],
           ["3 файла, Фибоначчи", mnogofaznoe(runs)]]
    for imya, (rez, f, ch) in vse:
        if R == 21 or imya != "3 файла, по два":
            print(f"  {imya:19} верно {rez == sorted(x)}  фаз {f}  "
                  f"данных прочитано {ch / len(x):.2f} раза")

серий 21
  4 файла, по два     верно True  фаз 5  данных прочитано 5.00 раза
  3 файла, по два     верно True  фаз 5  данных прочитано 9.00 раза
  3 файла, Фибоначчи  верно True  фаз 6  данных прочитано 4.57 раза
серий 20
  4 файла, по два     верно True  фаз 5  данных прочитано 5.00 раза
  3 файла, Фибоначчи  верно True  фаз 6  данных прочитано 4.50 раза
серий 22
  4 файла, по два     верно True  фаз 5  данных прочитано 5.00 раза
  3 файла, Фибоначчи  верно True  фаз 7  данных прочитано 5.14 раза
серий 23
  4 файла, по два     верно True  фаз 5  данных прочитано 5.00 раза
  3 файла, Фибоначчи  верно True  фаз 7  данных прочитано 5.13 раза
серий 34
  4 файла, по два     верно True  фаз 6  данных прочитано 6.00 раза
  3 файла, Фибоначчи  верно True  фаз 7  данных прочитано 5.29 раза
серий 35
  4 файла, по два     верно True  фаз 6  данных прочитано 6.00 раза
  3 файла, Фибоначчи  верно True  фаз 8  данных прочитано 5.89 раза

На 21 прогоне три файла по Фибоначчи читают данные 4,57 раза - меньше, чем четыре файла по два (5), и почти вдвое меньше наивной схемы на тех же трёх файлах (9: пять слияний и четыре копирования).

Граница правила видна на 22 прогонах. Ближайшая сумма соседних чисел Фибоначчи - 34, и программа добирает 12 фиктивных прогонов. Слияние с пустым прогоном - это переписывание настоящего прогона, фаза прибавилась, и 22 прогона стоят 5,14 прохода - больше, чем 5 у четырёх файлов. Сразу за числом Фибоначчи (21 → 22, 34 → 35) цена в показанных точках прыгает. Внутри промежутка она не обязана расти монотонно: при 23 прогонах программа даёт 5,13 прохода, немного меньше 5,14 при 22. Считай реальный объём чтений для своей раскладки. Где лежат фиктивные прогоны, тоже важно: здесь они все в начале большего файла и сливаются с настоящими; более аккуратная раскладка часть такого переписывания убирает.

Что ломается без этого

Три файла и равная раскладка. Каждое слияние по два оставляет один файл со всеми данными, и следующий проход начинается с копирования половины на другой файл - работа почти удваивается.

Раскладка почти поровну. Разложи 21 прогон как 11 и 10: фаза 1 сольёт 10 пар, и в одном файле останется один прогон, а в другом - десять двойных. Дальше каждая фаза сливает ровно одну пару: растущий прогон с очередным двойным, читая 3, 5, 7, …, 21. Фаз 11, прочитано 20 + 120 = 140 прогонов - 6,67 прохода вместо 4,57. Неравенство раскладки - не деталь, а суть метода.

Непроверенное расписание. Произвольная раскладка не обязана завершиться одним прогоном. Например, 4 и 4 дадут четыре прогона в единственном файле: два других пусты, и следующую фазу с двумя входами начать нельзя. Раскладка 7 и 3, напротив, доходит до одного прогона без фиктивных. Поэтому фиктивные прогоны нужны для выбранного здесь расписания Фибоначчи, а не для любого многофазного слияния. Фаза по определению длится до опустошения одного входа: завершиться с двумя непустыми входами она не может.

Зачем это в работе

Многофазная схема полезна при ограниченном числе независимых потоков и дорогом перераспределении прогонов. Файлы здесь играют роль последовательных лент: переключение ролей позволяет использовать освободившийся вход как следующий выход. Если памяти хватает на буферы широкого многопутевого слияния, сравни его стоимость с многофазным вариантом: меньшее число файлов само по себе не означает меньшее время. Отдельно считай чтения, записи, фиктивные прогоны и стоимость управления буферами.

Теперь сам

Три файла, 13 прогонов. Как их разложить, сколько будет фаз и сколько раз данные пройдут через слияние?