I have 55249 cities in my database. Every single one has got latitude longitude values. For every city I want to calculate distances to every other city and store those that are no further than 30km. Here is my algorithm:
# distance function
from math import sin, cos, sqrt, atan2, radians
def distance(obj1, obj2):
lat1 = radians(obj1.latitude)
lon1 = radians(obj1.longitude)
lat2 = radians(obj2.latitude)
lon2 = radians(obj2.longitude)
dlon = lon2 - lon1
dlat = lat2 - lat1
a = (sin(dlat/2))**2 + cos(lat1) * cos(lat2) * (sin(dlon/2))**2
c = 2 * atan2(sqrt(a), sqrt(1-a))
return round(6373.0 * c, 2)
def distances():
cities = City.objects.all() # I am using Django ORM
for city in cities:
closest = list()
for tested_city in cities:
distance = distance(city, tested_city)
if distance <= 30. and distance != 0.:
closest.append(tested_city)
city.closest_cities.add(*closest) # again, Django thing
city.save() # Django
This works but takes awful lot of time. Gonna take weeks to complete. Any way I could speed it up?