Опыт с удвоением: показатель роста по замерам

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

Как думаешь, что это за функция

Функция из чужой библиотеки, исходника нет. Замеры:

n = 1000:    8.5 мс
n = 2000:   31.7 мс
n = 4000:  122.1 мс
n = 8000:  491.2 мс

Линейная, n log n или квадратичная? И сколько она будет работать на 64 000 элементах?

Ответь себе до чтения. Каждое удвоение умножает время почти на 4 - это квадрат, и на 64 000 будет около 491 · 4³ ≈ 31 000 мс, полминуты. Ниже - как превратить такой взгляд в число и где он подводит.

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

Пробная поездка перед дальней дорогой. Проехал 10 км за 12 минут, 20 км - за 24: темп ровный, 1000 км - за 20 часов. Если же 20 км заняли 40 минут, значит, что-то нарастает - пробки к центру, - и экстраполировать надо осторожно. Опыт с удвоением - такая же пробная поездка для программы: не одна точка, а несколько, и смотрят не на время, а на то, как оно растёт.

Механизм: почему log₂ отношения

Пусть T(n) = c · nᵇ. Тогда T(2n) / T(n) = c · (2n)ᵇ / (c · nᵇ) = 2ᵇ: константа c сокращается, остаётся только показатель. Логарифм по основанию 2 отвечает на вопрос «в какую степень надо возвести 2, чтобы получить это отношение», - ровно b. Отношение 4 даёт b = 2, отношение 2 - b = 1, отношение 8 - b = 3.

Для n log n отношение чуть больше двух: 2 · log₂(2n) / log₂ n = 2 · (1 + 1 / log₂ n), показатель - около 1,1 и медленно сползает к 1. А если в цене два слагаемых, например накладные расходы плюс работа, показатель меняется с размером: на малых n побеждает одно, на больших - другое.

Протокол опыта: размеры через удвоение, на каждом - честный замер из прошлого урока (прогрев, повторы, минимум или медиана), показатель по каждой соседней паре. Смотрят на устойчивую часть ряда, а не на первую пару.

Правило

Показатель роста по замерам: b ≈ log₂(T(2n) / T(n)). Константа сокращается, остаётся степень. n log n даёт около 1,1, n² - 2. Показатель на малых n искажают накладные расходы, на больших - иерархия памяти; смотреть надо на устойчивую часть ряда и сравнивать с теорией: расхождение - сигнал скрытой цены.

Разбор: три функции на этой машине

Поиск повторов через список просмотренных (квадрат), sorted (n log n) и построение словаря (n). Каждый размер - лучшее из семи замеров по три прогона.

import math
import random
import timeit

random.seed(1)


def slovar(a):
    return {x: True for x in a}


def sortirovka(a):
    return sorted(a)


def povtory(a):
    # есть ли повторы: для каждого - поиск в уже просмотренном СПИСКЕ
    vidennye = []
    for x in a:
        if x in vidennye:
            return True
        vidennye.append(x)
    return False


bolshie = [50000, 100000, 200000, 400000, 800000]
malye = [1000, 2000, 4000, 8000]
for imya, f, razmery in [("повторы в списке", povtory, malye),
                         ("sorted", sortirovka, bolshie),
                         ("словарь", slovar, bolshie)]:
    proshloe = None
    print(imya)
    for n in razmery:
        a = list(range(n))
        random.shuffle(a)
        t = min(timeit.repeat(lambda: f(a), number=3, repeat=7)) / 3
        stroka = f"  n = {n:>6}: {t * 1000:7.1f} мс"
        if proshloe is not None:
            stroka += f", показатель {math.log2(t / proshloe):.2f}"
        print(stroka)
        proshloe = t

повторы в списке
  n =   1000:     8.5 мс
  n =   2000:    31.7 мс, показатель 1.90
  n =   4000:   122.1 мс, показатель 1.94
  n =   8000:   491.2 мс, показатель 2.01
sorted
  n =  50000:     8.6 мс
  n = 100000:    21.5 мс, показатель 1.33
  n = 200000:    56.7 мс, показатель 1.40
  n = 400000:   137.7 мс, показатель 1.28
  n = 800000:   321.0 мс, показатель 1.22
