Производительность, O-большое и модуль collections

Программа сверяет 100 000 заказов со списком из 100 000 заблокированных клиентов. Со списком это занимает десятки секунд; поменяй одну строку, чтобы использовать множество, — и работа закончится за долю секунды. Скорость в Python редко берётся из хитрых трюков — она берётся из правильного выбора структуры данных и алгоритма и из измерений вместо догадок. Этот урок даёт инструменты и для того, и для другого.

O-большое: как растёт время

Нотация O-большое описывает, как время выполнения операции растёт с размером данных n, без учёта постоянных множителей. O(1) — константа: не зависит от n. O(log n) — растёт очень медленно (двоичный поиск). O(n) — пропорционально n (один проход по списку). O(n log n) — хорошая сортировка. O(n²) — вложенные циклы по одним и тем же данным: в 10 раз больше данных — в 100 раз больше работы.

Почему словари и множества такие быстрые? Это хеш-таблицы: hash(key) почти напрямую указывает, где хранится элемент, поэтому in не перебирает данные. У списка такого указателя нет, и он вынужден сравнивать элементы по одному. А вставка в начало списка сдвигает все остальные элементы, поэтому insert(0, x) и pop(0) — O(n).

Не гадай, а измеряй: timeit и cProfile

timeit много раз выполняет небольшой фрагмент кода и возвращает общее время — так случайные колебания сглаживаются. Сравним поиск в списке и в множестве из 100 000 чисел:

import timeit

setup = 'data_list = list(range(100_000)); data_set = set(data_list)'
t_list = timeit.timeit('99_999 in data_list', setup=setup, number=200)
t_set = timeit.timeit('99_999 in data_set', setup=setup, number=200_000) / 1000
print(f'list: {t_list * 1000:.2f} ms for 200 lookups')
print(f'set:  {t_set * 1000:.4f} ms for 200 lookups')
print(f'the set is about {t_list / t_set:,.0f} times faster')

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

$ python -m cProfile -s cumulative slow.py
28656
         92741 function calls (51 primitive calls) in 0.019 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.019    0.019 {built-in method builtins.exec}
        1    0.000    0.000    0.019    0.019 slow.py:1(<module>)
        1    0.000    0.000    0.019    0.019 slow.py:4(main)
        1    0.000    0.000    0.019    0.019 {built-in method builtins.sum}
       23    0.000    0.000    0.019    0.001 slow.py:5(<genexpr>)
 92712/22    0.019    0.000    0.019    0.001 slow.py:1(fib)

92712/22 означает всего 92 712 вызовов, из которых только 22 сделаны снаружи (остальные рекурсивные). Профилировщик можно использовать и из кода; здесь мы читаем только количество вызовов — и видим, как lru_cache из урока о декораторах превращает десятки тысяч вызовов в 21:

import cProfile
import pstats
from functools import lru_cache

def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

@lru_cache(maxsize=None)
def fib_cached(n):
    return n if n < 2 else fib_cached(n - 1) + fib_cached(n - 2)

for func in (fib, fib_cached):
    profiler = cProfile.Profile()
    profiler.runcall(func, 20)
    stats = pstats.Stats(profiler).stats
    calls = sum(v[1] for (_, _, name), v in stats.items() if name == func.__name__)
    print(f'{func.__name__}(20): {calls} calls')

fib(20): 21891 calls
fib_cached(20): 21 calls

Модуль collections

**Counter** — словарь для подсчёта: передай ему любой итерируемый объект, и он посчитает элементы. most_common(n) возвращает n самых частых; отсутствующий ключ даёт 0 вместо KeyError; счётчики можно даже складывать и вычитать:

from collections import Counter

words = Counter('the cat and the hat and the bat'.split())
print(words.most_common(2))
print(words['the'], words['dog'])

votes = Counter(['plov', 'dolma', 'plov', 'kebab', 'plov', 'dolma'])
print(votes)
print(votes + Counter(['kebab', 'kebab']))

