Какова скорость работы различных коллекций

Скорость работы различных коллекций в Python

Производительность коллекций критична для оптимизации. Разберу Time Complexity для основных операций.

1. List (Динамический массив)

# Операции и их сложность
my_list = [1, 2, 3, 4, 5]

# Access by index: O(1) — очень быстро
value = my_list[0]  # Мгновенно

# Search: O(n) — медленно
if 3 in my_list:    # Проверяет каждый элемент
    pass

# Insert at beginning: O(n) — очень медленно!
my_list.insert(0, 0)  # Сдвигает все элементы

# Insert at end: O(1) amortized — быстро
my_list.append(6)

# Remove at beginning: O(n) — медленно
my_list.pop(0)  # Сдвигает все элементы

# Remove at end: O(1) — быстро
my_list.pop()

# Remove by value: O(n) — медленно
my_list.remove(3)  # Ищет и удаляет

# Iterate: O(n) — нужно посетить всё
for item in my_list:
    print(item)

Таблица сложности List:

*Amortized (в среднем)

import timeit

# Сравнение операций
test_list = list(range(10000))

# Insert at end: быстро
time1 = timeit.timeit(lambda: test_list.append(99999), number=10000)
print(f"append: {time1:.4f}s")  # ~0.0001s

# Insert at start: медленно
time2 = timeit.timeit(lambda: test_list.insert(0, -1), number=10000)
print(f"insert(0): {time2:.4f}s")  # ~0.5s (в 5000x медленнее!)

2. Dictionary (Hash Table)

Очень быстро для большинства операций.

my_dict = {'a': 1, 'b': 2, 'c': 3}

# Access: O(1) — мгновенно
value = my_dict['a']

# Search: O(1) — очень быстро
if 'a' in my_dict:
    pass

# Insert: O(1) — быстро
my_dict['d'] = 4

# Delete: O(1) — быстро
del my_dict['a']

# Iterate: O(n) — нужно посетить всё
for key, value in my_dict.items():
    print(key, value)

# Get with default: O(1)
value = my_dict.get('missing', 'default')  # Быстро

Таблица сложности Dictionary:

Сравнение List vs Dict для поиска:

import timeit

test_list = list(range(100000))
test_dict = {i: i for i in range(100000)}

# Поиск в List: O(n)
time_list = timeit.timeit(lambda: 99999 in test_list, number=1000)
print(f"List search: {time_list:.4f}s")  # ~0.3s

# Поиск в Dict: O(1)
time_dict = timeit.timeit(lambda: 99999 in test_dict, number=1000)
print(f"Dict search: {time_dict:.4f}s")  # ~0.0001s (в 3000x быстрее!)

3. Set (Hash Set)

Как Dictionary, но только ключи (без значений).

my_set = {1, 2, 3, 4, 5}

# Search: O(1) — мгновенно
if 3 in my_set:
    pass

# Insert: O(1) — быстро
my_set.add(6)

# Delete: O(1) — быстро
my_set.remove(3)

# Union: O(n + m) — O(n)
union = my_set | {6, 7, 8}

# Intersection: O(min(n, m))
intersection = my_set & {1, 2, 3, 10}

# Difference: O(n)
difference = my_set - {1, 2}

Таблица сложности Set:

4. Tuple (Immutable sequence)

my_tuple = (1, 2, 3, 4, 5)

# Access: O(1) — быстро (как list)
value = my_tuple[0]

# Search: O(n) — медленно (как list)
if 3 in my_tuple:
    pass

# Immutable: нельзя изменять
my_tuple[0] = 10  # ❌ TypeError!

Tuple быстрее List для:

• Хеширования (tuple можно использовать как ключ dict)
• Функции которые требуют immutable
• Возврата нескольких значений из функции

# Tuple можно использовать как ключ (list нельзя)
my_dict = {(1, 2): 'value'}  # ✅ OK
my_dict = {[1, 2]: 'value'}  # ❌ TypeError: unhashable type

5. Deque (Double-ended queue)

Оптимизирована для вставки/удаления с обоих концов.

from collections import deque

my_deque = deque([1, 2, 3, 4, 5])

# Add to front: O(1) — мгновенно!
my_deque.appendleft(0)

# Add to back: O(1) — мгновенно
my_deque.append(6)

# Remove from front: O(1) — мгновенно!
my_deque.popleft()

# Remove from back: O(1) — мгновенно
my_deque.pop()

# Access by index: O(n) — медленно!
value = my_deque[2]  # Нужно пройти к индексу

# Search: O(n) — медленно
if 3 in my_deque:
    pass