словарь
  n =  50000:     4.9 мс
  n = 100000:    14.7 мс, показатель 1.58
  n = 200000:    38.4 мс, показатель 1.39
  n = 400000:    83.6 мс, показатель 1.12
  n = 800000:   221.2 мс, показатель 1.40

Квадрат узнаётся сразу: 1,90 → 1,94 → 2,01. Первые пары чуть ниже двух: линейная часть работы (обход, append) ещё заметна рядом с квадратичной.

sorted - около 1,2-1,4 вместо теоретических 1,07-1,1. Словарь, алгоритм за O(n), - 1,1-1,6. Числа перемешаны, обращения к объектам-ключам идут вразброс, и с ростом n они вылезают из кеша: каждый элемент стоит всё дороже - ровно та лестница, что в первом уроке главы. Ряд у словаря ещё и неровный: тут и шум, и ступени кеша, на которые попадают одни удвоения и не попадают другие, - поэтому смотрят на несколько пар, а не на одну. Граница правила «показатель равен асимптотике»: на настоящей машине он равен асимптотике плюс рост цены одной операции.

Разбор: два слагаемых в одной цене

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

import math

def pokazateli(T, razmery):
    # по формуле времени - показатели log₂(T(2n) / T(n)) на удвоениях
    out = []
    for n in razmery:
        out.append(round(math.log2(T(2 * n) / T(n)), 2))
    return out

def s_nakladnymi(n):
    return 20000 + n                 # постоянные накладные + линия

def n_log_n(n):
    return n * math.log2(n)

def dva_slagaemyh(n):
    return 0.01 * n * n + 50 * n     # квадрат с маленьким множителем

razmery = [1000, 4000, 16000, 64000, 256000, 1024000]
print("n:", razmery)
print("20000 + n:      ", pokazateli(s_nakladnymi, razmery))
print("n log n:        ", pokazateli(n_log_n, razmery))
print("0.01 n² + 50 n: ", pokazateli(dva_slagaemyh, razmery))

n: [1000, 4000, 16000, 64000, 256000, 1024000]
20000 + n:       [0.07, 0.22, 0.53, 0.82, 0.95, 0.99]
n log n:         [1.14, 1.12, 1.1, 1.09, 1.08, 1.07]
0.01 n² + 50 n:  [1.22, 1.53, 1.82, 1.95, 1.99, 2.0]

Линейная функция с накладными расходами на входе выглядит «почти константой» до тех пор, пока работа не перевесит 20 000: показатель 0,07 на тысяче. Квадрат с маленьким множителем на малых n маскируется под линию - 1,22, и только к сотням тысяч честно показывает 2. А n log n ни при каком разумном n не даёт ровно 1: 1,07 на миллионе. Опыт на малых размерах обманывает в обе стороны.

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

Экстраполяция с маленьких входов. Тест на тысяче записей - 0,2 секунды, «значит, на миллионе будет 200 секунд». Если показатель 2, а не 1, - будет 55 часов.

Скрытый квадрат. x in список внутри цикла, spisok = spisok + [x] в цикле (новый список на каждом шаге), list.pop(0) - каждое по отдельности выглядит дешёвым. Опыт с удвоением на всей функции сразу показывает 2.

Ступень кеша, принятая за асимптотику. Пара удвоений вокруг размера кеша даёт показатель 1,6 у линейного алгоритма; дальше он вернётся к единице.

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

«Выдержит ли сервис рост данных в десять раз?» - вопрос про показатель, а не про время. Три-четыре замера с удвоением на копии данных дают b, а 10ᵇ - во сколько раз вырастет время: при b = 1,2 - в 16 раз, при b = 2 - в 100. Тот же приём проверяет асимптотику собственного кода: если ты ожидал n log n, а опыт показывает 2, где-то сидит квадрат.

Теперь сам

1. Замеры: 40 мс на n = 10⁵, 165 мс на 2 · 10⁵, 655 мс на 4 · 10⁵. Показатель? Сколько займёт 1,6 · 10⁶?
2. Почему у n log n отношение T(2n) / T(n) больше двух?
3. Линейный алгоритм дал показатель 1,5 на парах вокруг 1-4 миллионов элементов. Что ты проверишь, прежде чем объявить его квадратичным?