Troubleshooting — DSA 01

Симптомы

• Скрипт обрабатывает 1M событий, добавляя каждое в начало списка — занимает минуты вместо секунд. timeit показывает, что время на одну insert растёт линейно с длиной списка.

Причина

list.insert(0, ...) в CPython — O(n): все существующие элементы сдвигаются вправо через memmove. N таких вставок дают суммарно O(n^2). На 1M это около 10^12 операций сдвига.

Решение

1. Используй collections.deque и appendleft() — O(1) амортизированно за счёт doubly-linked-list блоков. Если порядок не важен — append() в конец и потом reverse(). Если важна последующая random-access итерация — copy в list только в самом конце.

Симптомы

• Дедупликация через if x not in result: result.append(x) на 200K элементах работает 30+ секунд. Профайлер показывает почти всё время в операторе in.

Причина

Оператор in на list — O(n), линейный поиск с равенством. Внутри цикла на N элементах получается O(n^2). Для 200K — это 4*10^10 операций сравнения.

Решение

1. Используй set для проверки членства: seen = set(); if x not in seen: seen.add(x); result.append(x). Оператор in на set — O(1) средний. Если порядок не важен — просто list(set(data)). Если нужна стабильность порядка с Python 3.7+ — dict.fromkeys(data).

Симптомы

• Сборка большого CSV из 100K строк через result += line занимает 10 секунд. Память во время работы растёт неравномерно скачками.

Причина

Строки в Python immutable, поэтому s += t создаёт новую строку и копирует обе. На N итерациях суммарно O(n^2) копирования байт. CPython иногда оптимизирует in-place при refcount=1, но на это нельзя полагаться.

Решение

1. Накапливай куски в list и в конце сделай ''.join(parts) — O(n) суммарно. Для очень больших данных — пиши прямо в io.StringIO или сразу в файл через csv.writer.

Симптомы

• Кастомный связный список из 10M узлов проходится за 8 секунд. Тот же объём данных в list — 0.15 секунды. Оба прохода O(n) теоретически.

Причина

Pointer chasing: каждый node.next — это указатель в произвольное место кучи. Prefetcher CPU не угадывает следующий адрес, каждое обращение почти всегда cache miss с 60+ ns латентностью. Массив укладывается в cache line по 64 байта — 8-16 элементов на одну загрузку.

Решение

1. Если нужна частая итерация — храни данные в list или numpy.ndarray, а не в linked list. Если нужны head/tail O(1) операции и итерация — collections.deque (блоки по 64 элемента дают приличную spatial locality). Linked list оправдан только в очень редких сценариях: разделяемые подсписки, точечные O(1) splice.

Симптомы

• ETL читает 10M записей в dict, lookup-ы в конце прохода стали медленнее в 100 раз. Профайлер показывает аномально долгие dict[key] вызовы.

Причина

Ключи имеют коллизию по хешу — все попадают в один кластер. Например, кастомный __hash__ возвращает 0 для всех объектов, либо ключи — атакующие строки с pre-computed коллизиями (SipHash без seed). Probing проходит весь массив.

Решение

1. Проверь распределение hash(key) для своих ключей: collections.Counter(hash(k) & 0xFF for k in keys). Если идёт перекос — поправь __hash__, чтобы он смешивал все поля. Для строк из недоверенного источника всегда используется SipHash с PYTHONHASHSEED, проблема исключена.

Симптомы

• data.sort(key=lambda x: random.random()) пробует «перемешать» список, но результат каждый раз новый и иногда непредсказуемый.

Причина

Timsort вызывает key(x) для каждого элемента один раз и кэширует. Но если key имеет side effects (random) — сортировка получает несогласованный порядок (нарушает strict weak ordering). Поведение undefined, конкретный результат зависит от количества сравнений.

Решение

1. Для перемешивания используй random.shuffle(data) — O(n), Fisher-Yates. Никогда не клади side effects или недетерминированные вычисления в key. Если key дорогой — вычисли заранее в list и используй sorted(zip(keys, data)).

Симптомы

• BST-обход 100K узлов или DFS на длинной цепочке падает с «RecursionError: maximum recursion depth exceeded» — Python 3 ограничивает стек 1000 кадрами по умолчанию.

