Eu tenho uma entrada de 36.742 pontos, o que significa que, se eu quisesse calcular o triângulo inferior de uma matriz de distância (usando a aproximação vincenty), precisaria gerar 36.742 * 36.741 * 0,5 = 1.349.974.563 distâncias.

Quero manter as combinações de pares que estão a 50 km uma da outra. Minha configuração atual é a seguinte

shops= [[id,lat,lon]...]

def lower_triangle_mat(points):
    for i in range(len(shops)-1):
        for j in range(i+1,len(shops)):
            yield [shops[i],shops[j]]

def return_stores_cutoff(points,cutoff_km=0):
    below_cut = []
    counter = 0
    for x in lower_triangle_mat(points):
        dist_km = vincenty(x[0][1:3],x[1][1:3]).km
        counter += 1
        if counter % 1000000 == 0:
            print("%d out of %d" % (counter,(len(shops)*len(shops)-1*0.5)))
        if dist_km <= cutoff_km:
            below_cut.append([x[0][0],x[1][0],dist_km])
    return below_cut

start = time.clock()
stores = return_stores_cutoff(points=shops,cutoff_km=50)
print(time.clock() - start)

Obviamente, isso levará horas e horas. Algumas possibilidades em que eu estava pensando:

Use numpy paravectorise esses cálculos ao invés de percorrerUse algum tipo dehash para obter um rápido desbaste (todas as lojas em um raio de 100 km) e depois calcular distâncias precisas entre essasEm vez de armazenar os pontos em uma lista, use algo como um quad-tree, mas acho que só ajuda no ranking de pontos próximos em vez da distância real -> então acho que algum tipo degeodatabaseEu posso obviamente tentar oHaversine ou projeto e usoeuclidiano distâncias, no entanto, estou interessado em usar a medida mais precisa possívelFazer uso deparalelo processamento (no entanto, eu estava tendo um pouco de dificuldade em descobrir como cortar a lista para ainda obter todos os pares relevantes).

Editar: Acho que o geohashing é definitivamente necessário aqui - um exemplode:

from geoindex import GeoGridIndex, GeoPoint

geo_index = GeoGridIndex()
for _ in range(10000):
    lat = random.random()*180 - 90
    lng = random.random()*360 - 180
    index.add_point(GeoPoint(lat, lng))

center_point = GeoPoint(37.7772448, -122.3955118)
for distance, point in index.get_nearest_points(center_point, 10, 'km'):
    print("We found {0} in {1} km".format(point, distance))

No entanto, também gostaria de vetorizar (em vez de fazer um loop) os cálculos de distância para as lojas retornadas pelo geo-hash.

Edit2: Pouria Hadjibagheri - Tentei usar lambda e map:

# [B]: Mapping approach           
lwr_tr_mat = ((shops[i],shops[j]) for i in range(len(shops)-1) for j in range(i+1,len(shops)))

func = lambda x: (x[0][0],x[1][0],vincenty(x[0],x[1]).km)
# Trying to see if conditional statements slow this down
func_cond = lambda x: (x[0][0],x[1][0],vincenty(x[0],x[1]).km) if vincenty(x[0],x[1]).km <= 50 else None

start = time.clock()
out_dist = list(map(func,lwr_tr_mat))
print(time.clock() - start)

start = time.clock()
out_dist = list(map(func_cond,lwr_tr_mat))
print(time.clock() - start)

E eles estavam por toda parte61 segundos (Eu restrinjai o número de lojas para 2000 de 32.000). Talvez eu tenha usado o mapa incorretamente?