Более быстрый способ вычисления расстояния между каждой точкой и оставшимися n-1 точками

Question

У меня есть n точек со мной, и я должен вычислить евклидово расстояние между каждой точкой и оставшимися n -1 точками. Я использовал следующий способ сделать это в Python:

for eachRow in range(0, numberOfPoints):
        distanceProximityMatrix.append([])

    print('Initialisation Completed')
    for i in range(0, numberOfPoints):
        if(i%100 == 0) : print('.', end = '')
        for j in range(i, numberOfPoints):
            if(i != j):
                tempDist = distanceForMultivariate(recordsList[i], recordsList[j], attributesToBeUsed, isFirstColumnID = isFirstColumnID)
                distanceProximityMatrix[i].append(tempDist) 
                distanceProximityMatrix[j].append(tempDist)
            else :
                distanceProximityMatrix[i].append(0)

Есть ли более быстрый способ сделать это, так как количество набираемых мной очков достаточно велико, и эта стратегия занимает много времени.

Примечание. Функция distanceForMultivariate вычисляет евклидово расстояние.

Answer 1

Если вы просто хотите найти ближайшие k баллы, что вы думаете об этом?
Начните с помещения первых k точек в некоторый отсортированный массив (в зависимости от расстояния до исходной точки), и рассчитайте максимальное расстояние, назовите это d_max.
Для каждой новой точки p выполните следующую проверку:

if (x_p - x_start > d_max) or (y_p - y_start > d_max)
then disregard(x)
else:
  d = distance (x, start);
  if d < d_max 
  then:
    insert_into_array(x) // obviously the array must stay sorted
    d_max = distance(array[k],start)

Идея заключается в следующем: если разница между X-координатами или Y-координатами больше, чем максимальное расстояние, то расстояние также будет больше.

1012 * Е.Г. * Представьте, что ваша начальная точка (2,2), и вы уже добавили (2,6), (2,3) и (3,2), тогда d_max будет равно 4. Другие ваши очки: (10,0), (0,20) и (5,6), тогда произойдет следующее:

Add (10,0)? No, because 10 - 2 > 4 (x_p - x_start > d_max)
Add (0,20)? No, because 20 - 2 > 4 (y_p - y_start > d_max)
Add (5,6) ? Maybe: 5 - 2 <= d_max (X-coordinates) => ok
                   6 - 2 <= d_max (Y-coordinates) => ok
                   distance((5,6),(2,2)) = 5, which is larger than 4 => don't add (5,6)

Очевидно, вам нужно создать какой-то «массив»:

• , где вы можете добавить точку где-то посередине, чтобы другие сместились соответственно (связанный список).
• Если вы добавили точку и у вас уже есть записи k, последняя запись должна быть удалена.

Поскольку вам нужно только сравнить расстояния, нет необходимости вычислять квадратный корень.

Answer 2

Я предполагаю, что 2D точки здесь. Тогда евклидово расстояние:

sqrt( (x1 - x2)^2 + (y1 - y2)^2 )

Здесь у нас есть следующие операции:

• 2 вычитания
• 2 умножения
• 1 дополнение
• 1 кв.м

Если вам нужно только сравнить расстояния (например, чтобы найти ближайших соседей), вы можете полностью удалить sqrt, поскольку он сохраняет порядок. Будьте осторожны, чтобы они не стали большими, хотя, если вы захотите суммировать значения позже, они могут стать довольно большими.

Уравнение треугольника НЕ ​​выполняется, поэтому не используйте его там, где это необходимо (поэтому не нужно искать пути или вообще где-нибудь, где вы бы суммировали расстояния!):

if sqrt(a) + sqrt(b) >= sqrt(c), then
a + b <= a + 2sqrt(a*b) + b = (sqrt(a) + sqrt(b)) ^2 >= sqrt(c)^2 = c

sqrt(100) + sqrt(1) >= sqrt(121) но 100 + 1 < 121

При этом, я не думаю, что вы можете уменьшить сложность, если вам действительно нужны все расстояния, потому что тогда вы, несмотря ни на что, вычисляете значения O (n ^ 2).

[Обновление, поскольку приложение теперь очищено]

Хотя я думаю, что мое решение работает для поиска ближайших соседей, на самом деле есть более эффективные алгоритмы, которые решают проблему, чем вычислять некоторое расстояние для всех пар точек. Например, kd-деревья.

Ответы на этот вопрос могут помочь: Как эффективно найти k-ближайших соседей в многомерных данных?