Как создать функцию, которая делает это с нуля, а затем ускорить ее в 80 раз с помощью numba
Как правило, найти ближайшую дорогу к заданной точке несложно, но когда мы говорим о миллионах точек и тысячах дорог, все может немного усложниться. Я хочу рассказать вам, как создать функцию, которая делает это с нуля, а затем ускорить ее в 80 раз с помощью Numba.
Итак, в этом тексте я собираюсь решить следующую задачу:
Данный
- 7 миллионов точек, каждая определяется своей долготой и широтой
- 10 тысяч дорог в графе. Дороги хранятся в виде графа OSMnx
To do
Для каждой дороги на графике найдите количество точек, к которым эта дорога является ближайшей.
Что по сути нужно, так это преобразовать первую карту во вторую, но с гораздо большим количеством точек и улиц.
К сожалению, данная задача слишком тяжела для стандартных функций Shapely, поэтому нам необходимо сделать собственное решение.
1. Геометрия
Начнем с самого простого подхода. Расстояние от начала координат до линии, определяемой двумя точками, можно рассчитать по следующей формуле:
Мы можем использовать эту формулу для расчета расстояния от любой заданной точки. Все, что для этого нужно, — преобразовать координаты так, чтобы данная точка оказалась в начале координат.
Давайте напишем простую функцию, которая перебирает все улицы и находит ближайшую.
Единственная проблема заключается в том, что в реальной жизни улицы не бесконечны и обычно определяются своими конечными точками.
Рассмотрим ситуацию на картинке. В то время как точка А находится ближе к первому отрезку, приведенная выше формула говорит нам, что точка А ближе ко второму отрезку, потому что его продолжение лежит в непосредственной близости от точки.
Чтобы исключить эти улицы, введем правило, согласно которому перпендикулярная линия, идущая от точки данных к улице, должна пересекать ее между своими конечными точками. В противном случае улица считается неактуальной. Я хотел бы отметить, что это правило эквивалентно требованию, чтобы линии, проведенные от точки данных до конечных точек улиц, образовывали с улицей острые углы. Второе требование легче проверить. Все, что нам нужно сделать, это вычислить скалярное произведение векторов, представляющих стороны треугольника. Если угол между двумя векторами тупой, скалярное произведение отрицательно, и наоборот.
Вот код, который проверяет, является ли треугольник острым.
Думаю, вы уже знаете, с какой следующей проблемой мы столкнемся. В реальной жизни не все улицы прямые. Рассмотрим ситуацию на картинке ниже
Алгоритм, который мы только что разработали, возвращает первую строку как ближайшую, а ответ, очевидно, будет второй. Это связано с тем, что текущий подход рассматривает только конечные точки и не учитывает кривизну. К счастью, граф OSMnx также содержит геометрию улиц, которую можно представить в виде последовательности координат конечных точек подсегментов улиц.
Теперь все, что нам нужно сделать, чтобы решить эту проблему, — это перебрать все подсегменты для каждой рассматриваемой улицы.
Это, однако, создает еще одну, довольно неожиданную проблему. Что произойдет, если продолжение одного из отрезков какой-нибудь дальней улицы окажется прямо рядом с точкой данных?
Точка будет связана с улицей №2, тогда как она явно принадлежит первой. Проблема, однако, может быть решена путем проверки остроты треугольника для каждого подотрезка, точно так же, как мы уже делали это для концов улиц.
Это охватывает все случаи, которые могут вызвать проблему, поэтому мы можем перейти к следующей части, оптимизации эффективности.
2. Оптимизация эффективности
На этом общий алгоритм закончен. Единственное, что мы можем добавить в логику функции, чтобы ускорить ее, — это проверять, не слишком ли далеко улица, и отбрасывать улицу, если это так. После добавления строки, которая проверяет, не находятся ли все конечные точки дальше определенного расстояния, функция выглядит так:
К сожалению, после всех корректировок на вычисление ближайшей улицы для каждого пункта из 7 миллионов уйдет примерно неделя. Нам нужно идти глубже.
Я собираюсь использовать библиотеку Numba, чтобы еще больше ускорить работу функции. Что он делает, так это переводит определенные функции Python в оптимизированный машинный код во время выполнения, используя библиотеку компилятора LLVM. Единственным недостатком является то, что он не поддерживает динамическую типизацию вместе с некоторыми специфичными для Python типами данных, такими как фреймы данных Pandas. Я намеренно не использовал неподдерживаемые типы данных, так что это не будет проблемой. Итак, все, что нам нужно сделать, это указать типы данных переменных, которые используются в ускоренных функциях.
Чтобы функция вызывалась с помощью Numba, декоратор @jit должен быть помещен перед ней. И это все.
Теперь, чтобы проверить прирост эффективности, давайте загрузим график улиц для центра Лондона и создадим тысячу точек. Пробовал найти ближайшую улицу для всех точек с ускорением Numba и без него. Вот результаты:
- без Numba — 4 минуты 27 секунд
- с Numba — 0 минут 3,4 секунды
Код работает в 80 раз быстрее, это впечатляет. Первоначальная задача по связыванию 7 миллионов точек с улицами была решена всего за несколько часов вместо недели.
Я сделал блокнот со всем кодом и большим количеством фотографий. Вы можете найти его в этом репозитории.
Спасибо за прочтение статьи, надеюсь, она была вам полезна!
