Introsort и pdqsort: быстрая сортировка со страховками

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

Как думаешь, можно ли сломать медиану трёх

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

Ответь себе до чтения. Можно, и не перебором входов: разбор покажет программу, которая строит такой вход за один прогон самой сортировки.

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

Лотерея, где ты каждый раз тянешь билет-опорный, надеясь на середину. Честный барабан почти всегда даёт что-то среднее. А если барабан крутит противник и решает, что написано на билете, только когда ты его развернул, он каждый раз скажет «почти самый маленький». Защита - не угадывать лучше, а следить за собой: если тянешь уже слишком долго, бросить лотерею и пойти надёжной дорогой, пусть и чуть более медленной.

Механизм: противник и страховка

Противник Макилроя («A Killer Adversary for Quicksort», 1999). Значения элементов поначалу не заданы - это «газ», он больше всего твёрдого. Когда сортировка сравнивает два газовых элемента, противник замораживает один из них в следующее по порядку маленькое значение. Какой - подсказывает сама сортировка: разбиение сравнивает все элементы с опорным, поэтому газовый элемент, который участвовал в прошлом сравнении и остался газом, - вероятный опорный (в программе это kandidat). Его и замораживают маленьким. Опорный получается почти минимальным, и разбиение отщепляет по два-три элемента (меньше медианы трёх всегда хотя бы один). Ответы противника непротиворечивы, значит, после прогона они складываются в обычный массив, и та же сортировка на нём повторит все сравнения. Против почти любой детерминированной быстрой сортировки противник одинаково хорош: ему не надо знать, как выбирается опорный. Исключение - точная медиана за линию (медиана медиан из раздела о порядковых статистиках): с ней разбиение всегда пополам, но её константа слишком велика для сортировки.

Introsort (Дэвид Массер, 1997). Быстрая сортировка со счётчиком глубины: каждое разбиение уменьшает запас на единицу, начальный запас - 2⌊log₂ n⌋. Запас кончился - текущий кусок сортируется пирамидальной (O(m log m) на куске длины m, без дополнительной памяти). Куски до 16 элементов сортировка не трогает, а в конце досортировывает весь массив вставками одним проходом (программа урока добивает каждый кусок сразу - для счёта сравнений это почти то же). В libstdc++ это __introsort_loop с __lg(n) * 2 и _S_threshold = 16.

Pdqsort (pattern-defeating quicksort, Орсон Петерс) - introsort с тремя добавками.

• Плохое разбиение - меньшая сторона короче 1/8 куска. Тогда несколько элементов на фиксированных местах переставляются, чтобы сломать шаблон противника. Запас плохих разбиений - log₂ n, и он передаётся вниз по рекурсии, как запас глубины у introsort: кончился на какой-то ветви - этот кусок идёт в пирамидальную.
• Узнавание порядка. Если разбиение не сделало ни одного обмена, кусок, вероятно, уже упорядочен - его пробуют добить вставками, которые сдаются после небольшого числа сдвигов. На строго возрастающем или убывающем входе, по замерам автора, время линейное.
• Разбиение блоками (приём BlockQuicksort Эделькампа и Вайса): индексы элементов «не на своей стороне» копятся в буферах по 64 без условных переходов, и процессор не ошибается в предсказании ветвлений.

Правило

Быструю сортировку, выбирающую опорный дёшево и детерминированно (по нескольким элементам), противник загоняет в Θ(n²) при любом таком правиле. Introsort ограничивает глубину 2⌊log₂ n⌋ и уходит в пирамидальную: O(n log n) гарантированно. Pdqsort добавляет борьбу с плохими разбиениями, линейное время на упорядоченных входах и разбиение без ветвлений. Устойчивости нет ни у одного - в библиотеках рядом всегда есть отдельная устойчивая сортировка.

Разбор: противник против медианы трёх

Быстрая сортировка с медианой первого, среднего и последнего, куски до 16 - вставками. Сначала противник строит вход, потом сортируем случайный вход и вход-убийцу - без защиты глубины и с ней.

import math
import random

schet = [0]

def sortirovat(a, menshe, s_zashchitoj):
    # быстрая: опорный - медиана первого, среднего и последнего;
    # куски до 16 - вставками; с защитой глубина не больше 2·log₂ n
    predel = -1
    if s_zashchitoj:
        predel = 2 * int(math.log2(len(a)))
    bystraya(a, 0, len(a) - 1, menshe, predel)

def vstavkami(a, lo, hi, menshe):
    for i in range(lo + 1, hi + 1):
        x = a[i]
        j = i - 1
        while j >= lo and menshe(x, a[j]):
            a[j + 1] = a[j]
            j = j - 1
        a[j + 1] = x