Таблица сложности Deque:

Когда использовать Deque:

# Queue (FIFO): Deque идеален
queue = deque()
queue.append(1)      # Add to back: O(1)
queue.popleft()      # Remove from front: O(1)

# Vs List
queue_list = []
queue_list.append(1)  # Add: O(1)
queue_list.pop(0)     # Remove from front: O(n) ❌ МЕДЛЕННО!

# Stack (LIFO): List быстрее
stack = []
stack.append(1)       # O(1)
stack.pop()           # O(1)

6. Default Dict и Other Dicts

from collections import defaultdict, OrderedDict, Counter

# DefaultDict: автоматически создает default значение
default_dict = defaultdict(int)
default_dict['a'] += 1  # автоматически создает 0 если нет
# Сложность: O(1) как обычный dict

# OrderedDict: помнит порядок вставки (Python 3.7+ dict тоже)
ordered_dict = OrderedDict()
ordered_dict['z'] = 1
ordered_dict['a'] = 2
# Iterate: сохраняет порядок вставки

# Counter: подсчитывает элементы
counter = Counter(['a', 'b', 'a', 'c', 'a'])
print(counter)  # Counter({'a': 3, 'b': 1, 'c': 1})
print(counter.most_common(2))  # [('a', 3), ('b', 1)]

7. Sorted Containers (не встроенные)

Для задач где нужны отсортированные данные.

# Встроенный sorted() — O(n log n)
result = sorted([3, 1, 4, 1, 5, 9])  # O(n log n)

# Из sortedcontainers
from sortedcontainers import SortedList, SortedDict

sl = SortedList([3, 1, 4, 1, 5, 9])

# Add: O(n) — нужно найти позицию и сдвинуть
sl.add(2)  # O(n)

# Search: O(log n) — бинарный поиск!
index = sl.bisect_left(4)  # O(log n)

# Access: O(1) — как обычный список
value = sl[2]

Сравнительная таблица

            Access  Search  Insert  Delete  Space
List        O(1)    O(n)    O(n)*   O(n)*   O(n)
Dict        O(1)    O(1)    O(1)    O(1)    O(n)
Set         -       O(1)    O(1)    O(1)    O(n)
Tuple       O(1)    O(n)    -       -       O(n)
Deque       O(n)    O(n)    O(1)    O(1)    O(n)
Heap        O(1)    O(n)    O(log n) O(log n) O(n)

* Amortized для O(1) на конец

Практические примеры оптимизации

Проблема 1: Медленный поиск в List

# ❌ МЕДЛЕННО: O(n) для каждого поиска
my_list = list(range(100000))
for i in range(1000):
    if i in my_list:  # O(n) × 1000 = O(n²)
        pass

# ✅ БЫСТРО: O(1) для каждого поиска
my_set = set(range(100000))
for i in range(1000):
    if i in my_set:  # O(1) × 1000 = O(n)
        pass

Проблема 2: Медленное удаление с начала

from collections import deque

# ❌ МЕДЛЕННО: List.pop(0) = O(n)
queue = list(range(10000))
for _ in range(1000):
    queue.pop(0)  # O(n) × 1000 = O(n²)

# ✅ БЫСТРО: Deque.popleft() = O(1)
queue = deque(range(10000))
for _ in range(1000):
    queue.popleft()  # O(1) × 1000 = O(n)

Проблема 3: Частые вставки в отсортированный список

from sortedcontainers import SortedList

# Использование SortedList вместо список + сортировка
sl = SortedList()
for val in [3, 1, 4, 1, 5, 9]:
    sl.add(val)  # O(n) за элемент
    # Всегда отсортирован!
    print(sl)  # [1, 1, 3, 4, 5, 9]

Мой рекомендуемый выбор

По задаче:

1. Нужен доступ по индексу → List
2. Нужны быстрые поиски → Set/Dict
3. Нужны операции с обоих концов → Deque
4. Нужно значение по ключу → Dict
5. Нужно избежать дубликатов → Set
6. Нужны неизменяемые данные → Tuple
7. Нужны отсортированные данные → sorted() или SortedList
8. Нужен счетчик элементов → Counter

Вывод

Основное правило: выбирай коллекцию в зависимости от того какие операции ты делаешь чаще всего.

# Если часто ищешь
my_set = {1, 2, 3}  # O(1) vs List O(n)

# Если часто вставляешь с начала
from collections import deque
my_deque = deque()  # O(1) vs List O(n)

# Если нужны быстрые поиски по ключу
my_dict = {}  # O(1) vs List O(n)

Отличие может быть в 1000x раз!