Зачем замерять

Все теории и асимптотики, изученные в этом и предыдущем модулях, имеют практический смысл только если они подтверждаются измерениями. Junior DE должен уметь:

1. Замерять время конкретной операции на конкретных данных.
2. Замерять память — peak usage, allocations.
3. Понимать, на каких формах данных алгоритм деградирует или ускоряется.

Этот урок — про инструменты (timeit, tracemalloc) и про конкретные замеры на разных формах входа.

Инструмент 1: timeit

timeit — стандартный Python-модуль для замеров. Запускает функцию много раз, возвращает усреднённое время.

import timeit

def test():
    sorted([3, 1, 4, 1, 5, 9, 2, 6])

# запускает test 1000 раз, возвращает суммарное время
elapsed = timeit.timeit(test, number=1000)
print(f"avg: {elapsed/1000*1e6:.2f} us")

Для одиночных замеров на больших данных удобнее time.perf_counter():

import time
arr = [...]
t = time.perf_counter()
sorted(arr)
elapsed = time.perf_counter() - t
print(f"{elapsed*1000:.1f} ms")

Не используйте time.time() для бенчмарков: он зависит от настроек системного времени и менее точен. time.perf_counter() — монотонные часы с лучшим разрешением.

Инструмент 2: tracemalloc

Для замера памяти в Python — tracemalloc. Включается перед измеряемой операцией, выдаёт peak usage.

import tracemalloc

tracemalloc.start()
sorted_arr = sorted(arr)
peak = tracemalloc.get_traced_memory()[1]
tracemalloc.stop()

print(f"peak: {peak / 1024 / 1024:.1f} MB")

get_traced_memory() возвращает (current, peak). peak — максимальное использование за время трассировки. Это и есть «сколько на самом деле выделилось».

Внимание: tracemalloc сильно замедляет код (10-100x). Не используйте для production-измерений времени — только для memory.

Полный бенчмарк: 6 форм данных, 3 sort

Подготовим разные формы массива:

import random
random.seed(42)

N = 10**6

# 1) random
arr_random = [random.randint(0, 10**9) for _ in range(N)]

# 2) sorted
arr_sorted = list(range(N))

# 3) reverse sorted
arr_reverse = list(range(N, 0, -1))

# 4) almost sorted (100 swap'ов)
arr_almost = list(range(N))
for _ in range(100):
    i = random.randint(0, N - 2)
    arr_almost[i], arr_almost[i + 1] = arr_almost[i + 1], arr_almost[i]

# 5) constant (все равные)
arr_constant = [42] * N

# 6) few distinct (10 уникальных значений)
arr_few = [random.randint(0, 10) for _ in range(N)]

Замерим три sort’а:

import time
import numpy as np

def bench_python_sorted(arr):
    a = arr[:]
    t = time.perf_counter()
    sorted(a)
    return time.perf_counter() - t

def bench_python_list_sort(arr):
    a = arr[:]
    t = time.perf_counter()
    a.sort()
    return time.perf_counter() - t

def bench_numpy_sort(arr):
    a = np.array(arr, dtype=np.int64)
    t = time.perf_counter()
    a.sort()
    return time.perf_counter() - t

cases = {
    "random": arr_random,
    "sorted": arr_sorted,
    "reverse": arr_reverse,
    "almost": arr_almost,
    "constant": arr_constant,
    "few_distinct": arr_few,
}

print(f"{'case':<14} {'sorted()':<12} {'list.sort':<12} {'numpy.sort':<12}")
for name, arr in cases.items():
    t1 = bench_python_sorted(arr) * 1000
    t2 = bench_python_list_sort(arr) * 1000
    t3 = bench_numpy_sort(arr) * 1000
    print(f"{name:<14} {t1:>8.1f} ms {t2:>8.1f} ms {t3:>8.1f} ms")

Типичный вывод на M-серии 2024:

case           sorted()     list.sort   numpy.sort
random          280.0 ms     270.0 ms      45.0 ms
sorted            8.0 ms       6.0 ms      12.0 ms
reverse          15.0 ms      12.0 ms      20.0 ms
almost            8.0 ms       6.0 ms      40.0 ms
constant          5.0 ms       3.0 ms      10.0 ms
few_distinct     50.0 ms      45.0 ms      30.0 ms

Анализ результатов

Наблюдения

