用于保存和查询坐标的Performant python数据结构

Question

对于类似地图的类，我当前在字典中保存了一些对象，例如：

{(3,5):<something>, (1,12):<whatever>, (17,2):<example>}

键用元组表示x/y坐标。不是每一个坐标都被占据了，还有“洞”。在

有些方法需要从字典中读出一个区域，例如“从（2,5）到（6,10）的所有对象”。我目前的方法是迭代所有键并返回请求区域中的所有键。由于这些类似地图的字典可以变得相当大，我正在寻找一种更直接的方式来获取这些区域。我考虑了一个OrdneredDict，这样如果迭代超过了请求的区域，我就可以停止迭代，但是也许还有更好的方法呢？在

Answer 1

所描述的问题是一个可以使用K-D tree有效解决的典型问题。在

k-d树（k-dimensional tree的缩写）是一种用于在k维空间中组织点的空间划分数据结构。在你的例子中k等于2。它基本上是一个二叉搜索树，在其中，您可以在每个级别上进行的比较之间进行交替。例如，如果在某个级别上，根据点的x坐标比较点，则在下一个级别上，将使用y坐标比较点。在

因此在树中插入一个点可以在O(logN)中完成。这个图像可以演示插入。因此，在数据结构中插入N个点将花费O(NlogN)时间。在

_{从http://coursera.cs.princeton.edu/algs4/assignments/kdtree.html拍摄的图像}

若要查找给定查询矩形中包含的所有点，请从根开始，并使用以下修剪规则递归搜索两个子树中的点：如果查询矩形与节点对应的矩形不相交，则无需探索该节点（或其子树）。只有当子树可能包含查询矩形中包含的点时，才会搜索子树。在

因此，下面的running Java code以最佳的方式解决了这个问题。对于矩形中包含的点的每个查询通常可以在O(R+logN)时间内得到回答。其中R是范围内的点数，N是点数。然而，对于病理数据，最坏的运行时间是O(R + sqrt(N))。在

    void run(){
        Scanner in = new Scanner(System.in);
        int numQueries = in.nextInt();
        Point2D root = null;
        for(int i=0; i<numQueries; i++){
            int type = in.nextInt();
            if(type == 0){   // Add a point
                double x = in.nextDouble();
                double y = in.nextDouble();
                root = addPoint(root, x, y, true);
            }else{
                double x1  = in.nextDouble();
                double y1 = in.nextDouble();
                double x2  = in.nextDouble();
                double y2 = in.nextDouble();
                System.out.println("the points in between the rectange with end points " + 
                     new Point2D(x1, y1) + " and " + new Point2D(x2, y2) + " are :");
                printPointsInRange(root, x1, y1, x2, y2, true);
            }
        }
    }


    // prints all points in the rectangle which has top left coordinates
    // (x1, y1) and bottom right coordinates (x2, y2)
    void printPointsInRange(Point2D root,
                        double x1, double y1, 
                        double x2, double y2, boolean vertical){
        if(root==null){
            return;
        }
        double x = root.x;
        double y = root.y;
        boolean outsideRange = Double.compare(x, x1)<0 || 
                                Double.compare(x, x2)>0 ||
                                 Double.compare(y, y1)>0 || 
                                 Double.compare(y, y2)<0;
        if(!outsideRange){
            System.out.println(root);
        }

        if(vertical){
            if(Double.compare(x, x1)<=0){ 
                // root lies left of left boundary or on the boundary
                printPointsInRange(root.right, x1, y1, x2, y2, !vertical);
            }else if(Double.compare(x, x2)>0){
                // root lies right of right boundary
                printPointsInRange(root.left, x1, y1, x2, y2, !vertical);
            }else if(Double.compare(x, x2)==0){
                // root lies on right boundary
                printPointsInRange(root.right, x1, y1, x2, y2, !vertical);
            }else{
                // root lies in between x1 and x2
                printPointsInRange(root.left, x1, y1, x2, y2, !vertical);
                printPointsInRange(root.right, x1, y1, x2, y2, !vertical);
            }
        }else{
            if(Double.compare(y, y2)<=0){ 
                // root lies below bottom boundary or on bottom boundary
                printPointsInRange(root.right, x1, y1, x2, y2, !vertical);
            }else if(Double.compare(y, y1)>0){
                // root lies above top boundary
                printPointsInRange(root.left, x1, y1, x2, y2, !vertical);
            }else if(Double.compare(y, y1)==0){
                // root lies on top boundary
                printPointsInRange(root.right, x1, y1, x2, y2, !vertical);
            }else{
                // root lies in between y1 and y2
                printPointsInRange(root.left, x1, y1, x2, y2, !vertical);
                printPointsInRange(root.right, x1, y1, x2, y2, !vertical);
            }
        }
    }

    Point2D addPoint(Point2D root, double x, double y, boolean vertical){
        if(root==null){
            return new Point2D(x, y);
        }
        if(vertical){   // vertical division
            double compare = Double.compare(root.x, x);
            if(compare<0){ // point is on left of root
                root.left = addPoint(root.left, x, y, !vertical);
            }else{        // point is on right of root or on root's x
                root.right = addPoint(root.right, x, y, !vertical);
            }
        }else{
            double compare = Double.compare(y, root.y);
            if(compare>0){    // point is above the root
                root.right = addPoint(root.right, x, y, !vertical);
            }else{            // point is below the root or on root's y 
                root.left = addPoint(root.left, x, y, !vertical);
            } 
        }
        return root;
    }

Answer 2

您可以生成所有潜在坐标并检查它们是否存在于dict中，而不是遍历整个dict中。这将是O(1)时间与当前{}时间的解决方案。在

类似这样的方法是可行的（其中grid是您的dict）

def subset_coordinates(grid, top_left, bottom_right):
    a, b = top_left
    c, d = bottom_right
    for i in range(a, c+1):
        for j in range(b, d+1):
            value = grid.get((i, j))
            if value is not None:
                yield value

objects_in_subset = subset_coordinates(grid, (2, 5), (6, 10))