Сортирующие сети: компараторы, принцип нулей и единиц, битонная сортировка

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

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

Сеть из 28 компараторов сортирует восемь чисел (она появится во втором разборе). Ты хочешь убедиться, что она верна на ЛЮБОМ входе. Перебрать все перестановки восьми чисел - 8! = 40 320 прогонов. Но сеть сравнивает числа, а не перестановки: значения могут повторяться, быть дробными, отрицательными. Сколько прогонов достаточно, чтобы доказать, что сеть верна на всех входах сразу?

Ответь себе до чтения. Кажется, что бесконечно много: входов бесконечно много. Ответ - 256, и все они состоят только из нулей и единиц.

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

Сортировочная горка на железной дороге, где стрелки переключаются по заранее написанному расписанию. Каждая стрелка смотрит на два вагона на соседних путях и ставит тяжёлый на правый путь. Расписание не зависит от того, какие вагоны пришли: те же стрелки, в том же порядке, в каждый день. Если расписание хорошее, на выходе вагоны всегда по весу.

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

Механизм: сеть, слои и почему хватает нулей и единиц

Сеть - это n проводов и последовательность слоёв; в слое каждый провод участвует не больше чем в одном компараторе, поэтому все компараторы слоя срабатывают за один такт. Работа сети - число компараторов, глубина - число слоёв. В отличие от быстрой сортировки, план сравнений не зависит от данных: та же сеть годится для железа, для видеокарты и для векторных команд процессора. Там компаратор - пара операций min и max без ветвления; в программе ниже он для наглядности записан через if. Битонная сеть строится для n, равного степени двойки, - другие n дополняют проводами с бесконечностью (в программе - числом больше всех данных), а после сортировки отбрасывают: эти провода окажутся в конце; так сделано и в задаче главы.

Принцип нулей и единиц (Кнут приписывает его Бурициусу, 1954). Пусть сеть не сортирует какой-то вход: на выходе y[i] > y[i + 1]. Заменим каждое число входа на 0, если оно меньше y[i], и на 1 иначе. Компаратор коммутирует с любой неубывающей функцией f: «сначала сравнить, потом заменить» даёт то же, что «сначала заменить, потом сравнить», ведь f(min(a, b)) = min(f(a), f(b)) - неубывающая функция не меняет, какое из двух чисел меньше. Значит, на нулях и единицах сеть выдаст замены тех же выходов - и на позициях i, i + 1 окажутся 1 и 0, то есть неотсортированный 0-1 вход. Неверная сеть всегда проваливает какой-то вход из нулей и единиц - поэтому проверки всех 2ⁿ таких входов достаточно.

Битонная сортировка (Бэтчер, 1968) - сортировка слиянием, где слияние тоже сеть. Отсортированные половины блока длины k сравниваются «зеркально»: i против k − 1 − i. После такого слоя каждая половина блока - битонная последовательность (сначала растёт, потом падает), и все её элементы не больше элементов другой половины. Дальше половины доводят компараторами на расстояниях k/4, k/8, …, 1. Слияние блока длины k занимает log₂ k слоёв, блоки растут 2, 4, …, n - глубина 1 + 2 + … + log₂ n.

Правило

Сортирующая сеть - фиксированные слои компараторов; глубина - число слоёв, работа - число компараторов. Сеть верна на любых входах, если она сортирует все 2ⁿ входов из нулей и единиц. Битонная сортировка Бэтчера: глубина log₂ n · (log₂ n + 1) / 2, компараторов n/4 · log₂ n · (log₂ n + 1); на 8 входах - 6 и 24. Сеть глубины O(log n) существует (AKS, 1983), но её константы - тысячи, и на практике её не применяют.

Разбор: битонная сеть на восьми входах

Программа строит слои по описанию выше, проверяет сеть на всех 256 входах из нулей и единиц и прогоняет один обычный вход с повтором. Бит i числа m берётся арифметикой: m // 2 ** i % 2.