1. Timsort vs numpy.sort на random: numpy в 6 раз быстрее. Причина — реализация на C + cache-friendly quicksort. На random данных Python Timsort не имеет шанса.
2. Timsort на sorted/almost: O(n) adaptive — десятки мс на 1М. Numpy не использует adaptive (introsort всегда O(n log n)) — медленнее.
3. Timsort на reverse: распознаёт descending run, реверсирует за O(n). Numpy — обычный O(n log n).
4. Constant: Timsort обнаруживает «уже отсортирован» за O(n). Numpy тоже быстро, но не настолько.
5. Few distinct: numpy выигрывает за счёт cache locality на повторяющихся значениях.

Вывод: Timsort — лидер для частично-отсортированных данных. Numpy — лидер для random случайных данных. На реальных DE-данных (логи, события — часто частично-отсортированные) Timsort часто выигрывает.

Скорость через размер

import time, random
random.seed(0)
sizes = [10**3, 10**4, 10**5, 10**6, 10**7]
for n in sizes:
    arr = [random.randint(0, 10**9) for _ in range(n)]
    t = time.perf_counter()
    sorted(arr)
    elapsed = time.perf_counter() - t
    print(f"n={n:>10}: {elapsed*1000:>8.1f} ms")

Ожидаемое:

• n=10^3: 0.5 мс,
• n=10^4: 5 мс,
• n=10^5: 50 мс,
• n=10^6: 300 мс (5x скачок — log n растёт),
• n=10^7: 3.5 с.

Каждый шаг x10 по n -> ~x10-12 по времени (n log n растёт примерно как n^1.1). Это подтверждает O(n log n).

Память: bytes vs int

В Python int занимает 28 байт + ссылка 8 байт = 36 байт «на элемент». 1М int — это ~36 МБ.

import sys
import tracemalloc

arr = list(range(1_000_000))
print(f"arr: {sys.getsizeof(arr) / 1024 / 1024:.1f} MB shell")  # ~8 МБ — только указатели
print(f"first int: {sys.getsizeof(arr[0])} bytes")              # 28 байт для маленьких int

tracemalloc.start()
sorted_arr = sorted(arr)
peak = tracemalloc.get_traced_memory()[1]
tracemalloc.stop()
print(f"sorted peak: {peak / 1024 / 1024:.1f} MB")

Peak — это исходный массив (8 МБ ссылок) + buffer Timsort’а + новый result list. Обычно peak ~ 15-25 МБ.

В numpy всё проще:

import numpy as np
arr = np.arange(1_000_000, dtype=np.int64)
print(f"arr: {arr.nbytes / 1024 / 1024:.1f} MB")     # 8 МБ

8 МБ для 1М int64. В 4 раза меньше, чем Python list. Numpy более эффективен по памяти.

Гайд по выбору sort

DE-кейс: pandas vs numpy на DataFrame

import pandas as pd
import numpy as np
import time

N = 10**6
df = pd.DataFrame({
    "ts": np.random.randint(0, 10**9, size=N, dtype=np.int64),
    "value": np.random.rand(N),
})

t = time.perf_counter()
df.sort_values("ts")
print(f"pandas sort_values: {(time.perf_counter()-t)*1000:.1f} ms")

t = time.perf_counter()
arr = df["ts"].values
arr.sort()
print(f"numpy sort raw: {(time.perf_counter()-t)*1000:.1f} ms")

Pandas sort_values делает permutation: O(n log n) на ts + O(n) на reorder каждой колонки. Numpy.sort на raw int64-массиве — чисто числовой sort, быстрее. Pandas на 1М строк × 2 колонки — ~80-150 мс, numpy.sort — ~30-50 мс.

Попробуй сам

Реализуйте полный бенчмарк по шаблону выше. Замерьте:

1. Шесть форм данных (random, sorted, reverse, almost, constant, few_distinct) на 1М элементов.
2. Три sort: Python sorted(), Python list.sort(), numpy.sort().
3. Память (через tracemalloc) для каждого вариантa.

Создайте таблицу с результатами. Сделайте выводы для каждой формы:

• На каких данных Timsort обгоняет numpy?
• На каких numpy обгоняет?
• Когда memory различается значительно?

Эта таблица — ваш cheatsheet для будущих DE-задач.

В следующих модулях курса мы продолжим с searching, recursion и applied patterns. Эти знания о сортировках понадобятся постоянно.