Timsort изнутри: серии, minrun и вставки двоичным поиском

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

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

Список из ста тысяч чисел уже отсортирован, и его снова отдают в sorted. Нижняя граница сортировки сравнениями - log₂ n! ≈ 1,5 миллиона. Сколько сравнений сделает sorted? А если список отсортирован по убыванию?

Ответь себе до чтения. Если «полтора миллиона, сортировка же» - разбор покажет 99 999 в обоих случаях. Нижняя граница говорит о худшем входе, а sorted смотрит на вход, который ему дали.

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

Библиотекарь расставляет вернувшиеся книги. Он не берёт их по одной: сначала замечает, что первые двадцать лежат уже по алфавиту, следующие пятнадцать - по алфавиту, но задом наперёд (переворачивает стопку), а дальше три книги вразнобой - их он вставляет в соседнюю стопку на место. Потом сливает стопки попарно. Если все книги вернули по порядку, работы - одно пролистывание.

Механизм: серии, minrun и вставки

Проход Timsort (list_sort_impl в Objects/listobject.c) повторяет три шага, пока массив не кончится.

1. Найти серию (count_run). Сравнить два первых элемента. Если второй меньше - серия убывающая, она длится, пока каждый следующий СТРОГО меньше; найденную серию разворачивают на месте. Иначе серия неубывающая, длится, пока следующий не меньше. Строгость нужна для устойчивости: разворот равных поменял бы их порядок. С Python 3.13 убывающая серия может содержать равные - их куски разворачиваются заранее, и общий разворот возвращает им исходный порядок.
2. Добить короткую серию до minrun элементов вставками: место для следующего элемента ищется двоичным поиском (log₂ от длины куска сравнений), потом хвост сдвигается. Сравнения в Python дороги - это вызов __lt__, а сдвиг ссылок - быстрый memmove, поэтому вставки на коротком куске выгодны.
3. Положить серию на стек и, может быть, слить её с соседями - правило слияний разберём в третьем уроке главы.

minrun - старшие 6 битов n, плюс единица, если среди отброшенных битов была хоть одна единица. Для n < 64 это само n: короткий список становится одной серией - готовый за n − 1 сравнение, остальное добивается вставками.

Правило

Timsort режет массив на серии: неубывающие и строго убывающие (их разворачивает). Короткую серию добивает до minrun вставками с двоичным поиском. minrun - старшие 6 битов n (плюс 1, если отброшены единицы), от 32 до 64 (при n < 64 - само n), так что n / minrun - степень двойки или чуть меньше. На уже упорядоченном входе - одна серия и n − 1 сравнение.

Разбор: какой minrun и сколько серий

Сначала сама формула и число серий, которое она даёт на случайных данных (там почти все серии будут длины minrun, последняя - остаток):

def minrun(n):
    # старшие 6 битов n плюс 1, если среди отброшенных была единица
    r = 0
    while n >= 64:
        # n & 1 - младший бит; r | ... станет 1, если 1 был хоть раз
        r = r | (n & 1)
        n = n >> 1          # деление на 2 нацело: младший бит уходит
    return n + r

for n in [63, 64, 65, 100, 2112, 1000000]:
    m = minrun(n)
    print(n, "minrun", m, "серий по minrun:", round(n / m, 1))

63 minrun 63 серий по minrun: 1.0
64 minrun 32 серий по minrun: 2.0
65 minrun 33 серий по minrun: 2.0
100 minrun 50 серий по minrun: 2.0
2112 minrun 33 серий по minrun: 64.0
1000000 minrun 62 серий по minrun: 16129.0

2112 - пример из документации CPython: с minrun = 32 получилось бы 66 серий, 64 из них слились бы идеально, а две лишние в конце пришлось бы сливать с огромным куском - лишние сравнения и копирование всего массива ради 64 элементов. С 33 серий ровно 64. На миллионе - 16 129 серий по 62 и ещё одна из двух элементов, всего 16 130, чуть меньше 2¹⁴ = 16 384: крупные слияния снова почти поровну.

Теперь сам проход на четырёх входах по 200 элементов (minrun(200) = 50):

import random

def serii(a, mr):
    # проход Timsort: серия по возрастанию или строго по убыванию
    # (убывающую разворачиваем); короткую добиваем вставками до mr
    a = a[:]
    i = 0
    dliny = []
    sravnenij = 0
    while i < len(a):
        j = i + 1
        if j < len(a):
            sravnenij = sravnenij + 1
            if a[j] < a[j - 1]:
                while j + 1 < len(a):
                    sravnenij = sravnenij + 1
                    if not a[j + 1] < a[j]:
                        break
                    j = j + 1
                lo = i
                hi = j
                while lo < hi:               # разворот на месте
                    a[lo], a[hi] = a[hi], a[lo]
                    lo = lo + 1
                    hi = hi - 1
            else:
                while j + 1 < len(a):
                    sravnenij = sravnenij + 1
                    if a[j + 1] < a[j]:
                        break
                    j = j + 1
        konec = j + 1
        if konec - i < mr:
            konec = min(i + mr, len(a))
            for k in range(j + 1, konec):   # вставка двоичным поиском
                x = a[k]
                lo = i
                hi = k
                while lo < hi:
                    mid = (lo + hi) // 2
                    sravnenij = sravnenij + 1
                    if x < a[mid]:
                        hi = mid
                    else:                # равный - после стоящего:
                        lo = mid + 1     # так равные сохраняют порядок
                for s in range(k, lo, -1):
                    a[s] = a[s - 1]
                a[lo] = x
        dliny.append(konec - i)
        i = konec
    return [dliny, sravnenij]