Причина

Каждый рекурсивный вызов кладёт frame в Python-стек: локальные переменные, return address. На больших деревьях стек переполняется до выхода с результатом. Это не stack overflow ОС, а sys.setrecursionlimit.

Решение

1. Перепиши обход в итеративный с явным стеком: stack = [root]; while stack: node = stack.pop(); ... stack.append(node.right); stack.append(node.left). Работает на произвольной глубине, ограниченной только RAM. Для tail-recursive вызовов sys.setrecursionlimit(10**6) — крайняя мера, лучше итерация.

Симптомы

• Скрипт читает CSV на 5GB через csv.reader и собирает все строки в list для дальнейшей обработки. Процесс убивается ОС или Python кидает MemoryError на 12GB RAM.

Причина

list из 50M dict-ов — это ~10GB только на overhead Python-объектов (каждый dict с короткими ключами весит ~232 байт, не считая values). PyObject pointer = 8 байт, плюс заголовок каждого объекта ~16 байт.

Решение

1. Используй streaming: обрабатывай по чанкам через pandas.read_csv(..., chunksize=100000) или iterate через csv.reader без накопления. Для аналитики — Polars/DuckDB читают в столбцовом формате с в 5-10 раз меньшим overhead. Если нужно много раз читать — конвертируй в Parquet.

Симптомы

• sys.getsizeof([0]*1_000_000) возвращает 8 млн с копейками байт, а sys.getsizeof([{} for _ in range(1_000_000)]) — те же миллионы, хотя dict-ов внутри миллион.

Причина

sys.getsizeof измеряет только сам объект-контейнер, не следуя по ссылкам. Для list это 56 байт заголовка + 8 байт на каждый PyObject*. Сами объекты-элементы (int, dict, str) считаются отдельно.

Решение

1. Используй pympler.asizeof для рекурсивного измерения, либо tracemalloc.get_traced_memory() для всей программы. Альтернатива — посчитать вручную: размер контейнера + sum(sys.getsizeof(x) for x in container).

Симптомы

• Стрим-агрегация скользящим окном на 1 минуту реально хранит 30+ минут событий. RAM-usage растёт линейно от времени работы, а не ограничен размером окна.

Причина

Очистка окна делается по ошибочному условию (например, по индексу, а не по timestamp). Либо используется list с del list[0] (O(n), плюс не очищается из-за условия), вместо deque. Иногда из-за хранения ссылок на старые события в логах.

Решение

1. Используй collections.deque с maxlen, либо явный popleft по предикату «timestamp старше now - window». Замерь реальный размер окна через len() и sys.getsizeof по чек-поинтам. Закрытые ссылки — через weakref если нужны для logging.

Симптомы

• bisect.bisect_left(sorted_arr, target) и bisect.bisect_right на массиве с повторяющимися значениями дают разные индексы, и логика «если bisect нашёл — элемент есть» иногда ошибается.

Причина

bisect_left возвращает первую позицию, куда можно вставить target, сохраняя порядок (то есть индекс первого вхождения, если есть). bisect_right — индекс после последнего вхождения. Сам по себе bisect не проверяет наличие — это off-by-one кейс.

Решение

1. Чтобы найти target: i = bisect_left(arr, target); if i < len(arr) and arr[i] == target: found. Чтобы найти range дубликатов: lo = bisect_left, hi = bisect_right, count = hi - lo. Не предполагай, что bisect сам делает equality check.

Симптомы

• DFS-обход графа из БД не завершается, забивает память. Если поставить sys.setrecursionlimit(10**4) — падает с RecursionError на тех же данных.

Причина

В графе есть цикл (например, A -> B -> A в lineage), а DFS не отслеживает visited-вершины. Каждое посещение запускает обход тех же узлов заново. Без visited-set DFS на циклическом графе не завершится.

Решение

1. Всегда веди visited = set() и проверяй if node in visited: continue перед обходом. Для обнаружения циклов в DAG — 3-цветная разметка (WHITE/GRAY/BLACK): встретили GRAY-вершину = цикл. Для топологической сортировки используй алгоритм Кана через очередь in-degree=0.

Симптомы

• Сортировка по (region, date) теряет порядок по date внутри region при ре-сортировке другим ключом. Хотя Timsort стабильна.

