Миллионы трехмерных точек: как найти 10 из них, ближайших к заданной точке?

Question

Точка в 3-й точке определяется как (x, y, z). Расстояние d между любыми двумя точками (X, Y, Z) и (x, y, z) равно d = Sqrt [(X-x) ^ 2 + (Y-y) ^ 2 + (Z-z) ^ 2]. Теперь в файле есть миллион записей, каждая запись - это некая точка в пространстве, в произвольном порядке. Для любой точки (a, b, c) найдите ближайшие 10 точек. Как вы будете хранить миллион точек и как вы получите эти 10 точек из этой структуры данных.

Answer 1

Этот вопрос нуждается в дальнейшем определении.

1) Решение относительно алгоритмов предварительного индексирования данных очень сильно зависит от того, можете ли вы хранить целые данные в памяти или нет.

При использовании kdtrees и octrees вам не нужно будет хранить данные в памяти, и выигрыш в производительности от этого факта не только потому, что объем памяти меньше, но и потому, что вам не нужно читать весь файл.

С помощью bruteforce вам придется читать весь файл и пересчитывать расстояния для каждой новой точки, которую вы будете искать.

Тем не менее, это может быть не важно для вас.

2) Другой фактор - сколько раз вам придется искать точку.

Как утверждал Дж. Ф. Себастьян, иногда bruteforce работает быстрее даже на больших наборах данных, но имейте в виду, что его тесты измеряют чтение всего набора данных с диска (что необязательно после построения дерева kd или октре и где-то написано) и что они измеряют только один поиск.

Answer 2

Рассчитайте расстояние для каждого из них и выберите Select (1..10, n) за O (n) время. Это был бы наивный алгоритм, я думаю.