Сложность по замерам

Во сколько раз дольше перемножить два числа, если каждое вдвое длиннее? По школьному правилу — вчетверо: каждая цифра одного числа умножается на каждую цифру другого. Python на числах в сотни тысяч бит отвечает иначе: втрое. На логарифмических осях время ложится на прямую с наклоном около 1,58, а log₂ 3 ≈ 1,585 — след алгоритма Карацубы, о котором в программе не сказано ни слова. Ниже семь операций, измеренных на Python и Go. Угадайте, как растёт каждая, и проверьте по наклону и по таблице под графиком.

Число над каждым отрезком — его наклон: во сколько раз выросло время, если записать это в степени роста n. Наклоны соседних отрезков скачут, и верить одному отрезку нельзя. Таблица ниже графика делает другое: делит время на шесть кандидатов и показывает, какое частное почти не меняется. Попробуйте «Умножение: повтор» на Python и на Go — там спрятана ловушка, в которую попал первый вариант замера для этой статьи.

Идея

Если время растёт как c·n^k, то ln T = ln c + k·ln n: на осях, где по обеим отложены логарифмы, это прямая, и её наклон — показатель k. Множитель c — скорость машины и языка — только сдвигает прямую вверх или вниз. Поэтому Python и Go в сцене дают на умножении один наклон при разнице во времени в разы: показатель принадлежит алгоритму. Наклон отрезка между двумя замерами

$$k_{12} = \frac{\ln(T_2/T_1)}{\ln(n_2/n_1)},$$

а тест удвоения из статьи об O-большом и главы курса — его частный случай: при n₂ = 2n₁ это просто log₂ отношения времён.

Наклон подсказывает, с какого кандидата начать, но не ставит диагноз. Диагноз ставит проверка отношением: время делят на кандидата — n, n log n, n², 2ⁿ — и смотрят на частное на больших n. У верного кандидата оно почти постоянно, у неверного ползёт вверх или вниз. Экспоненты проверяют на полулогарифмических осях: там они — прямые.

Наклон: что он знает и чего не знает

У степени наклон один на всех n. У остальных функций он свой в каждой точке, и это полезно понимать заранее.

Отсюда три следствия, и все видны в сцене.

n log n выглядит как n^1,1. На тысяче элементов наклон n log n — 1,14, на миллионе — 1,07, ровно 1,1 он при n = e¹⁰ ≈ 22 000. Логарифмический множитель прячется в десятых долях наклона, а округление его стирает: сортировка «растёт линейно». В курсе алгоритмов Седжвика и Уэйна это сказано прямо: тест удвоения логарифмических множителей не различает.

Экспонента не прямая. Наклон 2ⁿ растёт вместе с n, и на лог-лог осях график всё круче, как у «Подмножеств». Зато на полулогарифмических осях, где логарифм только у времени, ln 2ⁿ = n ln 2 — прямая. Её наклон — логарифм множителя на шаг: n на единицу больше — время вдвое. А n! гнётся вверх даже там: отношение n!/(n − 1)! = n растёт, это хуже любой экспоненты.

Один отрезок — это два замера и их шум. Если каждый замер ошибается на 10 %, наклон отрезка между n и 2n может уйти на ±0,3: log₂(1,1/0,9) ≈ 0,29. Наклон по многим точкам надёжнее, а надёжнее всего — то, что проверяет форму целиком.

Когда n log n не отличить от степени

Насколько похожи n log n и n^1,1? Подберём множитель c так, чтобы c·n^1,1 шла как можно ближе к n log n на выбранном отрезке, и посмотрим, как далеко они расходятся. Двигайте границы отрезка и показатель.

От тысячи до миллиона они расходятся не больше чем на ±3,1 % — меньше обычного шума замера. Чтобы разница выросла до ±8 %, нужен отрезок от тысячи до миллиарда, и даже там найдётся показатель, 1,079, который ближе к n log n, чем 1,1. Шесть порядков n на одной машине почти никогда не измерить. Вывод неприятный, но честный: по одним секундам n log n не отличить от n^1,08. Логарифм в ответе даёт знание алгоритма — замер только подтверждает, что ничего хуже не спряталось.