Причина

Стабильность Timsort означает «равные элементы сохраняют относительный порядок». Но если сортировать одним ключом, а потом другим — выигрывает последний ключ, остальное сохраняется только в пределах равенства по последнему ключу.

Решение

1. Для multi-key всегда сортируй одним вызовом с tuple-ключом: data.sort(key=lambda x: (x.region, x.date)). Либо последовательно от младшего ключа к старшему: sorted(data, key=lambda x: x.date); sorted(_, key=lambda x: x.region) — Timsort-стабильность гарантирует, что внутри region порядок по date сохранится.

Симптомы

• Попытка использовать list как ключ dict (d[[1,2,3]] = 'x') или элемент set падает с TypeError: unhashable type: 'list'.

Причина

Хеш-таблицы требуют, чтобы ключ был неизменяемым: hash(key) должен оставаться постоянным всё время, пока ключ в таблице. Если разрешить mutable ключ, его hash мог бы измениться после insert, и lookup не нашёл бы элемент.

Решение

1. Конвертируй mutable в immutable: list -> tuple, set -> frozenset, dict -> tuple(sorted(d.items())). Для кастомных классов — реализуй __hash__ и __eq__ согласованно (равные объекты должны иметь равный hash) и сделай поля immutable либо @dataclass(frozen=True).

Симптомы

• 0.1 + 0.2 == 0.3 возвращает False. Сортировка по float-ключу или dedup чисел даёт неверные результаты на близких значениях.

Причина

IEEE 754 binary64: десятичная дробь 0.1 в двоичной системе — бесконечная дробь, представляется приближённо. После арифметики младшие биты не совпадают с прямым представлением 0.3.

Решение

1. Сравнивай через math.isclose(a, b, rel_tol=1e-9) или abs(a-b) < eps. Для денежных значений используй decimal.Decimal с явной точностью. Не клади float в dict как ключ напрямую — округляй до нужной точности или используй decimal/int (центы вместо рублей).

Симптомы

• Скрипт пытается дедуплицировать 5 миллиардов event_id через set(). Падает с MemoryError на ~50GB RAM, хотя машина 64GB.

Причина

set из 5B 16-байтных UUID — это минимум 5B * (size_of(PyObject*) + size_of(PyUnicodeObject)) ~ 5B * 60 байт = 300GB. Даже с компактным хранением как bytes — десятки GB только на сами объекты, плюс bucket-overhead set.

Решение

1. Используй Bloom filter (pybloom-live, mmh3): на 5B элементов с false positive rate 0.001 — около 8GB битового массива. Если нужна точная дедупликация — внешняя сортировка с merge (sort -u или DuckDB DISTINCT с spill to disk). Для streaming — HyperLogLog для approximate distinct count.

Симптомы

• Поиск top-10 пользователей по выручке из 100M записей через sorted(data, reverse=True)[:10] занимает 45 секунд и держит весь список в RAM.

Причина

Полная сортировка — O(N log N), для 100M это ~2.7 миллиарда сравнений. Плюс sorted() создаёт новый list на N элементов — лишняя память. Top-K не требует полного порядка остальных N-K элементов.

Решение

1. Используй heapq.nlargest(10, data, key=lambda x: x.revenue) — O(N log K) через min-heap размера K. Для K=10, N=100M это ~330M сравнений — на порядок быстрее. Память — O(K). Для streaming — поддерживай heap размера K вручную: heappush + heappop при переполнении.

Симптомы

• Пайплайн обработки 50M записей падает на 49M из-за бага. Перезапуск начинает с нуля. Cycle of pain — каждый дебаг занимает 2 часа.

Причина

Промежуточные state-ы держатся в памяти Python и не сериализуются. После SIGTERM/OOM/exception всё в GC. Нет идемпотентности по chunk-ам.

Решение

1. Разбей на батчи фиксированного размера (10K-100K записей), пиши результат каждого батча в Parquet/SQLite/PostgreSQL. Веди checkpoint-file с last_processed_offset. При перезапуске — пропускай уже обработанные чанки. Для оркестрации используй Airflow или Prefect с tasks-уровнем retry.

Симптомы

