Внешняя сортировка: прогоны и многопутевое слияние

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

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

Нужно отсортировать 1024 гигабайта, оперативной памяти - 16 гигабайт. Обычная сортировка слиянием «по два» - сколько раз она перечитает все данные с диска?

Ответь себе до чтения. Прогонов по 16 гигабайт - 64, слияние по два - шесть проходов, плюс проход на прогоны: семь раз по 1024 гигабайта. Многопутевое слияние сливает все 64 прогона разом - и обходится двумя проходами.

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

Шестьдесят четыре отсортированные стопки карточек и стол, на котором помещается шестьдесят четыре карточки. Сливать стопки по две - много раз перекладывать все карточки. А можно положить на стол верхнюю карточку каждой стопки и всё время брать самую маленькую из лежащих: взял - на её место кладёшь следующую из той же стопки. Одного прохода хватает, чтобы собрать всё в одну отсортированную стопку.

На диске вместо карточки на столе лежит целый блок от каждой стопки: стол - это память, и блоков в неё помещается M / B.

Механизм: две фазы

Прогоны. Читаем M элементов, сортируем в памяти любой сортировкой, пишем - 2N / B обращений на весь файл. Получается ⌈N / M⌉ отсортированных прогонов.

Многопутевое слияние. В памяти по одному блоку от каждого из k прогонов и блок для вывода, то есть (k + 1) · B ≤ M, отсюда k ≈ M / B − 1. Берём наименьший из k текущих элементов (кучей - за log k), переносим в вывод; опустел блок прогона - дочитываем следующий, заполнился вывод - записываем. Каждый проход читает и пишет всё: 2N / B. Проходов ⌈log_k(N / M)⌉. Если прогонов не больше M / B − 1, то есть примерно при N ≤ M² / B, проход один: при M = 16 ГБ и блоке в мегабайт это 256 терабайт.

Выбор с замещением удлиняет прогоны. В памяти M элементов; выводим наименьший из тех, что не меньше последнего выведенного, а на его место читаем следующий. Если новый меньше последнего выведенного, он «замораживается» до следующего прогона. На случайных данных прогоны выходят в среднем 2M (рассуждение Кнута о снегоочистителе), на отсортированных - один прогон на весь файл.

Правило

Внешняя сортировка: прогоны по M элементов (один проход), затем слияние по k ≈ M / B прогонов за проход. Цена 2N/B · (1 + ⌈log_k(N/M)⌉) блочных обращений при k = M/B − 1 путях - по порядку роста это и нижняя граница для сортировки сравнениями. Примерно при N ≤ M² / B хватает одного прохода слияния. Выбор с замещением даёт прогоны около 2M на случайных данных.

Разбор: двухпутевое и многопутевое слияние

Маленькая модель, где всё видно: 600 чисел, память на 30, блок 5 - двадцать прогонов. Программа держит прогоны в списках Python, чтобы данные было видно, а обращения считает так, как их делал бы алгоритм с памятью M: блок читается, когда буфер прогона опустел, и пишется, когда заполнился буфер вывода.

import random

def vneshnyaya(x, M, B, k):
    # прогоны: читаем по M элементов, сортируем в памяти, пишем обратно
    obrashchenij = 2 * len(x) // B
    progony = []
    for s in range(0, len(x), M):
        progony.append(sorted(x[s:s + M]))
    prohodov = 0
    while len(progony) > 1:
        # k-путевое слияние: в памяти по блоку от каждого прогона и блок
        # вывода; блок читается, когда буфер прогона опустел, и пишется,
        # когда заполнился буфер вывода
        novye = []
        for g in range(0, len(progony), k):
            gruppa = progony[g:g + k]
            poz = [0] * len(gruppa)
            obrashchenij = obrashchenij + len(gruppa)
            vyhod = []
            while True:
                r = -1
                for q in range(len(gruppa)):
                    if poz[q] < len(gruppa[q]):
                        golova = gruppa[q][poz[q]]
                        if r == -1 or golova < gruppa[r][poz[r]]:
                            r = q
                if r == -1:
                    break
                vyhod.append(gruppa[r][poz[r]])
                poz[r] = poz[r] + 1
                if len(vyhod) % B == 0:
                    obrashchenij = obrashchenij + 1
                if poz[r] % B == 0 and poz[r] < len(gruppa[r]):
                    obrashchenij = obrashchenij + 1
            novye.append(vyhod)
        progony = novye
        prohodov = prohodov + 1
    return [progony[0] == sorted(x), prohodov, obrashchenij]

random.seed(6)
x = []
for i in range(600):
    x.append(random.randint(0, 10 ** 6))