Проверка отношением

Возьмём кандидата f и поделим каждое время на f(n). Если кандидат верен, частное — это c с шумом: оно стоит на месте. Если рост быстрее кандидата, частное растёт; если медленнее — падает. В таблице сцены у каждого кандидата нарисовано, как идёт частное от малых n к большим, и записан его разброс — отношение наибольшего значения к наименьшему на верхней половине размеров.

Почему верхней половины? Потому что на малых n время портят постоянные расходы: вызов функции, проверки, выделение памяти. В «Вставке в начало» на Python они видны прямо: работа растёт как n², а наклон на первых отрезках — около 1,8 и только к большим n подбирается к 2. Сумма a·n + b·n² выглядит степенью только там, где второе слагаемое задавило первое.

Разброс к тому же отвечает на конкретный вопрос. Частные помещаются в коридор c·(1 ± r) при каком-нибудь c ровно тогда, когда разброс не больше (1 + r)/(1 − r). Разброс 1,22 означает «все замеры в пределах ±10 % от одной формулы», разброс 1,5 — «не лучше ±20 %». Это и есть задача в конце статьи.

Где замер врёт

Малые n. Постоянные расходы занижают показатель. Мерить нужно там, где один запуск длится хотя бы миллисекунды, а выводы делать по большим n.

Память. Пока данные помещаются в кэш процессора, каждое обращение почти бесплатно; когда перестают — дорожает в разы. На графике это ступенька: в «Сортировке» на Go наклон на одном-двух отрезках подскакивает выше 1,5, а дальше снова держится около 1,1 — в этих местах массив перестаёт помещаться в очередной уровень кэша. Подробнее об этой стене — в статье «Данные, удобные кэшу».

Данные. Сложность зависит не только от размера входа. «Сортировка готового» растёт линейно: Timsort в Python находит готовые отсортированные куски, pdqsort в Go замечает готовый порядок, и оба проходят массив один раз. Замер на удобных данных говорит об этих данных, а не о худшем случае.

Хуже, когда данные неудобны незаметно. Первый вариант замера умножения для этой статьи показал в Go наклон 1,2 и время в 19 раз меньше нынешнего на двух миллионах бит. Байты чисел брались из младших битов линейного конгруэнтного генератора, а младшие 8 бит такого генератора по модулю 2³² повторяются каждые 256 шагов. Числа вышли периодическими, и их половины совпадали. Карацуба в Go вычисляет среднее слагаемое как (x₀ − x₁)·(y₁ − y₀) + z₀ + z₂, и у таких чисел разности почти нулевые: третье умножение достаётся даром, рекурсия идёт в две ветки вместо трёх, а рост падает почти до n log n. Python ничего не заметил: в CPython то же слагаемое считается через суммы, (a_h + a_l)(b_h + b_l), и одинаковые половины ему не помогают. Ряд «Умножение: повтор» в сцене воспроизводит эту ошибку нарочно. Ни один из замеров не выглядел подозрительно — подозрительным было только расхождение языков.

Шум. Соседние процессы, частота процессора, сборка мусора. Лечится повторами и минимумом или медианой — об этом статья «Как честно измерить скорость». На наклон шум действует сильнее, чем на само время: он входит в разность двух логарифмов.

Код

Первая программа не меряет, а судит. Четыре «загадочных» набора замеров с шумом до 8 % — n log n, n^1,585, квадрат с заметной линейной частью и 2ⁿ — и для каждого: наклоны отрезков, наклон по верхней половине и проверка отношением. В конце — близнецы из второй сцены.

A: n from 1000 to 1024000
  local slopes: 1.05 1.17 1.04 1.26 0.89 1.12 1.22 1.07 1.03 1.04
  slope over the upper half: 1.10
  ratio test: n log n x1.12, n x1.40, n^1.585 x5.43
  verdict: n log n

