У меня есть ввод 36 742 точки, что означает, что если бы я хотел вычислить нижний треугольник матрицы расстояний (используя приближение Винсенти), мне нужно было бы сгенерировать 36 742 * 36 741 * 0,5 = 1 349 974 563 расстояния.
Я хочу сохранить комбинации пар, которые находятся в пределах 50 км друг от друга. Моя текущая установка выглядит следующим образом
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)
Это, очевидно, займет часы и часы. Некоторые возможности, о которых я думал:
- Используйте numpy для векторизации этих вычислений, а не в цикле.
- Используйте какое-нибудь хэширование, чтобы получить быстрый приблизительный результат (все магазины в пределах 100 км), а затем рассчитайте только точные расстояния между этими магазинами.
- Вместо хранения точек в списке используйте что-то вроде дерева квадрантов, но я думаю, что это помогает только для ранжирования близких точек, а не фактического расстояния -> поэтому я предполагаю, что это какая-то база геоданных
- Очевидно, я могу попробовать гаверсинус или проект и использовать евклидовы расстояния, однако я заинтересован в использовании максимально точной меры.
- Используйте параллельную обработку (однако у меня возникли некоторые трудности с тем, как сократить список, чтобы получить все соответствующие пары).
Редактировать: я думаю, что геохэширование здесь определенно необходимо — пример от:
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))
Однако я также хотел бы векторизовать (вместо цикла) расчеты расстояния для магазинов, возвращаемых геохэшем.
Edit2: Pouria Hadjibagheri. Я пытался использовать лямбда и карту:
# [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)
И все они были около 61 секунды (я ограничил количество магазинов до 2000 с 32 000). Возможно, я неправильно использовал карту?