def bitonnaya(n):
    # слои компараторов [a, b]: после компаратора x[a] <= x[b], a < b
    sloi = []
    k = 2
    while k <= n:
        # первый шаг слияния блока длины k - «зеркальный»: i против k-1-i
        sloj = []
        for blok in range(0, n, k):
            for t in range(k // 2):
                sloj.append([blok + t, blok + k - 1 - t])
        sloi.append(sloj)
        j = k // 4
        while j >= 1:
            sloj = []
            for i in range(n):
                if i // j % 2 == 0:
                    sloj.append([i, i + j])
            sloi.append(sloj)
            j = j // 2
        k = k * 2
    return sloi

def progon(sloi, x):
    x = x[:]
    for sloj in sloi:
        for a, b in sloj:
            if x[a] > x[b]:
                x[a], x[b] = x[b], x[a]
    return x

def proverit_01(sloi, n):
    # принцип нулей и единиц: хватит всех 2^n входов из 0 и 1
    plohih = 0
    for m in range(2 ** n):
        x = []
        for i in range(n):
            x.append(m // 2 ** i % 2)
        y = progon(sloi, x)
        for i in range(n - 1):
            if y[i] > y[i + 1]:
                plohih = plohih + 1
                break
    return plohih

sloi = bitonnaya(8)
for s in sloi:
    print(s)
kompar = 0
for s in sloi:
    kompar = kompar + len(s)
print("глубина", len(sloi), "компараторов", kompar,
      "плохих 0-1 входов", proverit_01(sloi, 8))
print(progon(sloi, [5, 1, 7, 3, 3, 8, 2, 6]))

[[0, 1], [2, 3], [4, 5], [6, 7]]
[[0, 3], [1, 2], [4, 7], [5, 6]]
[[0, 1], [2, 3], [4, 5], [6, 7]]
[[0, 7], [1, 6], [2, 5], [3, 4]]
[[0, 2], [1, 3], [4, 6], [5, 7]]
[[0, 1], [2, 3], [4, 5], [6, 7]]
глубина 6 компараторов 24 плохих 0-1 входов 0
[1, 2, 3, 3, 5, 6, 7, 8]

Шесть слоёв по четыре компаратора - глубина 6, работа 24, как в формулах: 3 · 4 / 2 = 6 и 8/4 · 3 · 4 = 24. Ни один из 256 входов из нулей и единиц не провален, значит, по принципу сеть сортирует всё, в том числе вход с двумя тройками. Слои 2 и 4 - зеркальные: [0, 3], [1, 2] и [0, 7], [1, 6], [2, 5], [3, 4].

Для сравнения: обычная сортировка вставками на восьми числах - до 28 сравнений, и они идут друг за другом. Сеть делает 24 сравнения, но в шесть тактов.

Разбор: где случайные тесты слабее принципа

Сеть чётно-нечётных перестановок: слои по очереди сравнивают пары (0, 1), (2, 3), … и (1, 2), (3, 4), …. Ей нужно n слоёв. Что будет, если поставить на один меньше? Проверим двумя способами: всеми входами из нулей и единиц и пятьюстами случайными перестановками.

import random

def progon(sloi, x):
    x = x[:]
    for sloj in sloi:
        for a, b in sloj:
            if x[a] > x[b]:
                x[a], x[b] = x[b], x[a]
    return x

def otsortirovan(y):
    for i in range(len(y) - 1):
        if y[i] > y[i + 1]:
            return False
    return True

def plohie_01(sloi, n):
    spisok = []
    for m in range(2 ** n):
        x = []
        for i in range(n):
            x.append(m // 2 ** i % 2)
        if not otsortirovan(progon(sloi, x)):
            spisok.append(x)
    return spisok

def chet_nechet(n, sloev):
    # слои по очереди: пары (0,1),(2,3),... и (1,2),(3,4),...
    sloi = []
    for t in range(sloev):
        sloj = []
        for i in range(t % 2, n - 1, 2):
            sloj.append([i, i + 1])
        sloi.append(sloj)
    return sloi

random.seed(1)
for sloev in [8, 7]:
    sloi = chet_nechet(8, sloev)
    plohie = plohie_01(sloi, 8)
    promahov = 0
    for t in range(500):
        x = list(range(8))
        random.shuffle(x)
        if not otsortirovan(progon(sloi, x)):
            promahov = promahov + 1
    print(sloev, "слоёв, плохих 0-1 входов:", len(plohie))
    for x in plohie:
        print("   ", x)
    print("    не отсортировано случайных:", promahov, "из 500")

8 слоёв, плохих 0-1 входов: 0
    не отсортировано случайных: 0 из 500
7 слоёв, плохих 0-1 входов: 3
    [1, 1, 0, 0, 0, 0, 0, 0]
    [1, 1, 1, 1, 0, 0, 0, 0]
    [1, 1, 1, 1, 1, 1, 0, 0]
    не отсортировано случайных: 40 из 500

Восемь слоёв - ни одного провала. Семь слоёв - ровно три плохих входа из 256, и программа их называет. Все три начинаются с двух единиц подряд: левая единица в первом слое стоит рядом с равной и не двигается, её путь вправо начинается со слоя 3, и шести переходов до конца уже не хватает. Случайные перестановки тоже нашли ошибку, но только в восьми процентах прогонов. Для сети побольше доля может оказаться ничтожной, и тысяча случайных тестов пройдёт зелёной.

Разница в природе ответа. 256 входов из нулей и единиц - доказательство для всех входов сразу. Случайные перестановки - выборка из 8! = 40 320, а сами числа - вообще бесконечное множество.

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

Слой с общим проводом. Если в одном слое два компаратора делят провод, они не могут сработать одновременно, и «глубина 6» на деле окажется больше. Проверка слоя - каждый номер провода встречается не больше одного раза.

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

Неверное направление компаратора. Битонную сеть часто пишут с компараторами «по убыванию» в части блоков. Перепутанное направление ломает битонность, и сеть сортирует только часть входов.

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

Видеокарты сортируют короткие массивы битонной сетью: она без ветвлений, и все потоки варпа делают одно и то же. Векторизованные сортировки на процессоре (например, Highway VQSort и x86-simd-sort, на которую опирается NumPy) досортировывают маленькие блоки сетями прямо в векторных регистрах. В железе сеть компараторов сортирует пакеты в коммутаторах и сигналы в ПЛИС.

Принцип нулей и единиц - пример приёма, который переносится далеко за пределы сетей: для сетей слияния и выбора действуют свои принципы нулей и единиц, и доказывать их корректность на двоичных входах тоже достаточно.

Теперь сам

1. Сколько слоёв и компараторов у битонной сети на 16 входах? А у сети чётно-нечётных перестановок?
2. Сколько входов из нулей и единиц нужно проверить для сети на 12 проводах, и сколько перестановок?
3. Слой [0, 2], [1, 3], [2, 4] - что с ним не так?