random.seed(5)
n = 200
peremeshany = list(range(1000))
random.shuffle(peremeshany)
nabory = [["по возрастанию", list(range(n))],
          ["по убыванию", list(range(n, 0, -1))],
          ["пила из 4 зубцов", list(range(50)) * 4],
          ["случайные", peremeshany[:n]]]
for imya, a in nabory:
    r = serii(a, 50)                # minrun(200) = 50
    print(imya, "- серии", r[0], "сравнений", r[1])

по возрастанию - серии [200] сравнений 199
по убыванию - серии [200] сравнений 199
пила из 4 зубцов - серии [50, 50, 50, 50] сравнений 199
случайные - серии [50, 50, 50, 50] сравнений 864

Готовый и обратный порядок - одна серия, 199 сравнений, слияний не будет вовсе. Пила из четырёх зубцов - четыре готовые серии за те же 199 сравнений. Случайные данные дают те же четыре серии по 50, но их пришлось собирать вставками: 864 сравнения - около 4,3 на элемент. Это и есть цена двоичного поиска: k-й элемент ищет место среди k уже стоящих за ≈ log₂ k сравнений, а сумма log₂ k по k до 50 - это log₂ 50! ≈ 214 на кусок, четыре куска - около 860.

Разбор: сравнения настоящего sorted

Посчитаем сравнения на настоящем Python 3.12: обёртка над ключом прибавляет единицу при каждом вызове __lt__.

import random


class Klyuch:
    # обёртка считает каждое сравнение, которое делает сортировка
    schet = 0

    def __init__(self, x):
        self.x = x

    def __lt__(self, drugoj):
        Klyuch.schet += 1
        return self.x < drugoj.x


def sravnenij(dannye):
    Klyuch.schet = 0
    # key=Klyuch: каждый элемент один раз обёрнут, сравниваются обёртки
    sorted(dannye, key=Klyuch)
    return Klyuch.schet


n = 100000
random.seed(1)
sluchajnye = random.sample(range(n), n)
naboru = {
    "по возрастанию": list(range(n)),
    "по убыванию": list(range(n, 0, -1)),
    "случайные": sluchajnye,
    "две серии": list(range(0, n, 2)) + list(range(1, n, 2)),
    "возрастание + 100 случайных":
        list(range(n)) + random.sample(range(n), 100),
}
for imya in naboru:
    print(imya, sravnenij(naboru[imya]))

по возрастанию 99999
по убыванию 99999
случайные 1528982
две серии 199998
возрастание + 100 случайных 102580

Готовые данные - n − 1. Случайные - 1 528 982 при нижней границе log₂ 100000! ≈ 1 516 704: перерасход 0,8%. Это граница правила «Timsort адаптивен»: на случайных данных выигрыша от адаптивности нет, и тогда важно, что он остаётся почти оптимальным. «Две серии» - чётные, потом нечётные: два прохода по n − 1 сравнению, поиск серий и одно слияние. Сто случайных чисел в хвосте отсортированных ста тысяч почти ничего не стоят: 2581 сравнение сверх n − 1.

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

NaN в списке чисел. Любое сравнение с NaN ложно, и серия «по возрастанию» не прерывается там, где должна:

nan = float("nan")
print(sorted([3.0, nan, 1.0, 2.0]))
print(sorted([nan, 3.0, 1.0, 2.0]))
print(sorted([3.0, 1.0, nan, 2.0, 0.5]))

[3.0, nan, 1.0, 2.0]
[nan, 1.0, 2.0, 3.0]
[0.5, 1.0, 2.0, 3.0, nan]

Первый результат не отсортирован вовсе, и ошибки нет. Сортировка верит, что < - строгий порядок; NaN это нарушает. Лечение - отфильтровать или заменить NaN до сортировки, либо ключ key=lambda x: (x != x, x): x != x истинно только у NaN, поэтому у чисел ключ (False, x), у NaN - (True, nan), и кортежи с False встают раньше: числа сортируются между собой, NaN уходят в конец.

Дорогой __lt__. Сравнение - вызов метода. Если ключ сравнивает сложные объекты, лучше один раз вычислить ключ-число через key=: ключи считаются по одному разу на элемент, а сравнений на случайных данных в 15 раз больше.

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

Данные из жизни редко случайны: журналы почти упорядочены по времени, выгрузки склеены из отсортированных кусков, к отсортированной таблице дописали десяток строк. На таких данных sorted работает почти за линию, и пересортировать «на всякий случай» почти ничего не стоит. Поэтому слияние двух отсортированных списков в Python пишут просто как sorted(a + b): Timsort найдёт две серии и сольёт их за n сравнений, а не за n log n.

Теперь сам

1. Чему равен minrun для n = 1000 и n = 4096?
2. Список [5, 4, 3, 3, 2, 1], Python 3.12, minrun = 6. Сколько сравнений сделает поиск первой серии, какой она будет длины и что Timsort сделает дальше?
3. Почему серия «по убыванию» в Python 3.12 строгая, а «по возрастанию» - нет?