Как оптимизировать перебор списка?

Как оптимизировать перебор списка

Перебор (iteration) — одна из самых частых операций в коде. Неправильно написанный перебор может сильно замедлить приложение. Покажу реальные техники оптимизации.

1. Основные проблемы неоптимизированного кода

# ❌ Плохо: множественные обращения к атрибутам
result = []
for i in range(len(my_list)):
    result.append(my_list[i] * 2)  # Доступ к атрибуту my_list

# ❌ Плохо: функции внутри цикла
for item in items:
    print(len(item))  # len() вызывается каждый раз!

# ❌ Плохо: конкатенация строк
result = ""
for word in words:
    result = result + word  # Создаёт новую строку каждый раз!

2. List comprehensions vs циклы

List comprehension быстрее обычного цикла:

import timeit

# Способ 1: обычный цикл
def method1():
    result = []
    for i in range(1000):
        result.append(i * 2)
    return result

# Способ 2: list comprehension
def method2():
    return [i * 2 for i in range(1000)]

print(timeit.timeit(method1, number=10000))  # 0.45 сек
print(timeit.timeit(method2, number=10000))  # 0.28 сек

# List comprehension на 60% быстрее!

Правило: используй list comprehension где возможно:

# ✅ Быстро
squares = [x ** 2 for x in range(1000)]

# ✅ С условием
evens = [x for x in range(1000) if x % 2 == 0]

# ✅ С преобразованием
names_upper = [name.upper() for name in names]

# ✅ Генератор для больших данных
squares_gen = (x ** 2 for x in range(1000000))  # Не хранит всё в памяти

3. map() и filter() для функциональной обработки

# ❌ Медленнее
result = []
for item in items:
    if is_valid(item):
        result.append(transform(item))

# ✅ Быстрее
result = list(map(transform, filter(is_valid, items)))

# Ещё быстрее (ленивое вычисление)
result_lazy = map(transform, filter(is_valid, items))
for item in result_lazy:
    print(item)  # Вычисляется по мере необходимости

4. Локальные переменные работают быстрее

# ❌ Медленно: каждый раз ищет my_list.append в глобальной области
my_list = []
for i in range(1000000):
    my_list.append(i)

# ✅ Быстро: append сохранён в локальной переменной
my_list = []
append_method = my_list.append  # Локальная переменная
for i in range(1000000):
    append_method(i)

# На 10-15% быстрее!

5. Избегай множественных обращений к атрибутам

# ❌ Медленно
def process_users(users):
    result = []
    for user in users:
        if user.active and user.verified and user.admin:
            result.append(user.name.upper() + user.email.lower())
    return result

# ✅ Быстро: кэшируем атрибуты
def process_users(users):
    result = []
    for user in users:
        # Вытаскиваем атрибуты в локальные переменные
        if user.active and user.verified and user.admin:
            name = user.name
            email = user.email
            result.append(name.upper() + email.lower())
    return result

# Или ещё лучше
def process_users(users):
    return [
        f"{user.name.upper()}{user.email.lower()}"
        for user in users
        if user.active and user.verified and user.admin
    ]

6. NumPy для работы с большими наборами данных

import numpy as np
import timeit

# Способ 1: обычный Python список
def python_method():
    arr = list(range(1_000_000))
    return [x * 2 for x in arr]

# Способ 2: NumPy массив
def numpy_method():
    arr = np.arange(1_000_000)
    return arr * 2

print(timeit.timeit(python_method, number=10))  # 0.85 сек
print(timeit.timeit(numpy_method, number=10))   # 0.015 сек

# NumPy в 50 раз быстрее!

7. Итерирование с индексом оптимально

# ❌ Медленно: len() и индексирование
for i in range(len(items)):
    print(items[i])

# ✅ Быстро: прямая итерация
for item in items:
    print(item)

# ✅ Если нужны индексы: enumerate()
for i, item in enumerate(items):
    print(f"{i}: {item}")

8. zip() для одновременной итерации

# ❌ Медленно
for i in range(len(names)):
    print(names[i], ages[i])

# ✅ Быстро и понятнее
for name, age in zip(names, ages):
    print(name, age)

9. Конкатенация строк

import timeit

# ❌ Очень медленно: O(n²)
def slow_concat():
    result = ""
    for word in ["word"] * 1000:
        result = result + word
    return result

# ✅ Быстро: O(n)
def fast_concat():
    return "".join(["word"] * 1000)

# ✅ С преобразованием: для больших данных
def fast_concat_gen():
    return "".join(str(x) for x in range(1000))

print(timeit.timeit(slow_concat, number=100))    # 0.5 сек
print(timeit.timeit(fast_concat, number=100))    # 0.0001 сек

# join() в 5000 раз быстрее!

10. Выбор правильной структуры данных

# ❌ Медленно: O(n) для поиска в списке
if item in my_list:  # Проверяет каждый элемент
    pass

# ✅ Быстро: O(1) для поиска в set
if item in my_set:  # Хэширование
    pass

# Сравнение
import timeit

my_list = list(range(10000))
my_set = set(range(10000))

print(timeit.timeit(
    lambda: 9999 in my_list,
    number=100000
))  # 0.3 сек

print(timeit.timeit(
    lambda: 9999 in my_set,
    number=100000
))  # 0.001 сек

# Set в 300 раз быстрее!

11. Полная оптимизация: пример

# Задача: найти все уникальные пары пользователей, у которых одинаковый статус

# ❌ Очень медленно: O(n³)
def slow_approach(users):
    result = []
    for i in range(len(users)):
        for j in range(len(users)):
            if users[i].status == users[j].status and i != j:
                pair = (users[i].id, users[j].id)
                if pair not in result:
                    result.append(pair)
    return result

# ✅ Быстро: O(n)
def fast_approach(users):
    from collections import defaultdict
    
    # Группируем по статусу
    by_status = defaultdict(list)
    for user in users:
        by_status[user.status].append(user.id)
    
    # Находим пары
    result = set()
    for status, user_ids in by_status.items():
        for i, uid1 in enumerate(user_ids):
            for uid2 in user_ids[i+1:]:
                result.add((min(uid1, uid2), max(uid1, uid2)))
    
    return list(result)

Чеклист оптимизации

1. Профилируй — py-spy, cProfile
2. Используй list comprehension вместо циклов
3. Кэшируй атрибуты в локальных переменных
4. Используй map/filter для функциональной обработки
5. Выбирай правильную структуру (set vs list)
6. NumPy для больших данных
7. join() для строк, не конкатенацию
8. Генераторы для больших последовательностей
9. Избегай множественных вызовов функций в цикле
10. Тестируй с реальными данными

Вывод

Можно улучшить перебор на 10-100x не меняя алгоритм. Начни с профилирования, потом применяй техники выше. Помни: микро-оптимизации важны только если они показывают результаты на профайлере.