Когда замер спорит с асимптотикой: константы и точка пересечения

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

Как думаешь, где граница

Сортировка вставками - Θ(n²), слиянием - Θ(n log n). С какого размера массива слияние, написанное на чистом Python, начинает обгонять вставки, тоже написанные на Python? Варианты: с 4, с 16, со 100, с 1000.

Ответь себе до чтения. Многие отвечают «почти сразу, асимптотика же». Замер на этом сайте - между 64 и 128.

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

Добраться на другой конец города можно пешком или на метро. Метро быстрее в пути, но до станции идти десять минут, а потом ещё ждать поезд. На два квартала пешком выгоднее, на десять километров - метро. Где именно граница, зависит не от скорости поезда в учебнике, а от того, сколько идти до станции именно у тебя.

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

Если T₁(n) = a · n² и T₂(n) = b · n · log₂ n, то первый быстрее, пока a · n < b · log₂ n, то есть пока n / log₂ n < b / a. Точка пересечения n* растёт вместе с отношением констант: вдвое большее b / a сдвигает её больше чем вдвое.

Откуда константы. У вставок на шаг внутреннего цикла - сравнение и сдвиг, всё внутри одного вызова. У слияния на каждый уровень рекурсии - вызовы функции, срезы (новые списки), append; на маленьком куске эти накладные расходы больше самой работы. В C вызов дешёв, и вставки выигрывают до 10-20 элементов; в Python вызов функции стоит как десятки сравнений - и граница уезжает к сотне.

Модель стоимости курса - «каждое действие одинаково» - ловит форму кривых, но не отношение констант: она одинаково оценивает вызов функции и сравнение двух чисел.

Правило

Асимптотика решает на больших n; где большие начинаются, решают константы: квадратичный алгоритм выигрывает, пока n / log₂ n < b / a. Константы зависят от машины и языка, поэтому точку пересечения находят замером на целевой машине, а модель стоимости даёт лишь порядок величины.

Разбор: точка пересечения в модели

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

import random

dejstvij = [0]

def vstavkami(a):
    a = a[:]
    dejstvij[0] = dejstvij[0] + len(a)          # копия
    for i in range(1, len(a)):
        x = a[i]
        j = i - 1
        while j >= 0 and x < a[j]:
            a[j + 1] = a[j]
            j = j - 1
            dejstvij[0] = dejstvij[0] + 2       # сравнение и сдвиг
        a[j + 1] = x
        dejstvij[0] = dejstvij[0] + 2   # запись x и последнее сравнение
    return a

def sliyaniem(a):
    dejstvij[0] = dejstvij[0] + 1               # вызов функции
    if len(a) <= 1:
        return a
    m = len(a) // 2
    l = sliyaniem(a[:m])
    r = sliyaniem(a[m:])
    dejstvij[0] = dejstvij[0] + len(a)          # два среза - копии
    out = []
    i = 0
    j = 0
    while i < len(l) and j < len(r):
        if r[j] < l[i]:
            out.append(r[j])
            j = j + 1
        else:
            out.append(l[i])
            i = i + 1
        dejstvij[0] = dejstvij[0] + 2           # сравнение и запись
    dejstvij[0] = dejstvij[0] + len(l) - i + len(r) - j   # хвосты
    while i < len(l):
        out.append(l[i])
        i = i + 1
    while j < len(r):
        out.append(r[j])
        j = j + 1
    return out

random.seed(1)
for n in [8, 16, 32, 64, 128, 256]:
    a = []
    for k in range(n):
        a.append(random.random())
    dejstvij[0] = 0
    vstavkami(a)
    v = dejstvij[0]
    dejstvij[0] = 0
    sliyaniem(a)
    print(n, "вставками", v, "слиянием", dejstvij[0])

8 вставками 44 слиянием 79
16 вставками 152 слиянием 205
32 вставками 412 слиянием 497
64 вставками 2050 слиянием 1195
128 вставками 7464 слиянием 2783
256 вставками 32134 слиянием 6336

В модели вставки выигрывают до 32 элементов, на 64 уже проигрывают почти вдвое. Точка пересечения - между 32 и 64.

Разбор: точка пересечения на машине

Те же два алгоритма на настоящем Python 3.12, лучшее из пяти замеров:

import random
import timeit


def vstavkami(a):
    a = a[:]
    for i in range(1, len(a)):
        x = a[i]
        j = i - 1
        while j >= 0 and x < a[j]:
            a[j + 1] = a[j]
            j = j - 1
        a[j + 1] = x
    return a


def sliyaniem(a):
    if len(a) <= 1:
        return a
    m = len(a) // 2
    l = sliyaniem(a[:m])
    r = sliyaniem(a[m:])
    out = []
    i = j = 0
    while i < len(l) and j < len(r):
        if r[j] < l[i]:
            out.append(r[j])
            j = j + 1
        else:
            out.append(l[i])
            i = i + 1
    out.extend(l[i:])
    out.extend(r[j:])
    return out


random.seed(1)
for n in [8, 16, 32, 64, 128, 256]:
    a = [random.random() for _ in range(n)]
    k = max(1, 20000 // n)
    v = min(timeit.repeat(lambda: vstavkami(a), number=k, repeat=5)) / k
    s = min(timeit.repeat(lambda: sliyaniem(a), number=k, repeat=5)) / k
    print(f"{n:>4}  вставками {v * 1e6:7.1f} мкс",
          f" слиянием {s * 1e6:7.1f} мкс")

   8  вставками     1.8 мкс  слиянием     8.6 мкс
  16  вставками     5.6 мкс  слиянием    20.1 мкс
  32  вставками    15.0 мкс  слиянием    44.6 мкс
  64  вставками    72.9 мкс  слиянием   102.0 мкс
 128  вставками   265.0 мкс  слиянием   227.6 мкс
 256  вставками  1141.4 мкс  слиянием   491.8 мкс

На машине граница - между 64 и 128, вдвое дальше, чем в модели. На восьми элементах вставки быстрее впятеро, а модель обещала меньше чем вдвое (44 против 79). Модель считала вызов функции и срез за одно действие, а в CPython вызов sliyaniem с созданием двух списков-срезов стоит как десятки сравнений. Граница правила «модель стоимости предсказывает выбор»: она верно предсказала, КТО выиграет на больших и на маленьких n, но ошиблась вдвое в том, ГДЕ граница.

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

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

Порог, перенесённый с другой машины. Константа из статьи про C перенесена в Python - и гибрид режет массив там, где переход ещё невыгоден.

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

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

Почти каждый быстрый алгоритм в библиотеках - гибрид с порогом: вставки внутри сортировок (16 в libstdc++, minrun 32-64 в Timsort - до этой длины кусок собирают вставками), умножение Карацубы, которое переходит на школьное ниже нескольких десятков машинных слов, быстрое преобразование Фурье с прямыми формулами на маленьких кусках. Каждый такой порог найден замером. Когда пишешь свой гибрид, порог - это параметр, который подбирают опытом на целевой машине, а не выводят из формулы.

Теперь сам

1. T₁ = 2n², T₂ = 50 · n · log₂ n. До какого n из степеней двойки выигрывает первый?
2. Почему на восьми элементах вставки обгоняют слияние на машине впятеро, а в модели - меньше чем вдвое?
3. Гибриду на Python с порогом «вставки до 16» замер показал, что выгоднее 64. Противоречит ли это libstdc++, где порог 16?