Сложность операций с коллекциями
Здесь рассматривается, во что обходятся конкретные операции над списком, множеством и словарём и почему выбор структуры определяет больше, чем оптимизация кода. Сама O-нотация со всей строгостью разбирается далее, в главе «Введение в алгоритмы».
В настоящей главе оценивается стоимость каждой операции над коллекциями Python и обсуждается выбор структуры, соответствующей задаче.
Слайды к главе. Материал главы изложен также в шестой части лекции «Python. Начало» с замерами в терминале; слайды лекции доступны на сайте книги и в PDF.
В нотации O-большое описывается, как время выполнения алгоритма растёт вслед за размером входных данных.
Значение сложности
Ниже миллион чисел помещается в список и в множество, после чего в каждом из них выполняется поиск одного и того же значения оператором in. Синтаксис не отличается ни одним символом, отличается работа, выполняемая внутри:
from timeit import timeit
import random
# Сравним поиск в списке и множестве
large_list = list(range(1000000))
large_set = set(large_list)
# Ищем случайный элемент
target = random.randrange(1000000)
# Время поиска в списке (O(n))
list_time = timeit(lambda: target in large_list, number=1000)
# Время поиска в множестве (O(1))
set_time = timeit(lambda: target in large_set, number=1000)
print(f"Поиск в списке: {list_time:.4f} сек")
print(f"Поиск в множестве: {set_time:.4f} сек")
Разрыв составляет несколько порядков. Списку приходится перебирать элементы подряд, пока не будет найден нужный, — в среднем полмиллиона сравнений. Множество вычисляет от значения хеш и сразу обращается к ячейке, соответствующей этому хешу, обходясь одной операцией независимо от того, миллион там элементов или десять.
Сложность операций со списками
Константное время O(1)
my_list = [1, 2, 3, 4, 5]
# Эти операции выполняются за постоянное время
my_list.append(6) # Добавление в конец
last = my_list.pop() # Удаление с конца
element = my_list[2] # Доступ по индексу
length = len(my_list) # Получение длины
Почему O(1): список в Python устроен как динамический массив указателей. Он выделяет память с запасом, поэтому append записывает указатель в свободную ячейку и увеличивает счётчик длины, не перемещая остальные элементы.
Изредка запас исчерпывается, и списку приходится выделить больший блок памяти и скопировать туда все элементы, что стоит \( O(n) \). Однако поскольку размер увеличивается кратно, перевыделения происходят всё реже, и в среднем на одну операцию по-прежнему приходится константа. Такую усреднённую сложность называют амортизированной \( O(1) \).
Линейное время O(n)
my_list = [1, 2, 3, 4, 5]
# Эти операции требуют обхода или сдвига элементов
my_list.insert(0, 0) # Вставка в начало → сдвиг всех элементов
my_list.remove(3) # Поиск и удаление элемента
element in my_list # Поиск элемента
my_list.index(4) # Поиск индекса элемента
Почему O(n): при вставке в начало все элементы, следующие далее, приходится сдвигать на одну позицию. А in, remove и index проходят по списку с начала, сравнивая элементы: заранее известного места под значение у массива нет.
Медленный и быстрый код
Обе функции ниже удаляют дубликаты с сохранением порядка. Отличие в одной строке: первая проверяет item not in result по списку, вторая обращается к множеству seen. За строкой внутри цикла скрывается ещё один проход по всем элементам, превращающий линейный алгоритм в квадратичный.
# НЕЭФФЕКТИВНО: O(n²)
def remove_duplicates_slow(data):
result = []
for item in data:
if item not in result: # O(n) для каждого элемента!
result.append(item)
return result
# ЭФФЕКТИВНО: O(n)
def remove_duplicates_fast(data):
seen = set()
result = []
for item in data:
if item not in seen: # O(1) проверка!
seen.add(item)
result.append(item)
return result
# Тестируем на семи тысячах случайных чисел
import random
data = [random.randrange(7000) for _ in range(7000)]
slow_time = timeit(lambda: remove_duplicates_slow(data), number=1)
fast_time = timeit(lambda: remove_duplicates_fast(data), number=1)
print(f"Медленная версия: {slow_time:.4f} сек") # 0.0520
print(f"Быстрая версия: {fast_time:.4f} сек") # 0.0002
Разница составляет двести пятьдесят раз, и растёт она вместе с объёмом. На семидесяти тысячах элементов медленная версия выполняется за 4.6 секунды против 2 миллисекунд у быстрой, то есть отстаёт почти в две тысячи раз. Время первой выросло в девяносто раз при десятикратном росте данных: это и есть квадратичность.
Следует отметить тонкость самого измерения. Если вместо случайных чисел подставить набор [1, 2, 2, 3, 4, 4, 5] * 1000, содержащий те же семь тысяч элементов, разница сократится до полутора раз вместо двухсот пятидесяти. Причина в том, что различных значений там всего пять. Список result, растущий только на новых значениях, не превысит пяти элементов, проверка item not in result пройдёт по пяти элементам вместо тысяч, и квадратичность не проявится.
Алгоритм проверяется на данных, приближенных к реальным. На неудачно подобранном наборе квадратичный код не вызывает подозрений, а проблема проявляется на реальных данных.
Сложность операций с множествами
В основе множества лежит хеш-таблица, рассмотренная в главе про хеш-функции, поэтому большинство операций имеют сложность O(1).
my_set = {1, 2, 3, 4, 5}
# O(1) операции
my_set.add(6) # Добавление
my_set.remove(3) # Удаление
4 in my_set # Проверка вхождения
len(my_set) # Длина
# операции над двумя множествами — сложность у каждой своя
s1 = {1, 2, 3}
s2 = {3, 4, 5}
union = s1 | s2 # объединение: O(len(s1) + len(s2))
intersection = s1 & s2 # пересечение: O(min(len(s1), len(s2)))
difference = s1 - s2 # разность: O(len(s1))
Для построения объединения необходимо пройти оба множества целиком. Для пересечения достаточно перебрать элементы меньшего множества и проверить каждый в большем, причём проверка по хешу стоит константу. Поэтому пересечение множества из тысячи элементов с множеством из двух миллионов выполняется за десятки микросекунд, а объединение тех же двух занимает на три порядка дольше.
Интересный факт: при массовых коллизиях хешей операции с множеством вырождаются в O(n). На практике это почти не встречается, за исключением случаев, когда данные намеренно подобраны злоумышленником, знающим хеш-функцию.
Сложность операций со словарями
Словари также построены на хеш-таблицах, поэтому всё, что выполняется по ключу, стоит O(1). Любая операция, вынужденная просмотреть все значения, стоит O(n), сколь бы коротко она ни записывалась.
my_dict = {'a': 1, 'b': 2, 'c': 3}
# O(1) операции
my_dict['d'] = 4 # Вставка/обновление
value = my_dict['a'] # Доступ
del my_dict['b'] # Удаление
'a' in my_dict # Проверка ключа
# O(n) операции
list(my_dict.keys()) # Создание списка ключей
list(my_dict.values()) # Создание списка значений
'value' in my_dict.values() # Поиск по значениям
Вычисление сложности на практике
Метод 1. Анализ вложенных циклов
# O(n²) — квадратичная сложность
def find_pairs_quadratic(items):
pairs = []
for i in range(len(items)): # O(n)
for j in range(i + 1, len(items)): # O(n)
pairs.append((items[i], items[j])) # O(1)
return pairs
# O(n) — линейная сложность
def count_unique(items):
seen = set()
for item in items: # O(n)
seen.add(item) # O(1)
return len(seen) # O(1)
Сложности вложенных циклов перемножаются, а сложности участков, следующих подряд, складываются: один цикл по всем элементам даёт \( O(n) \), а цикл, вложенный в цикл, \( O(n^2) \). Оценивать следует не отступы, а суть: вызов item not in some_list внутри цикла также является скрытым вложенным циклом, хотя выглядит как одна строка.
Метод 2. Учёт дорогостоящих операций
Вложенные циклы видны сразу, а вызовы библиотечных функций остаются незаметными. sorted стоит \( O(n \log n) \), list(...) и sum(...) обходятся в \( O(n) \), min и max также в \( O(n) \). При разборе функции эти стоимости подставляются и складываются.
def process_data(data):
result = []
# Сортировка: O(n log n)
sorted_data = sorted(data) # O(n log n)
# Поиск каждого элемента: O(n) × O(log n) = O(n log n)
for target in sorted_data: # O(n)
# Бинарный поиск: O(log n)
# (предположим, что у нас есть реализация)
index = binary_search(sorted_data, target)
result.append(index)
return result
# Общая сложность: O(n log n) + O(n log n) = O(n log n)
Метод 3. Практическое измерение
Сложность можно измерить, выполнив операцию на входах разного размера и проследив, как растёт время. Одну быструю операцию измерить нельзя. Вставка в список занимает микросекунды, разрешение таймера и случайный шум того же порядка, и вместо зависимости будут получены помехи. Поэтому операция повторяется много раз, и это обеспечивает timeit.
from timeit import timeit
print(f"{'размер':>8} {'время, мкс':>12} {'отношение':>10}")
prev = None
for size in [10_000, 20_000, 40_000, 80_000, 160_000]:
setup = f"data = list(range({size}))"
# вставляем и тут же удаляем, чтобы список не рос за время замера
t = timeit("data.insert(0, -1); data.pop(0)", setup=setup, number=2000) / 2000
ratio = f"{t / prev:.1f}x" if prev else "—"
print(f"{size:8} {t * 1e6:12.1f} {ratio:>10}")
prev = t
размер время, мкс отношение
10000 4.4 —
20000 8.0 1.8x
40000 15.7 2.0x
80000 33.1 2.1x
160000 62.0 1.9x
Линейная сложность: удвоение размера удваивает время. В измерении важны две детали. Подготовка списка вынесена в setup, иначе в измеряемое время попало бы его создание. После каждой вставки элемент удаляется, иначе за две тысячи повторов растущий список исказил бы результат.
Если проделать то же самое с append, окажется, что время вызова не зависит от размера.
Практические правила для выбора коллекций
Область применения списков
Список является выбором по умолчанию. Он необходим, когда важен порядок элементов и доступ по индексу, когда данные добавляются и извлекаются с конца и когда повторяющиеся значения допустимы или осмысленны.
Список плохо приспособлен к работе с началом: insert(0, x) и pop(0), требующие сдвига всего хвоста, стоят \(O(n)\) каждая. На больших данных это превращается в квадратичное время; там требуется дек, рассмотренный в главе про структуры данных и приспособленный к работе с обоими концами.
Область применения множеств
Множество применяется ради проверки принадлежности. Она стоит \(O(1)\) против \(O(n)\) у списка. Фильтрация миллиона событий по списку разрешённых идентификаторов займёт минуты, а через множество — доли секунды. Попутно множество удаляет дубликаты и поддерживает объединение, пересечение и разность.
Множество не подходит в двух случаях: если важен порядок вставки, поскольку множество его не хранит; и если элементы нехешируемы, поскольку списки и словари в множество поместить нельзя.
Область применения словарей
Словарь необходим там, где у данных есть естественный ключ, будь то имя канала, номер события или дата измерения. Поиск по ключу стоит \(O(1)\), поэтому словарь заменяет перебор списка везде, где приходится искать запись, у которой поле равно заданному значению. На нём же удобно группировать, отводя под ключ категорию, а под значение список объектов, попадающих в неё.
С версии Python 3.7 словарь сохраняет порядок вставки. Поиск по значению словарь не поддерживает: такой поиск стоит \(O(n)\). Если он требуется часто, имеет смысл завести второй словарь с обратным отображением.
Оптимизация на практике
Если по коллекции многократно выполняется поиск, её лучше преобразовать в множество или словарь один раз до цикла. Построение множества имеет тот же порядок \( O(m) \), что и один линейный поиск, хотя и с большей константой, поэтому оно окупается после нескольких поисков: \( n \) проверок обходятся в \( O(n + m) \) вместо \( O(n \cdot m) \).
# ПЛОХО: O(n²)
def find_common_elements_slow(list1, list2):
result = []
for item in list1: # O(n)
if item in list2: # O(m) - линейный поиск!
result.append(item)
return result
# ХОРОШО: O(n + m)
def find_common_elements_fast(list1, list2):
set2 = set(list2) # O(m) - создание множества
result = []
for item in list1: # O(n)
if item in set2: # O(1) - поиск в хеш-таблице!
result.append(item)
return result
Некоторые правила сложности
- O(1) < O(log n) < O(n) < O(n log n) < O(n²) — эту иерархию необходимо запомнить.
- Особого внимания требуют вложенные циклы, дающие O(n²): внутренний цикл часто скрыт за вызовом наподобие
x in list. - Структура подбирается под операцию: множества и словари для поиска, списки для последовательного перебора, дек для работы с обоих концов.
Преждевременная оптимизация вредна: подбор констант в коде, выполняемом раз в сутки, является напрасной тратой времени. Однако выбор структуры данных к ней не относится: от него зависит, останется программа работоспособной на реальных данных или нет.
Задание. Решить задачи с разбором сложности: «Решение задач на Python и анализ сложности».