M = 30
B = 5
print("N =", len(x), "M =", M, "B =", B, "прогонов", len(x) // M)
print("путей  верно  проходов  обращений")
for k in [2, M // B - 1]:
    print(k, vneshnyaya(x, M, B, k))

N = 600 M = 30 B = 5 прогонов 20
путей  верно  проходов  обращений
2 [True, 5, 1440]
5 [True, 2, 720]

Двухпутевое слияние - пять проходов (⌈log₂ 20⌉) и 1440 обращений. Пятипутевое (M / B − 1 = 5) - два прохода и 720 обращений, вдвое меньше. Обе цифры совпадают с формулой: 2 · 600 / 5 = 240 обращений за проход, умножить на 1 + 5 и на 1 + 2. На настоящих размерах разница больше: при M / B в тысячи слияние почти всегда укладывается в один проход, а двухпутевое делает десяток.

Разбор: насколько длинные прогоны даёт выбор с замещением

Память на 20 элементов, тысяча чисел. Считаем длины прогонов на случайных, отсортированных и обратно-отсортированных данных.

import random

def zameshchenie(x, M):
    # в памяти M элементов; выводим наименьший из тех, что не меньше
    # последнего выведенного; меньшие ждут следующего прогона
    pamyat = x[:M]
    sled = M
    dliny = []
    tekushchij = 0
    poslednij = None
    zamorozheny = []
    while len(pamyat) > 0:
        luchshij = -1
        for q in range(len(pamyat)):
            if luchshij == -1 or pamyat[q] < pamyat[luchshij]:
                luchshij = q
        v = pamyat.pop(luchshij)
        tekushchij = tekushchij + 1
        poslednij = v
        if sled < len(x):
            if x[sled] >= poslednij:
                pamyat.append(x[sled])
            else:
                zamorozheny.append(x[sled])
            sled = sled + 1
        if len(pamyat) == 0:
            dliny.append(tekushchij)
            tekushchij = 0
            pamyat = zamorozheny
            zamorozheny = []
    return dliny

random.seed(3)
x = []
for i in range(1000):
    x.append(random.randint(0, 10 ** 6))
M = 20
d = zameshchenie(x, M)
print("случайные: прогонов", len(d),
      "средняя длина", round(sum(d) / len(d), 1))
print("по возрастанию:", zameshchenie(sorted(x), M))
d = zameshchenie(sorted(x, reverse=True), M)
print("по убыванию: прогонов", len(d), "длины", d[:4], "...")

случайные: прогонов 26 средняя длина 38.5
по возрастанию: [1000]
по убыванию: прогонов 50 длины [20, 20, 20, 20] ...

Случайные данные - средний прогон 38,5, почти 2M = 40: вдвое длиннее, чем при «прочитать, отсортировать, записать», значит, прогонов вдвое меньше. Отсортированный вход - один прогон на всю тысячу: сортировать нечего. Обратный порядок - худший случай, прогоны ровно по M: каждый новый элемент меньше выведенного и замораживается. Минимум из M элементов здесь ищется перебором, чтобы не загромождать программу; в настоящей реализации это куча.

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

Слияние по два на больших данных. Сортировка 1024 гигабайт делает семь проходов вместо двух - и работает в 3,5 раза дольше, хотя «тоже O(N log N)».

Слишком много путей. Если k · B больше памяти, блоки буферов перестают помещаться, и каждое чтение становится случайным доступом. Число путей ограничено памятью.

Быстрая сортировка прямо на диске. Разбиение по опорному элементу читает и пишет вразброс; на диске это случайный доступ. Внешнюю сортировку строят на слиянии, потому что слияние - это проходы.

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

ORDER BY по таблице больше work_mem в PostgreSQL - внешняя сортировка: прогоны сортируются в памяти и сливаются многопутевым слиянием. Любопытная деталь: с версии 9.6 PostgreSQL формирует прогоны быстрой сортировкой, а в 11 убрал выбор с замещением совсем - кеш процессора оказался важнее длины прогонов. DuckDB с версии 1.4 сортирует в две фазы с параллельным слиянием и уходит на диск, если не хватает памяти. Утилита sort в Unix сортирует файлы любого размера тем же способом, складывая прогоны во временный каталог.

Теперь сам

1. N = 10⁹ элементов, M = 10⁷, B = 10⁴. Сколько прогонов, сколько путей, сколько проходов слияния?
2. Хватит ли одного прохода слияния для 100 ГБ при памяти 1 ГБ и блоке 1 МБ?
3. Почему выбор с замещением на обратном порядке даёт прогоны ровно по M?