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

Question

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

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

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

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

Answer 1

您可以生成所有潜在坐标并检查它们是否存在于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))