Что быстрее: список или словарь?

# Что быстрее: список или словарь?

Это не простой вопрос «быстрее-медленнее». Сравнение зависит от операции, которую вы выполняете. Давайте разберёмся детально.

Поиск элемента (самое важное различие)

Поиск по индексу (список)

my_list = [1, 2, 3, 4, 5]
value = my_list[2]  # O(1) — константное время!

Поиск по значению (список)

my_list = [1, 2, 3, 4, 5]
if 3 in my_list:  # O(n) — линейное, медленно!
    pass

Поиск по ключу (словарь)

my_dict = {1: 'a', 2: 'b', 3: 'c'}
value = my_dict[2]  # O(1) — очень быстро!

Таблица сложности операций

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

Когда список быстрее

# Если нужен доступ по индексу
data = [10, 20, 30, 40, 50]
for i in range(len(data)):
    print(data[i])  # Быстро — O(1) на каждый доступ

Когда словарь быстрее

# Если нужно часто искать и проверять наличие
users = {
    1: {'name': 'Alice'},
    2: {'name': 'Bob'},
    1000: {'name': 'Charlie'},
}

user = users[1000]  # O(1) — быстро, даже с большой коллекцией!

if 1000 in users:  # O(1) — очень быстро!
    pass

Тест производительности

import time

# Тест 1: Поиск по индексу (список выигрывает)
my_list = list(range(1_000_000))

start = time.time()
for _ in range(100_000):
    _ = my_list[500_000]
print(f"Список по индексу: {time.time() - start:.4f}s")

# Тест 2: Поиск значения (словарь выигрывает)
start = time.time()
for _ in range(100_000):
    _ = 500_000 in my_list  # O(n) внутри!
print(f"Список поиск: {time.time() - start:.4f}s")

my_dict = {i: i for i in range(1_000_000)}
start = time.time()
for _ in range(100_000):
    _ = 500_000 in my_dict  # O(1) — мгновенно!
print(f"Словарь поиск: {time.time() - start:.4f}s")

Расход памяти

import sys

my_list = list(range(1000))
my_dict = {i: i for i in range(1000)}

print(f"Список: {sys.getsizeof(my_list)} байт")
print(f"Словарь: {sys.getsizeof(my_dict)} байт")
# Словарь занимает больше памяти!

Выводы

1. Список быстрее для:

   • Доступа по известному индексу
   • Сохранения порядка элементов
   • Экономии памяти
   • Итерации в порядке добавления

2. Словарь быстрее для:

   • Поиска и проверки наличия элемента
   • Быстрого доступа по ключу
   • Когда ключи — уникальные идентификаторы
   • Группировки данных по категориям

Правильный выбор

# Если нужны индексы и порядок → список
students = ['Alice', 'Bob', 'Charlie']
first = students[0]

# Если нужны быстрые поиски → словарь
student_ids = {'Alice': 1, 'Bob': 2, 'Charlie': 3}
alice_id = student_ids['Alice']

# Если нужны оба → комбинация
student_list = ['Alice', 'Bob']
student_index = {name: idx for idx, name in enumerate(student_list)}

Вывод: нет абсолютного победителя. Выбор зависит от того, какие операции вам нужны. В современном Python для поиска всегда используй словарь или множество (set) вместо проверки наличия в списке!