• Стриминг с window-агрегацией на Kafka-потоке имеет p50 = 5ms, но p99 = 800ms. Скачки латентности коррелируют с моментами очистки окна.

Причина

Окно реализовано через list с del list[0] для старых элементов — O(n) на каждое удаление. При большом окне (N=10K) операция занимает миллисекунды, блокируя event loop.

Решение

1. Используй collections.deque — popleft O(1). Для time-based windows — храни (timestamp, value) и popleft в while-цикле, пока самый старый старше cutoff. Для агрегаций sum/count — обновляй инкрементально (running_sum += new - removed), не пересчитывай заново.

Симптомы

• Кастомный O(n) подсчёт уникальных через hash через мою хеш-функцию — медленнее sorted(data) для n < 1000.

Причина

Big-O скрывает константы. O(n) с большой константой (моя hash-функция в чистом Python) проигрывает O(n log n) с маленькой константой (Timsort, написанный на C). Для маленьких n константы доминируют.

Решение

1. Меряй на реальных размерах. Для маленьких списков (n < 100) линейный поиск может быть быстрее hash и binary search из-за cache locality. Для больших — выбирай по асимптотике. Если есть Python-уровневая обработка элементов внутри O(n) — почти всегда проиграешь C-уровневому O(n log n) или O(n^2).

Симптомы

• BFS на графе lineage (10M вершин, средний degree 50) пытается выделить queue на сотни миллионов записей, OOM.

Причина

BFS хранит весь frontier — вершины, до которых текущий уровень дошёл. На графе с большим branching factor frontier растёт экспоненциально по уровням. Память — O(V) в худшем случае, но константа большая (8 байт указатель + overhead Python-int + bookkeeping).

Решение

1. Если граф направленный и нужен любой обход — DFS использует O(h) памяти (глубина рекурсии). Если нужен именно shortest-path-обход — рассмотри bidirectional BFS (вдвое меньше глубина). Для очень больших графов — обработка по чанкам, материализация frontier на диск, или внешний фреймворк (NetworkX -> graph-tool, GraphFrames в Spark).

Симптомы

• Попытка получить максимум через heapq.heappop(heap) возвращает минимальный элемент. heapq не имеет heappop_max.

Причина

Python heapq реализует только min-heap. Это явно описано в документации, но интуиция «куча» обычно подразумевает max-heap.

Решение

1. Инвертируй знаки: heappush(heap, -value), потом -heappop(heap) даст максимум. Для tuple-ключей: push (-key, value), pop первого элемента — максимум по key. Альтернатива — heapq._heapify_max и _siftdown_max (внутренние, но рабочие). Для production — sortedcontainers.SortedList или явная реализация max-heap.

Симптомы

• Цикл for j in range(N): for i in range(N): total += matrix[i][j] (по столбцам) работает в 5-10 раз медленнее, чем по строкам, на одной и той же матрице 5000x5000.

Причина

Numpy/list of lists хранит данные row-major: строка целиком лежит в непрерывной памяти. Доступ по столбцам прыгает через всю строку (8*5000 = 40000 байт), каждый шаг — потенциальный cache miss. Кэш-линии (64 байта) загружаются и тут же выкидываются — cache thrashing.

Решение

1. Меняй порядок циклов: внешний — строка, внутренний — столбец. Если задача требует доступа по столбцам — транспонируй матрицу заранее (matrix.T в numpy создаёт view, но материализуй через .copy() для последующих доступов в кэш-friendly режиме). Для column-store оптимизации используй pandas/Polars или DuckDB.

Симптомы

• Между двумя checkpoint tracemalloc.take_snapshot() видна разница в +500MB, gc.collect() возвращает 0 и не уменьшает потребление.

Причина

Объекты держатся живыми ссылками: глобальные переменные, замыкания, registered callbacks, кэши. GC находит только циклические ссылки — обычное удержание через refcount > 0 GC не трогает.

Решение

1. Найди живые ссылки: objgraph.show_most_common_types() даст топ по количеству объектов в куче. objgraph.show_backrefs() покажет, кто держит конкретный объект. Часто виноваты глобальные dict-кэши, lru_cache без maxsize, незакрытые file handles, события в очередях без consumer.

Симптомы

