Алгоритмическая сложность, I/O операции, N+1 проблемы, оптимизации
Преждевременная оптимизация — корень всех зол. Но игнорирование производительности — гарантия проблем.
| Сложность | Название | Пример | 10 элементов | 1000 элементов |
|---|---|---|---|---|
| O(1) | Константная | Доступ по индексу | 1 оп | 1 оп |
| O(log n) | Логарифмическая | Бинарный поиск | 4 оп | 10 оп |
| O(n) | Линейная | Перебор списка | 10 оп | 1000 оп |
| O(n log n) | Линейно-логарифмическая | Сортировка | 33 оп | 10 000 оп |
| O(n²) | Квадратичная | Два вложенных цикла | 100 оп | 1 000 000 оп |
| O(2ⁿ) | Экспоненциальная | Рекурсивный Fibonacci | 1024 оп | 🚀 катастрофа |
# ❌ Плохо: O(n²)
def find_duplicates(items):
duplicates = []
for i in range(len(items)):
for j in range(i + 1, len(items)):
if items[i] == items[j]:
duplicates.append(items[i])
return duplicates
# ✅ Хорошо: O(n)
def find_duplicates(items):
seen = set()
duplicates = set()
for item in items:
if item in seen:
duplicates.add(item)
else:
seen.add(item)
return list(duplicates)Что проверять:
# ❌ N+1 запросов
posts = Post.objects.all() # 1 запрос
for post in posts:
print(post.author.name) # N запросов (по одному на пост)
# Итого: 1 + N запросов# ✅ Django: select_related (для ForeignKey)
posts = Post.objects.select_related('author').all()
# 1 запрос с JOIN
# ✅ Django: prefetch_related (для ManyToMany)
posts = Post.objects.prefetch_related('tags').all()
# 2 запроса: один для постов, один для тегов
# ✅ SQLAlchemy: joinedload
from sqlalchemy.orm import joinedload
posts = session.query(Post).options(joinedload(Post.author)).all()Что проверять:
select_related/prefetch_related/joinedload# ❌ Плохо: чтение всего файла в память
def process_large_file(path):
with open(path) as f:
content = f.read() # Может занять всю память!
for line in content.split('\n'):
process(line)
# ✅ Хорошо: потоковое чтение
def process_large_file(path):
with open(path) as f:
for line in f: # Читает по строке
process(line)# ❌ Плохо: последовательные запросы
import requests
def fetch_all_users(user_ids):
results = []
for user_id in user_ids:
response = requests.get(f'https://api.example.com/users/{user_id}')
results.append(response.json())
return results # 100 пользователей = 100 запросов последовательно
# ✅ Хорошо: параллельные запросы
import asyncio
import aiohttp
async def fetch_all_users(user_ids):
async with aiohttp.ClientSession() as session:
async def fetch(user_id):
async with session.get(f'https://api.example.com/users/{user_id}') as resp:
return await resp.json()
tasks = [fetch(user_id) for user_id in user_ids]
return await asyncio.gather(*tasks) # ПараллельноЧто проверять:
# ❌ Без кэширования
def get_expensive_data(user_id):
return db.query("SELECT ... complex join ... WHERE user_id = ?", user_id)
# ✅ С кэшированием
from functools import lru_cache
@lru_cache(maxsize=1000)
def get_expensive_data(user_id):
return db.query("SELECT ... complex join ... WHERE user_id = ?", user_id)
# ✅ С кэшированием и TTL
from redis import Redis
import json
redis = Redis()
def get_user_data(user_id):
key = f"user:{user_id}"
cached = redis.get(key)
if cached:
return json.loads(cached)
data = db.query("SELECT ... WHERE user_id = ?", user_id)
redis.setex(key, 300, json.dumps(data)) # TTL 5 минут
return dataЧто проверять:
# ❌ Плохо: создаёт большой список в памяти
def get_squares(n):
return [x ** 2 for x in range(n)] # Все в памяти
result = sum(get_squares(1000000)) # 1M integers в памяти
# ✅ Хорошо: генератор
def get_squares(n):
for x in range(n):
yield x ** 2 # По одному значению
result = sum(get_squares(1000000)) # O(1) память# ❌ Плохо: ненужное копирование
def process_data(data):
copied = data.copy() # Зачем?
result = transform(copied)
return result
# ✅ Хорошо: работа с оригиналом (если мутация допустима)
def process_data(data):
return transform(data)| Инструмент | Что измеряет |
|---|---|
| cProfile | Время выполнения функций |
| line_profiler | Время по строкам кода |
| memory_profiler | Использование памяти |
| py-spy | Профилирование в продакшене |
| Django Debug Toolbar | SQL запросы, время рендеринга |
# Запуск профилировщика
python -m cProfile -o output.prof myscript.py
# Анализ результатов
python -m pstats output.prof# ❌ Плохо: O(n²) из-за создания новых строк
def build_csv(rows):
result = ""
for row in rows:
result += ",".join(row) + "\n" # Создаёт новую строку каждый раз
return result
# ✅ Хорошо: O(n)
def build_csv(rows):
lines = [",".join(row) for row in rows]
return "\n".join(lines)# ❌ Плохо: O(n) поиск в списке
def is_valid_user(user_id, valid_ids):
return user_id in valid_ids # valid_ids — список
# ✅ Хорошо: O(1) поиск в set
def is_valid_user(user_id, valid_ids):
return user_id in set(valid_ids) # Или хранить как set# ❌ Плохо: несколько проходов по данным
def analyze_data(items):
total = sum(items)
average = total / len(items)
max_value = max(items)
min_value = min(items)
count = len(items)
return {'total': total, 'avg': average, 'max': max_value, 'min': min_value, 'count': count}
# ✅ Хорошо: один проход
def analyze_data(items):
if not items:
return {'total': 0, 'avg': 0, 'max': 0, 'min': 0, 'count': 0}
total = max_value = min_value = items[0]
count = 1
for item in items[1:]:
total += item
count += 1
max_value = max(max_value, item)
min_value = min(min_value, item)
return {'total': total, 'avg': total / count, 'max': max_value, 'min': min_value, 'count': count}Ключевая мысль: Оптимизируйте только после измерения. Используйте профилировщик, чтобы найти узкие места, а не предполагайте.
Вопросы ещё не добавлены
Вопросы для этой подтемы ещё не добавлены.