Вычисление большого количества латов / Lngs для набора 2000 латов / Lngs в Ruby

Question

Я пытаюсь найти лучший способ решения проблемы ниже:

Проблема

У меня есть (до) 100 000 точек широты / долготы в наборе А У меня есть (до) 2000 лат / лн очков в наборе B

Мне нужно найти ближайшего соседа точек в наборе B к точкам в наборе A.

Как только они были соединены - мне нужно вычислить их расстояние, которое будет: 2000 Set A points to 2000 Set B Points.

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

Текущее решение

Используя реализацию KDTree в Ruby, я могу создать поиск KDTree, который будет соответствовать моим точкам. Затем я использую метод haversine в Ruby, чтобы вычислить расстояние между точками, когда они связаны.

Код KDTree: Код KDTree Ruby Код Хаверсин Код Хаверсайн

Платформа

У меня работает jruby - с рельсами в качестве веб-фреймворка.

Выпуск

Это медленно! От 30 до 40 секунд медленно ... Я думаю, что основная горловина бутылки находится в KDtree, но поиск точки тоже занимает много времени (я думаю). При меньших числах в наборе B он быстрее, но при большем количестве очков в наборе B он становится намного быстрее.

Вопрос

Кто-нибудь подумает сделать это по-другому? Есть что-то, чего мне не хватает. Я думаю, что библиотека Java могла бы быть намного быстрее, но как бы я это реализовал, и какую бы я использовал (не сильно в Java - я использую Jruby для многопоточности кода ruby ​​в JVM)

Answer 1

Просто идея в моей голове.Если вы округлите свои широты / долготы до двух десятичных знаков, то все точки с точностью до 1,11 км будут одинаковыми.См. this для более подробной информации.Я не уверен на 100% в этом, но может быть, это работает для вас.Вне курса для областей вблизи избирательных участков это не будет работать, так как там уменьшается долгота.

Чтобы ускорить вычисление расстояния между двумя широтами / долготами, вы можете рассчитать евклидово расстояние, используя простую формулу расстояния, а не географическое расстояние,Это расстояние не будет точным вне курса, но ускорит ваш процесс.

Answer 2

Можно ли сохранить информацию в базе данных?Потому что тогда вы можете использовать GeoKit , который использует базу гео-данных (MySQL, Postgres> 8.1 и т. Д.), Так что вы можете сделать это:

Location.find(:all, :origin =>[37.792,-122.393], :within=>10, :order=>"distance asc")

Также вы можете найтирасстояние между двумя точками и т. д. Время отклика будет больше по сравнению с запросом БД и намного быстрее, чем вы видите.