都市名とGPS座標を含むテキストファイル（UTF-8、約50K行）があります。行の例：
San Pedro locality -3367 -5968 Argentina Buenos Aires San Pedro
Talagante locality -3366 -7093 Chile Metropolitana Talagante
Peñaflor locality -3362 -7092 Chile Metropolitana Talagante
3列目と4列目は、最後の列の都市のGPS座標です。
GPS座標を考えると、クローゼットの都市を見つける必要があります。私はこれを何億回も行う必要があります。このタスクで私を助けることができるいくつかのツールは何ですか？Java/Pythonソリューションが理想的です。
あなたが探しているのはKDツリーです。ここでPython実装へのリンクを見つけましたが、私はPython開発者ではなく、試したことはありません。KDツリーは、平面内で最も近い点を見つける平方根の複雑さをサポートします。これは、おそらく取得できる最高の複雑さです。おそらく1秒間に約100万回のクエリを実行する余裕があります。
編集：実際、あなたの質問は私にもう少し徹底的な調査をさせました。おそらく、このページで可能なアプローチとして説明されているものが役立つでしょう。あなたが興味を持っているのは、最も近い隣人の多くのクエリに最適なソリューションを提供することです。
これらのレコードをSQLiteデータベースに保存します。SQLiteの上に空間クエリとタイプを追加するSpatiaLiteと呼ばれるプロジェクトがあります。これにより、データベースに「xから20メートル以内のすべてのアイテムを与える」などの質問をすることができます。
データベースを使用したくない場合は、四分木を使用できます。Pythonにはいくつかの実装があります。四分木は長方形の空間を4つの部分に分割し、次に各部分をさらに4つの部分に分割します。検索は非常に効率的です。
あなたが求めているような幾何学的なクエリ（最も近い点）の場合、KDツリーは優れたデータ構造です。それに加えて、実装するのはそれほど難しくありません。私はJavaの実装を持っています。それがあなたにとってどれほど効率的かわからない。それは私の任務でした。Point2Dおよびその他のユーティリティクラスはここに実装されています。あなたはそこで彼らのソースコードを見ることができます。RectHV必要な別のユーティリティクラスです。私が書いたものです。
public class RectHV {
private final double xmin, ymin; // minimum x- and y-coordinates
private final double xmax, ymax; // maximum x- and y-coordinates
// construct the axis-aligned rectangle [xmin, xmax] x [ymin, ymax]
public RectHV(double xmin, double ymin, double xmax, double ymax) {
if (xmax < xmin || ymax < ymin) {
throw new IllegalArgumentException("Invalid rectangle");
}
this.xmin = xmin;
this.ymin = ymin;
this.xmax = xmax;
this.ymax = ymax;
}
// accessor methods for 4 coordinates
public double xmin() { return xmin; }
public double ymin() { return ymin; }
public double xmax() { return xmax; }
public double ymax() { return ymax; }
// width and height of rectangle
public double width() { return xmax - xmin; }
public double height() { return ymax - ymin; }
// does this axis-aligned rectangle intersect that one?
public boolean intersects(RectHV that) {
return this.xmax >= that.xmin && this.ymax >= that.ymin
&& that.xmax >= this.xmin && that.ymax >= this.ymin;
}
// draw this axis-aligned rectangle
public void draw() {
StdDraw.line(xmin, ymin, xmax, ymin);
StdDraw.line(xmax, ymin, xmax, ymax);
StdDraw.line(xmax, ymax, xmin, ymax);
StdDraw.line(xmin, ymax, xmin, ymin);
}
// distance from p to closest point on this axis-aligned rectangle
public double distanceTo(Point2D p) {
return Math.sqrt(this.distanceSquaredTo(p));
}
// distance squared from p to closest point on this axis-aligned rectangle
public double distanceSquaredTo(Point2D p) {
double dx = 0.0, dy = 0.0;
if (p.x() < xmin) dx = p.x() - xmin;
else if (p.x() > xmax) dx = p.x() - xmax;
if (p.y() < ymin) dy = p.y() - ymin;
else if (p.y() > ymax) dy = p.y() - ymax;
return dx*dx + dy*dy;
}
// does this axis-aligned rectangle contain p?
public boolean contains(Point2D p) {
return (p.x() >= xmin) && (p.x() <= xmax)
&& (p.y() >= ymin) && (p.y() <= ymax);
}
// are the two axis-aligned rectangles equal?
public boolean equals(Object y) {
if (y == this) return true;
if (y == null) return false;
if (y.getClass() != this.getClass()) return false;
RectHV that = (RectHV) y;
if (this.xmin != that.xmin) return false;
if (this.ymin != that.ymin) return false;
if (this.xmax != that.xmax) return false;
if (this.ymax != that.ymax) return false;
return true;
}
// return a string representation of this axis-aligned rectangle
public String toString() {
return "[" + xmin + ", " + xmax + "] x [" + ymin + ", " + ymax + "]";
}
}
これがKDツリーです。
public class KdTree {
private static class Node {
private Point2D p; // the point
private RectHV rect; // the axis-aligned rectangle corresponding to this node
private Node lb; // the left/bottom subtree
private Node rt; // the right/top subtree
Node() {
p = null;
rect = null;
lb = null;
rt = null;
}
}
private Node tree;
private Point2D nearestPoint, infinitePoint;
private int sz;
private double nearestDist;
// construct an empty set of points
public KdTree() {
tree = new Node();
sz = 0;
infinitePoint = new Point2D(Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY);
}
// is the set empty?
public boolean isEmpty() {
return (sz == 0);
}
// number of points in the set
public int size() {
return sz;
}
////////////////////////////////////////////////
// private function for inserting any element //
////////////////////////////////////////////////
private void privateInsert( Node nd, Point2D p, int lv, double xmin, double ymin, double xmax, double ymax) {
if(nd.p == null) {
nd.p = p;
nd.rect = new RectHV(xmin, ymin, xmax, ymax);
nd.lb = new Node();
nd.rt = new Node();
sz = sz + 1;
}
else if( lv % 2 == 0 ) {
double X = nd.p.x();
double x = p.x();
if( x <= X ) {
xmax = X;
privateInsert(nd.lb, p, lv+1, xmin, ymin, xmax, ymax);
}
else {
xmin = X;
privateInsert(nd.rt, p, lv+1, xmin, ymin, xmax, ymax);
}
}
else {
double Y = nd.p.y();
double y = p.y();
if( y <= Y ) {
ymax = Y;
privateInsert(nd.lb, p, lv+1, xmin, ymin, xmax, ymax);
}
else {
ymin = Y;
privateInsert(nd.rt, p, lv+1, xmin, ymin, xmax, ymax);
}
}
}
////////////////////////////////////////////////
// private function for searching any element //
////////////////////////////////////////////////
private Node privateSearch( Node nd, Point2D p, int lv ) {
if( nd.p == null ) return nd;
else if( p.equals( nd.p ) == true ) return nd;
if(lv % 2 == 0) {
double X = nd.p.x();
double x = p.x();
if( x <= X ) {
return privateSearch( nd.lb, p, lv+1 );
}
else {
return privateSearch( nd.rt, p, lv+1);
}
}
else {
double Y = nd.p.y();
double y = p.y();
if( y <= Y ) {
return privateSearch(nd.lb, p, lv+1);
}
else {
return privateSearch(nd.rt, p, lv+1);
}
}
}
/////////////////////////////////////////////////
// private function for drawing all the points //
/////////////////////////////////////////////////
private void privateDraw (Node nd) {
if(nd.p == null) return;
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.setPenRadius(.01);
double x = nd.p.x();
double y = nd.p.y();
StdDraw.point( x, y );
privateDraw( nd.lb );
privateDraw( nd.rt );
}
//////////////////////////////////////////
// private function for range searching //
//////////////////////////////////////////
private void privateRange(Node nd, RectHV rect, Queue<Point2D> que){
if(nd.p == null) return;
if( rect.contains( nd.p ) == true ) que.enqueue( nd.p );
if( nd.rect.intersects(rect) == true ) {
privateRange(nd.lb, rect, que);
privateRange(nd.rt, rect, que);
return;
}
else return;
}
//////////////////////////////////////////////////////
// private function for searching nearest neighbour //
//////////////////////////////////////////////////////
private void privateNearest( Node nd, Point2D p ) {
if(nd.p == null) return;
double d = p.distanceSquaredTo(nd.p);
if(d < nearestDist) {
nearestDist = d;
nearestPoint = nd.p;
}
if(nd.lb.p != null && ( nd.lb.rect.distanceSquaredTo(p) < nearestDist) ) privateNearest(nd.lb, p);
if(nd.rt.p != null && ( nd.rt.rect.distanceSquaredTo(p) < nearestDist) ) privateNearest(nd.rt, p);
}
// add the point p to the set (if it is not already in the set)
public void insert(Point2D p) {
if( contains( p ) == true ) {
return;
}
else {
privateInsert(tree, p, 0, 0.00, 0.00, 1.00, 1.00);
}
}
// does the set contain the point p?
public boolean contains(Point2D p) {
Node nd = privateSearch(tree, p, 0);
if(nd.p == null) return false;
else return true;
}
// draw all of the points to standard draw
public void draw() {
privateDraw(tree);
}
// all points in the set that are inside the rectangle
public Iterable<Point2D> range( RectHV rect ) {
Queue<Point2D> que = new Queue<Point2D>();
privateRange(tree, rect, que);
return que;
}
// a nearest neighbor in the set to p; null if set is empty
public Point2D nearest(Point2D p) {
nearestPoint = infinitePoint;
nearestDist = Double.POSITIVE_INFINITY;
privateNearest(tree, p);
return nearestPoint;
//return p;
}
}
GeoHashは、もう1つの選択肢であり、それぞれを実装するのに非常に効率的で、高速です。