Как решать задачу оптимизации неэффективного алгоритма

Что проверяют

Идёте ли вы от измерений или от догадок и знаете ли, где в Python-стеке данных реально теряется время. Следом часто дают кусок кода с циклом по DataFrame и просят его ускорить.

Как отвечать

Порядок действий:

• замер: сначала эталонный результат и тест, который проверит, что оптимизированная версия выдаёт то же самое. Потом профилирование: cProfile для общей картины, line_profiler для построчного разбора, py-spy для работающего процесса без перезапуска, %timeit в ноутбуке;
• сложность: ищите вложенные циклы и поиск по списку внутри цикла. x in list это O(n), x in set в среднем O(1). Соединение двух таблиц вложенными циклами заменяется хэш-соединением, то есть merge по ключу;
• векторизация: построчные iterrows() и apply в pandas заменяются операциями над колонками и выражениями NumPy, выигрыш часто измеряется порядками. Если логика не векторизуется, помогает Numba;
• память: подходящие типы (category для строк с малым числом значений, float32 вместо float64, если хватает точности), чтение по частям, ленивые вычисления в Polars;
• кэш: functools.cache или lru_cache для повторных чистых вычислений, сохранение промежуточных признаков;
• параллелизм и приближения: для задач на процессоре нужны процессы (multiprocessing, joblib), а не потоки. Иногда меняют сам алгоритм, например точный перебор соседей на ANN-индекс в FAISS.

В конце сравните время и память до и после на одних и тех же данных и назовите цену: код сложнее, результат приближённый, под кэш уходит память.

Где спотыкаются

Оптимизируют то, что показалось медленным, без профилировщика. Потом выясняется, что основное время уходит на чтение CSV, а не на переписанный цикл.

Приводят пример «заменил пузырьковую сортировку на быструю». В Python сортировку руками не пишут, встроенная sorted уже работает за O(n log n), а у быстрой сортировки худший случай O(n²).

Запускают ThreadPoolExecutor на вычислительной задаче и удивляются, что быстрее не стало. В обычной сборке CPython потоки помогают в основном на вводе-выводе и в библиотеках, которые отпускают GIL, как NumPy.