[('the', 3), ('and', 2)]
3 0
Counter({'plov': 3, 'dolma': 2, 'kebab': 1})
Counter({'plov': 3, 'kebab': 3, 'dolma': 2})

**defaultdict** автоматически создаёт отсутствующее значение при первом обращении с помощью переданной фабрики: list, int, set. Он идеален для группировки. Осторожно: даже чтение отсутствующего ключа добавляет его в словарь:

from collections import defaultdict

students = [('Aysel', '9A'), ('Murad', '9B'), ('Leyla', '9A'), ('Elvin', '9B'), ('Nigar', '9A')]
by_class = defaultdict(list)
for name, group in students:
    by_class[group].append(name)
print(dict(by_class))
print(by_class['10C'], len(by_class))

{'9A': ['Aysel', 'Leyla', 'Nigar'], '9B': ['Murad', 'Elvin']}
[] 3

**deque** (двусторонняя очередь) добавляет и удаляет элементы с обоих концов за O(1), тогда как у списка удаление из начала — O(n). С maxlen она хранит только последние n элементов — идеально для списков «недавно просмотренного» и скользящих окон. **namedtuple** создаёт лёгкий неизменяемый кортеж, у полей которого есть имена:

from collections import deque, namedtuple

queue = deque(['Aysel', 'Murad'])
queue.append('Leyla')
queue.appendleft('Elvin')
print(queue.popleft(), queue)

recent = deque(maxlen=3)
for page in ['home', 'lessons', 'python', 'quiz', 'profile']:
    recent.append(page)
print(list(recent))

Point = namedtuple('Point', ['x', 'y'])
p = Point(3, 4)
print(p, p.x, p[1], p._replace(x=10))

Elvin deque(['Aysel', 'Murad', 'Leyla'])
['python', 'quiz', 'profile']
Point(x=3, y=4) 3 4 Point(x=10, y=4)

itertools и скорость в стиле Python

**itertools** — набор быстрых ленивых «кирпичиков» для циклов, написанных на C: соединение последовательностей (chain), нарастающие суммы (accumulate), соседние пары (pairwise), сочетания и декартово произведение, группировка:

from itertools import accumulate, chain, combinations, groupby, pairwise, product

print(list(chain([1, 2], (3, 4), 'ab')))
print(list(accumulate([5, 3, 8, 2])))
print(list(pairwise([10, 12, 15, 11])))
print(list(combinations('ABC', 2)))
print(len(list(product(range(10), repeat=4))))
fruits = sorted(['cherry', 'apple', 'blueberry', 'avocado', 'banana'])
print({k: list(g) for k, g in groupby(fruits, key=lambda w: w[0])})

[1, 2, 3, 4, 'a', 'b']
[5, 8, 16, 18]
[(10, 12), (12, 15), (15, 11)]
[('A', 'B'), ('A', 'C'), ('B', 'C')]
10000
{'a': ['apple', 'avocado'], 'b': ['banana', 'blueberry'], 'c': ['cherry']}

numbers = [1, 2, 2, 3, 4, 4, 5]
for n in numbers:
    if n % 2 == 0:
        numbers.remove(n)
print(numbers)

numbers = [1, 2, 2, 3, 4, 4, 5]
numbers = [n for n in numbers if n % 2 != 0]
print(numbers)

[1, 2, 3, 4, 5]
[1, 3, 5]

from collections import Counter
import re

text = '''Python is fast to write. Python is fun.
Fast code is good, but correct code is better.'''
# 1) turn the text into a list of lower-case words
# 2) print the 3 most common words as 'word: count'

is: 4
python: 2
fast: 2

ids = [105, 230, 105, 999, 412, 230, 7, 105]
seen = set()
duplicates = set()
# one pass: if an id is already in seen, it is a duplicate

print(sorted(duplicates))
print(len(seen), 'unique ids')

[105, 230]
5 unique ids