Блог

Я пытаюсь найти ближайшую точку в базе данных geoida для каждой точки, хранящейся во второй базе данных. Вот майский подход, который является чрезвычайно медленным. geoida.db хранит 55000 координат

 import sqlite3
from kdtree import KDTree

database = sqlite3.connect('geoida.db')
cursor = database.cursor()
cursor.execute("select lat, lon  from coords")
geoid = cursor.fetchall()

database = sqlite3.connect('F.tsj')
cursor = database.cursor()
cursor.execute("select C1, C2 from tblSoPoints") 
results = cursor.fetchall()
for line in results:
    tree = KDTree.construct_from_data(geoid)
    nearest = tree.query(query_point=line, t=2)
    print nearest[0]
  

обе базы данных содержат широты и долготы

Почему вы создаете KDTree снова и снова? Мне кажется, что вы должны создать его один раз и запросить его для каждой точки. Построение дерева — это O (N log N) (или O (N (log N) ^ 2) в зависимости от алгоритма), поэтому выполнение этого N раз делает ваш алгоритм O (N ^ 2 log N). Построение дерева один раз и его запрос сохранят сложность на уровне O (N log N).

Просто создайте дерево вне цикла:

 tree = KDTree.construct_from_data(geoid)
for line in results:
  nearest = tree.query(query_point=line, t=2)