def piramidalnaya(a, lo, hi, menshe):
    n = hi - lo + 1
    for start in range(n // 2 - 1, -1, -1):
        prosejat(a, lo, start, n, menshe)
    for konec in range(n - 1, 0, -1):
        a[lo], a[lo + konec] = a[lo + konec], a[lo]
        prosejat(a, lo, 0, konec, menshe)

def prosejat(a, lo, i, n, menshe):
    while 2 * i + 1 < n:
        c = 2 * i + 1
        if c + 1 < n and menshe(a[lo + c], a[lo + c + 1]):
            c = c + 1
        if not menshe(a[lo + i], a[lo + c]):
            return
        a[lo + i], a[lo + c] = a[lo + c], a[lo + i]
        i = c

def bystraya(a, lo, hi, menshe, predel):
    while hi - lo + 1 > 16:
        if predel == 0:
            piramidalnaya(a, lo, hi, menshe)
            return
        predel = predel - 1
        m = (lo + hi) // 2
        if menshe(a[m], a[lo]):
            a[m], a[lo] = a[lo], a[m]
        if menshe(a[hi], a[lo]):
            a[hi], a[lo] = a[lo], a[hi]
        if menshe(a[hi], a[m]):
            a[hi], a[m] = a[m], a[hi]
        a[m], a[hi - 1] = a[hi - 1], a[m]      # опорный - перед концом
        p = a[hi - 1]
        i = lo
        for j in range(lo, hi - 1):
            if menshe(a[j], p):
                a[i], a[j] = a[j], a[i]
                i = i + 1
        a[i], a[hi - 1] = a[hi - 1], a[i]
        bystraya(a, lo, i - 1, menshe, predel)
        lo = i + 1
    vstavkami(a, lo, hi, menshe)

# Противник Макилроя: значения не заданы заранее («газ»), и каждое
# сравнение двух газовых элементов он решает так, чтобы опорный
# оказался как можно меньше
n = 200
znach = [n] * n                     # n - «газ», больше любого твёрдого
tverdyh = [0]
kandidat = [-1]

def protivnik(x, y):
    schet[0] = schet[0] + 1
    if znach[x] == n and znach[y] == n:
        if x == kandidat[0]:
            znach[x] = tverdyh[0]
        else:
            znach[y] = tverdyh[0]
        tverdyh[0] = tverdyh[0] + 1
    if znach[x] == n:
        kandidat[0] = x
    elif znach[y] == n:
        kandidat[0] = y
    return znach[x] < znach[y]

def prosto(x, y):
    schet[0] = schet[0] + 1
    return x < y

sortirovat(list(range(n)), protivnik, False)
for i in range(n):
    if znach[i] == n:               # газ, оставшийся до конца, - твёрдый
        znach[i] = tverdyh[0]
        tverdyh[0] = tverdyh[0] + 1
ubijca = znach[:]
for imya, vhod in [["случайные", list(range(n))], ["убийца", ubijca]]:
    if imya == "случайные":
        random.seed(4)
        random.shuffle(vhod)
    for zashchita in [False, True]:
        schet[0] = 0
        a = vhod[:]
        sortirovat(a, prosto, zashchita)
        print(imya, "защита глубины:", zashchita, "сравнений", schet[0],
              "отсортировано", a == sorted(vhod))

случайные защита глубины: False сравнений 1574 отсортировано True
случайные защита глубины: True сравнений 1574 отсортировано True
убийца защита глубины: False сравнений 10135 отсортировано True
убийца защита глубины: True сравнений 4664 отсортировано True

На случайных данных защита не включается: глубина и так около log₂ n. На входе-убийце без защиты - 10 135 сравнений, почти n² / 4 = 10 000: каждое разбиение отщепляет единицы. С защитой - 4664: после 14 разбиений вглубь (2⌊log₂ 200⌋ = 14) остаток уходит в пирамидальную.

Разбор: страховка стоит константу, а не асимптотику

4664 сравнения - втрое больше, чем на случайных данных. Страховка не делает убийцу безвредным: пирамидальная сортировка медленнее быстрой в два-три раза из-за константы и плохой локальности. Но разрыв растёт по-разному. На миллионе элементов квадрат - около 2,5 · 10¹¹ сравнений, минуты процессора даже в C и часы в Python, а introsort на том же входе - порядка 4 · 10⁷ сравнений, в тысячи раз меньше. Граница правила: «introsort защищён» значит «не хуже n log n с константой побольше», а не «так же быстр, как на случайных».

Отсюда и выбор Python: sorted - Timsort, слиянием, у него нет опорного и нет противника: худший случай O(n log n) при любом входе, а сравнения из урока 1 показали, что на случайных данных он почти у нижней границы.

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

Атака сложностью. Сервис сортирует присланные клиентом данные самописной быстрой сортировкой с детерминированным опорным. Злоумышленник один раз прогоняет противника локально и шлёт вход-убийцу: запрос на сто тысяч элементов - это 2,5 · 10⁹ сравнений, секунды процессора в C и минуты в Python. Тот же класс, что HashDoS из раздела про хеширование. Защита - библиотечная сортировка с гарантией или случайный опорный.

Устойчивость, которой нет. std::sort, sort.Slice в Go и sort_unstable в Rust переставляют равные элементы. Многоключевая сортировка «сначала по вторичному, потом по первичному» на них ломается молча; для неё есть std::stable_sort, sort.SliceStable, slice::sort.

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

Вопрос «какая сортировка в стандартной библиотеке» имеет разные ответы в разных языках, и от ответа зависят гарантии. CPython: Timsort с powersort, устойчиво. C++ (libstdc++): std::sort - introsort, stable_sort - слиянием. Java: объекты - Timsort, примитивы - двухопорная быстрая сортировка Ярославского с вставками, слиянием серий и пирамидальной в запасе. Go с 1.19: sort.Sort - pdqsort. Rust с 1.81: sort_unstable - ipnsort (потомок pdqsort), sort - driftsort (устойчивая, слиянием). Новые реализации в Rust ещё и могут остановить программу с ошибкой, заметив, что сравнение не задаёт порядка, - вместо тихого мусора, как с NaN в уроке 1.

Теперь сам

1. Какой запас глубины выдаст introsort для n = 10⁶?
2. Почему случайный выбор опорного защищает от противника Макилроя, а медиана трёх - нет?
3. Где pdqsort выигрывает у introsort на почти упорядоченном массиве?