Comments 10
А зачем вы везде корень квадратный таскаете (даже в расте)? Там же достаточно сразу сравнивать с квадратом расстояния
max_dist2 = max_dist**2
return [poly for poly in polygon_subset if np.dot(v := poly.center - point, v) < max_dist2]И зачем хранить x и y в отдельных объектах, когда можно завести двумерный массив и, если действительно нужен доступ к отдельно x и y, то сделать их через "слайсы" (вроде self.x = points[:,0])?
Такой код обычно, не плохо оптимизируется numba, приближаясь по скорости к нативному. Но разве это кого-то волнует, когда стоит цель переписать на раст.
Когда стоит цель показать как переписать на rust, то да никого не волнует. А реальный код вполне мог быть неподъёмен для numba
Цель изначально декларируется, улучшить производительность. И этот код подъемный для numba 100%, особенно если разложить координаты по отдельным numpy массивам. А команда конечно же скажет спасибо за то, что теперь еще надо поддерживать и код на расте.
И этот код подъемный для numba 100%
Код который в статье — может быть, однако в статье у нас...
Давайте создадим небольшую библиотеку, которая будет демонстрировать
наши исходные проблемы производительности (однако выполняющая совершенно
произвольную работу).
...совсем не тот код, который реально используется в продакшене. Пока код не показали, судить о его пригодности для Numba это гадание на кофейной гуще ¯\_(ツ)_/¯
Эх, неудачную задачу для оптимизации выбранным способом авторы статьи выбрали. Просто можно использовать так называемые QuadTrees, куда в зависимости от того, чего больше, и что фиксированнно, можно "упаковать" и прямоугольники, описанные вокруг полигонов, и точки. Итого, грубо говоря, число операций с N*M уменьшится до N*log(M)...
Во втором flamegraph видно, что большая часть времени тратится на обработку паник в trampoline-inner. Вы случайно всеми этими оптимизациями не поломали поведение программы? Или там модуль написан в стиле panic driven execution flow?
Что-то это почти один-в-один напоминает задачу поиска ближайших соседей (k-nearest neighbour, k-NN), для которой построено много классических алгоритмов, как точных, так и гораздо более быстрых приближенных. Может, туда посмотреть?
Я применил "в лоб" только один из приёмов (точный, а не приближенный), заимствованных оттуда. Это сразу дало прирост x8 на вашем тестовом примере с 1000 полигонов. Вкратце.
Замечу, что в этом примере расстояния ищутся не эффективно. Для каждой точки в приведенном примере мы пробегаем ВСЕ полигоны и считаем расстояние до их центров. Это можно значительно улучшить, если найти ОДИН ОПОРНЫЙ полигон, лежащий в интервале max_dist, и ограничить дальнейший перебор только теми полигонами, которые лежат не далее, чем (2*max_dist) от найденного опорного. Расстояния между центрами полигонов можно кэшировать в словарь словарей расстояний, построенный на идентификаторах полигонов {id0: {id1: distance, id2:distance, ...}, ...}. Вложенные словари упорядочены по distance. Поэтому отбор ближайших полигонов для найденного опорного ведем по словарю и прекращаем, как только очередная дистанция превысила 2*max_dist.
Если вам достаточно приближенного решения, то есть жадный алгоритм поиска ближайших соседей. Он имеет существенно меньшую вычислительную сложность, чем точный, и как следствие, работает радикально быстрее на большом количестве элементов.
Сказанное выше сработает, если полигоны относительно статичны (не меняются "слишком часто"), иначе пересчет кэша расстояний съест весь выигрыш.
Дальнейшие размышления. В тестовом примере рассмотрен синтетический случай. Полигоны генерятся так, что РАВНОМЕРНО распределяются по указанной области. Я подозреваю, что в вашей реальной задаче это не так, и полигоны собраны в какие-то кластеры (возможно, ограничивают более-менее статичный 3D-объект?). Если да, то:
1) Вышеуказанный алгоритм даст еще больший выигрыш, т.к. равномерное распределение полиномов для него - пожалуй, самое плохое. Наибольший выигрыш по сравнению с полным перебором он даст как раз на кластеризованных полигонах.
2) Решение можно еще качественно ускорить, явно побив полигоны по кластерам с вычисляемым центром кластера и "радиусом" границы (keyword кластерный анализ). Можно сузить изначальный поиск полигона только теми кластерами, у которых расстояние от центра до точки не более, чем max_dist+cluster_radius
Ну и еще - в синтетическом примере работа ведется со списками питона, которые заметно медленнее, чем словари. Надеюсь, списки так используются только в синтетическом примере, а не в проде. А про ускорение numpy-вычислений другие участники уже написали.
Мы просто забыли узнать скорость!
We just forgot to ask for speed!
Переводчик даже не пытался понять что он перевёл :(
Ускоряем Python в сто раз при помощи менее чем ста строк на Rust