Python berechnen viele Entfernungen schnell

Ich habe eine Eingabe von 36.742 Punkten. Wenn ich also das untere Dreieck einer Distanzmatrix berechnen wollte (mit der Annäherung an fünfzig), müsste ich 36.742 * 36.741 * 0,5 = 1.349.974.563 Distanzen erzeugen.

Ich möchte die Paarkombinationen behalten, die nicht weiter als 50 km voneinander entfernt sind. Mein aktuelles Setup ist wie folgt

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)

Dies wird natürlich Stunden und Stunden dauern. Einige Möglichkeiten, über die ich nachgedacht habe:

Use numpy to vectorise diese Berechnungen, anstatt eine Schleife durchVerwende irgendeine Art von hashing, um einen schnellen Rohschnitt zu erhalten (alle Geschäfte innerhalb von 100 km) und dann nur die genauen Entfernungen zwischen diesen Geschäften zu berechnen. Anstatt die Punkte in einer Liste zu speichern, benutze ich so etwas wie einen Viererbaum, aber ich denke, das hilft nur bei der Rangfolge der nahen Punkte anstatt der tatsächlichen Entfernung -> also denke ich, dass eine Art von geodatabase Ich kann natürlich das @ versuch Haversine oder projizieren und @ verwend euclidean Entfernungen, aber ich bin daran interessiert, das genauestmögliche Maß zu verwendenGebrauch machen vonparalleprocessing (allerdings hatte ich einige Schwierigkeiten, die Liste zu kürzen, um trotzdem alle relevanten Paare zu erhalten).

Bearbeite: Ich denke, Geohashing ist hier definitiv erforderlich - ein Beispielvo:

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))

Ich möchte jedoch auch die Entfernungsberechnungen für die vom Geo-Hash zurückgegebenen Stores vektorisieren (anstatt zu schleifen).

Edit2: Pouria Hadjibagheri - Ich habe es mit Lambda und Map versucht:

# [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)

Und sie waren überall 61 Sekunden (Ich habe die Anzahl der Geschäfte von 32.000 auf 2000 beschränkt.) Vielleicht habe ich die Karte falsch benutzt?