Пример фрагмента (наивная реализация попарных Евклидовых расстояний):
def pairwise_distances(X):
n = len(X)
D = [[0.0]*n for _ in range(n)]
for i in range(n):
xi = X[i]
for j in range(n):
xj = X[j]
s = 0.0
for k in range(len(xi)):
d = xi[k] - xj[k]
s += d*d
D[i][j] = s**0.5
return D
Возможные оптимизации по времени и памяти (без изменения интерфейса):
- Алгоритмические улучшения
- Использовать симметрию матрицы расстояний: вычислять только для $j>i$ и копировать в симметричную ячейку — экономия ~2× работы/памяти.
- Перейти от тройного Python-цикла к линейной алгебре: воспользуйтесь формулой $\Vert a-b{\Vert }^2=\Vert a{\Vert }^2+\Vert b{\Vert }^2-2a\cdot b$ и BLAS-операциями (умножение матриц) — часто сильное ускорение за счёт C/Fortran-кода.
- Для больших наборов, когда нужны ближайшие соседи, заменить вычисление всех пар на приближенные структуры (FAISS, Annoy, KDTree) — уменьшает сложность с $O(n^{2}d)$ до ~$O(n\log n)$ или лучше для поиска топ-k.
- Оптимизации реализации
- Переписать на NumPy: хранить X как contiguous ndarray, использовать dot/BLAS вместо Python-циклов.
- Вычислять блоками (tiling / chunking), чтобы уменьшить пиковую память: обрабатывать подматрицы размера B×B.
- Использовать типы с меньшей точностью: float32 вместо float64 — экономия памяти и часто ускорение.
- JIT-компиляция: numba для компактных циклов или Cython, если не получается полностью векторизовать.
- Параллелизация по блокам: joblib, multiprocessing или многопоточность BLAS (контролировать OMP_NUM_THREADS).
- Избегать лишних аллокаций: заранее выделять буферы, переиспользовать массивы, не создавать временные большие массивы.
- Экономия памяти
- Не хранить всю матрицу D, если можно: возвращать генератор блоков или сохранять только треугольную часть.
- Для очень больших X использовать np.memmap, чтобы не держать весь массив в оперативной памяти.
- Хранить результаты компрессированно или на диске при необходимости.
Инструменты профилирования и методика поиска узких мест
- CPU / время
- cProfile (встроенный) + snakeviz для визуализации — хорош для поиска "горячих" функций.
- py-spy или pyinstrument — sampling-профайлер с низким оверхедом, показывает "горячие" стеки.
- line_profiler (строчный) — подробная статистика по строкам (нужны @profile).
- timeit / microbenchmarks для сравнений мелких изменений.
- Память / аллокации
- memory_profiler — отслеживает потребление памяти по строкам (использует @profile).
- tracemalloc — отслеживает выделения Python-объектов и позволяет сравнивать снимки.
- valgrind massif / massif-visualizer — для C-уровня и расширений.
- scalene — одновременно CPU+memory профайлер, показывает выделения по строкам и время.
- Профилирование C/BLAS
- perf / VTune / Intel Advisor — для анализа системного времени, когда большая часть работы в нативном коде.
- Проверить активность BLAS (MKL/OpenBLAS) через переменные окружения и утилиты, т.к. многопоточность BLAS может влиять на производительность.
Рекомендуемая методика
1. Собирать репрезентативный набор данных и базовый тайм/мемори-бенчмарк.
2. Запускать sampling-профайлер (py-spy) и cProfile, чтобы найти горячие функции и тяжелые строки.
3. Для подозрительных мест применять line_profiler и memory_profiler / tracemalloc.
4. Пробовать одно изменение за раз (векторизация, типы, блокирование, numba) и сравнивать метрики.
5. Для крупных алгоритов проверять альтернативные алгоритмы (approx NN, деревья, графы) и сохранять интерфейс.
6. Контролировать побочные эффекты (точность при float32, многопоточность BLAS) и проводить регрессионные тесты.
Важные оценки сложности (для данного примера)
- Наивный алгоритм: время $O(n^{2}d)$, память для матрицы расстояний $O(n^2)$.
- После частичной оптимизации (симметрия + блоки + BLAS): время по-прежнему $O(n^{2}d)$ но с меньшими константами; можно снизить пиковую память через блокирование до ~$O(Bd)$ в буфере.
Если нужно, могу показать конкретный скорректированный вариант кода (NumPy/numba/блочное вычисление) и команды для запуска профайлеров.