Наклоны отрезков в наборе A гуляют от 0,89 до 1,26, хотя шум всего 8 %. Наклон по верхней половине — 1,10, и округление сказало бы «линейно». Проверка отношением различает: у n log n частное разбросано на 12 %, у n — на 40 %. На таком отрезке, в три порядка, это ещё получается. Набор C — квадрат плюс линейная часть: наклоны идут от 1,3 к 2,1, и даже на верхней половине разброс частного у n² — 1,45. Это предупреждение: квадрат с большим линейным слагаемым на малых n выглядит чем угодно.

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

Сколько стоит замер

Удвоение n обходится дёшево. Пусть время растёт как n^k, и последний запуск длится B. Предыдущий — в 2^k раз короче, тот, что перед ним, — ещё в 2^k, и все вместе они стоят не больше

$$B\left(1 + 2^{-k} + 2^{-2k} + \dots\right) = B \cdot \frac{2^k}{2^k - 1}.$$

Для линейного роста это 2B, для квадрата — 4/3 B, для куба — 8/7 B. Для экспоненты, где n растёт на единицу, а время умножается на b, сумма — B·b/(b − 1). Значит, весь замер стоит O(B): примерно столько же, сколько самый долгий запуск. Повторы умножают это на число попыток, а порог в 2 мс на размер добавляет по нескольку миллисекунд на каждый малый n. Сама проверка отношением — O(число кандидатов × число замеров): мгновенно.

Где это работает

Олимпиады и собеседования. Прежде чем отправлять решение, его прогоняют на n, 2n, 4n на случайных и на худших входах. Если время каждый раз растёт вчетверо, а ограничение — 10⁵, ждать вердикта не нужно. Как перевести шаги в секунды, рассказывает статья «Сколько операций в секунду».

Поиск мест, которые растут не так. В 2007 году Саймон Голдсмит, Алекс Эйкен и Дэниел Уилкерсон описали инструмент trend-prof: он запускает программу на входах разного размера, считает, сколько раз выполнился каждый базовый блок кода, и подгоняет к этим счётчикам степенные законы. Блок, у которого показатель больше ожидаемого, — кандидат в ошибку производительности, даже если на тестовых входах он ещё ничего не стоит. Счётчики вместо секунд избавляют от шума — это та же мысль, что и подсчёт шагов в статье об O-большом.

Скрытая сложность библиотек. Перевод большого целого числа в десятичную строку CPython долго делал за квадратичное время. В 2022 году это признали уязвимостью — CVE-2020-10735: длинная строка цифр в запросе надолго занимала процессор сервера, — и Python по умолчанию ограничил такие преобразования 4300 цифрами. Ни в одной строке пользовательского кода квадрата не было: он был в int() и str(). Замер на нескольких размерах находит такие места раньше атакующего.

История

Тест удвоения как привычку закрепили учебники: в «Алгоритмах» Седжвика и Уэйна программа DoublingRatio печатает время и отношение времён при удвоении n, а показатель читатель угадывает по отношению — с оговоркой, что логарифмических множителей так не увидеть. Подбор степенных законов по замерам вырос в отдельную область — экспериментальную алгоритмику; её обзор — книга Catherine McGeoch «A Guide to Experimental Algorithmics» (2012).

А показатель 1,585 из первой сцены — сам из истории о росте. В 1960 году Андрей Колмогоров на своём семинаре предположил, что быстрее чем за n² два n-значных числа не перемножить. Через неделю 23-летний студент Анатолий Карацуба нашёл способ обойтись тремя умножениями половин вместо четырёх: отсюда n^log₂3. Подробно — в статье об умножении Карацубы.

Задачи

Таблица замеров чужой программы и восемь кандидатов. Наклон округлять бесполезно: в первом же примере n log n притворяется линейным. Во втором примере — настоящий замер умножения из этой статьи.