алгоритм поиска ближайших друзей?

Question

У меня есть программа python, сидящая на стороне сервера, управляющая информацией о местоположении пользователя, у каждого друга есть пара (долгота, широта), с учетом точки (долгота, широта), как я могу найти ближайших (скажем, в пределах 5 км) друзейэффективно?

У меня есть 10K пользователей онлайн ...

Спасибо.Bin

Answer 1

Новый ответ:

Я бы сохранял lat и long в отдельных столбцах.Поместите индексы на них.Затем, когда вы хотите найти ближайших друзей определенного пользователя, просто сделайте что-то вроде

select field1, field1, ..., fieldn from users 
where 
    user_lat > this_lat - phi and user_lat < this_lat + phi
    and
    user_lon > this_lon - omega and user_lon < this_lon + omega

, где phi и omega - это градусы широты и долготы, соответствующие вашему желаемому расстоянию.Это будет зависеть от того, где вы находитесь на земном шаре, но существуют определенные уравнения для его выяснения.Существует также вероятность того, что ваша база данных может выполнить эти вычисления за вас.

---

старый ответ.

Я бы посмотрел на quadtrees и kd-trees.

Kd-деревья были бы здесь каноническим решением, я считаю.

Answer 2

Создайте dict {graticule: [users]} («graticule» - это блок с широтой 1 градус х 1 градус долготы; поэтому вы можете просто округлить значения).Чтобы найти соседних пользователей, сначала получите пользователей из той же и смежных сеток (поскольку цель может быть около края), затем отфильтруйте их с помощью базового теста ограничивающего прямоугольника (то есть, какие минимальные долгота / широта возможны для кого-либо вжелаемый радиус), затем проведите подробный тест (если вам нужна точность, то вам нужна более сложная математика, чем просто Пифагор).

Answer 3

Простым способом будет сортировка точек по долготе, а затем при поиске друзей найдите минимальную и максимальную долготы возможных совпадений.Сортировка списка - O (n log n), и поиск друзей является линейным, но только для друзей в пределах диапазона долготы.Вот пример для случая, когда у вас есть все точки на плоской 2D-поверхности:

# friends is the sorted list of (x, y) tuples, (px, py) is my location
def get_near(friends, px, py, maxdist):
    i1 = bisect.bisect_left(friends, (px - maxdist, py))
    i2 = bisect.bisect_right(friends, (px + maxdist, py))
    return [(x, y) for (x, y) in friends[i1:i2] if math.hypot(px - x, py - y) < maxdist]

Для случая долготы / широты вам придется использовать другую функцию для проверки расстояния вместо евклидовойрасстояние (math.hypot).

Answer 4

http://www.movable -type.co.uk / scripts / latlong.html с точки зрения эффективности, единственное, что действительно приходит на ум, - это предварительное вычисление расстояния, когда записи вносятся в базу данных, у него есть другая таблица, в которой хранится пара местоположений вместе с расстоянием, для каждого местоположения, добавляемого в момент добавления, вы понесете затраты на вычисление расстояния до каждой другой точки в системе, но тогда поиск по этой таблице может быстро разрешать местоположения на определенном расстоянии.

Похоже, ответ Ааронастерлинга - это то, что я пытался продумать сам, но не знал, что существует :), так что, возможно, это лучшее решение, но я уверен, что во время поиска с этим алгоритмом у вас возникнут дополнительные затраты. (хотя, вероятно, небольшой, поскольку обход дерева, если он достаточно сбалансирован, обычно довольно быстрый процесс, мне потребуется некоторое время, чтобы понять, как именно дерево составлено, но для меня это новая концепция).