• Цикл sum(x for x in arr if x > threshold) на отсортированном массиве работает в 2-3 раза быстрее, чем на shuffled. Тот же big-O O(n), та же память.

Причина

На отсортированном массиве предикат x > threshold даёт длинные серии True и длинные серии False — branch predictor предугадывает идеально. На случайных данных — 50/50 промахи, каждый промах = 10-20 тактов простоя pipeline.

Решение

1. Для критичных горячих циклов на больших массивах — переходи на numpy: arr[arr > threshold].sum() векторизуется через SIMD, без бранчей. Если данные можно предобработать (отсортировать) — branchy-логика после сортировки сильно ускоряется. Альтернатива — branchless-код (например, mask вместо if).

Симптомы

• Сравнение Counter(items) и собственного defaultdict(int) loop показывает, что defaultdict быстрее в 2 раза на 10M элементах. Хотя оба О(n).

Причина

Counter — это dict с дополнительной логикой (методы most_common, операции с другими Counter). Конструктор делает Counter(iterable) -> внутренне dict + дополнительная _missing_-логика. defaultdict(int) использует чистый dict-protocol через __missing__ и нативный int.__add__.

Решение

1. Если нужно только подсчитать — defaultdict(int) с d[key] += 1 или dict.get(key, 0) + 1. Counter оправдан, когда нужны most_common, операции between counters, или удобство кода важнее производительности. Для очень горячих циклов — pandas.value_counts или numpy.unique(arr, return_counts=True).

Симптомы

• BST с глубиной 50, но шириной 10K на уровень. Обход padает с RecursionError на 1100-й вершине.

Причина

RecursionError срабатывает на превышении sys.getrecursionlimit() (1000 по умолчанию) — учитывается общая глубина стека Python-кадров, включая накопленные вызовы хелперов. Не имеет значения, дерево «широкое» или «глубокое» в смысле графа — важна глубина именно функциональных вызовов.

Решение

1. Перепиши обход в итеративный с явным stack/queue: для BFS — collections.deque, для DFS — list как stack. Для in-order/post-order traversal — явный stack с маркерами posetility. Если рекурсия неустранима (например, для readability на не-critical-пути) — sys.setrecursionlimit, но осторожно: реальный stack overflow ОС даст segfault.

Симптомы

• Join 10M строк fact-таблицы с 100K dim-таблицы делается через два вложенных list-loop. Время — 30 минут.

Причина

Вложенный цикл — это O(N*M) = 10^12 сравнений. Linear scan по dim для каждой fact-записи. Это hash join на бумаге, но реализован как nested loop.

Решение

1. Построй dict (hash table) из dim по join-key один раз — O(M). Lookup для каждой fact — O(1). Суммарно O(N+M) = ~10M операций. Если данные не помещаются — используй pandas.merge (внутри hash join), либо DuckDB/SQLite с явным индексом. Для больших join — Spark broadcast join с broadcasted dim.

Симптомы

• Тест проходит 9 раз из 10, в одном случае order ключей dict отличается, snapshot-сравнение падает.

Причина

В Python 3.3+ hash(str), hash(bytes) рандомизирован при старте процесса (PYTHONHASHSEED=random по умолчанию). Это защита от hash-flooding атак, но мешает воспроизводимости snapshots, которые зависят от порядка ключей или probing-последовательности.

Решение

1. Для тестов: установи PYTHONHASHSEED=0 (или фиксированное число) перед запуском. Лучшее решение — не полагайся на порядок dict/set в логике, делай явный sort при сравнении. Для серилизации — используй json.dumps(d, sort_keys=True). Для snapshot-тестов с pytest — sort items в fixture.

Симптомы

• for x in lst: if predicate(x): lst.remove(x) — оставляет половину элементов, которые должны быть удалены, плюс работает медленно.

Причина

Две проблемы: (1) lst.remove(x) — O(n) (поиск + сдвиг), итого O(n^2). (2) модификация list во время итерации — индексы итератора съезжают, элементы пропускаются.

Решение

1. Создай новый list через comprehension: result = [x for x in lst if not predicate(x)] — O(n), читаемо, без багов. Если нужна модификация in-place — итерируй по копии: for x in lst[:]: lst.remove(x). Для больших списков — filter() с генератором или numpy boolean mask.