У меня есть список, и я хочу рассчитать среднее расстояние каждого элемента в списке до всех других элементов в списке - PullRequest
Новая
       7

У меня есть список, и я хочу рассчитать среднее расстояние каждого элемента в списке до всех других элементов в списке

0 голосов
/ 23 апреля 2020

Список содержит координаты x, y и выглядит следующим образом: [[1,2], [2,3], [5,6]....] Я знаю, как рассчитать расстояние между двумя координатами. Мне нужно вычислить расстояние между [1,2] со всеми остальными координатами в списке, а затем перейти к [2,3] и сделать то же самое и т. Д.

Что было бы лучше способ решить эту проблему?

Мой первоначальный подход заключался в создании двух циклов for: 

for i in range (0, len(coordinateslist)):
    for j in range (0, len(coordinateslist)):
        distanceList.append(computeDist(coordinateslist[i),coordinateslist[j])

Ответы [ 2 ]

1 голос
/ 24 апреля 2020

Вам необходимо определить, какие пары координат вы хотите сравнить. См. Таблицу ниже для определения возможных сравнений. 

*   A  B  C  ...

A   AA AB AC
B   BA BB BC
C   CA CB CC
...          ...

При условии, что допустимыми сравнениями являются (AB, A C, B C) или (BA, CA, CB), но не оба.

Вам нужно немного изменить свой l oop. 

from itertools import islice

for i, point in enumerate(coordinateslist):
    for other in islice(coordinateslist, i):
        distanceList.append(computeDist(point, other))
0 голосов
/ 23 апреля 2020

Таким образом, решение грубой силы может выглядеть следующим образом: ex [x, y, z, l, m ...] вычислять каждое парное расстояние ровно один раз x: (точки -x) y: (точки -x -y ) z: (points -x -y -z) et c ... 

def calculate_distances(points)
    tocalc = points
    answers = dict()
    for point in points:
        for dot in tocalc:
            if point!=dot: # distance to itself is always 0
                answers[sorted([point,dot])] = distance(point,dot)
        tocalc.pop(0) #no need to process this item again
     return answers

Затем вы можете делать такие вещи, как sum(answers.values()), 'sorted (ответы, ключ = лямбда k: k. value) `, et c.

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

def calculate_distances(points):
    currind=0
    tocalc_ind = 1
    # we also know the answer looks like a matrix with diagonal of zeros...
    answers = dict()
    for p_ind in range(len(points)):
        currind = p_ind
        if points[currind] not in answers:
            answers[points[currind]] = dict()
        for c_ind in range(tocalc_ind,len(points)): # implicitly skipping previous
            answers[points[currind]][points[c_ind]] = distance(points[currind],points[c_ind])
    return answers

Обратите внимание, что я изменил формат данных, чтобы помочь визуализировать ответ. Я уверен, что есть другие оптимизации, но они должны выполняться за O (n) время, потому что второй вложенный l oop обычного O (n * n) уменьшается каждый ход.

...