python - 字典Python的智能循环

Question

我的字典看起来像

position_dictionnary = {(0,0): <PositionObject1>, (0,1): <PositionObject2>, ...  (x,y): <PositionObjectn>}

我有一个函数需要返回给定位置周围特定范围内的 PositionObject 列表。现在我有这段代码对我来说工作得很好:

def getSurrounding(center_position, range, position_dictionnary):
    for x,y in position_dictionnary:
         if abs(center_position.x - x) + abs(center_position.y - y) < range:
             yield position_dictionnary[(x,y)]

但是当字典变得很大时，它就会变得太长，所以我问是否有一种方法可以直接循环字典的正确索引，或者我认为没有其他方法可以让它运行得更快。 (如果解决方案不是很好的实践证明，但速度更快，那就可以了)

Answer 1

您可以通过对 x 和 y 坐标进行双重排序来在亚线性时间内完成此操作。当然，这是假设点字典是相当静态的，因为添加或移动事物显然会产生(小)成本。

下面涉及使用多个排序容器，因此对 getSurrounding 的每个查询将调用 4 个二分搜索，这仍然是 O(log(N))。额外的好处是，这应该适用于位置的 float 值，但我还没有真正考虑过。

from sortedcollections import SortedDict, SortedList

pos_dict = {(0,0): 'a',
            (1,2): 'b',
            (1,3): 'c',
            (2,2): 'd',
            (2,6): 'e',
            (3,2): 'f',
            (4,4): 'g',
            (5,5): 'h'}

sd = SortedDict()

# put everything into a sorted dictionary
for x, y in pos_dict:
    temp = sd.get(x, SortedList())
    temp.add(y)
    sd[x] = temp

# we look for candidate x values in the sorted dictionary 
# and be clever with the Manhattan
# distance to find the y values

rng = 2
ctr = (2,2)
points_in_range = []

left_x = ctr[0] - rng
right_x = ctr[0] + rng

low_y = ctr[1] - rng
hi_y = ctr[1] + rng

x_vals = sd.keys()[sd.bisect(left_x) : sd.bisect(right_x)]

# get y values within the remaining Manhattan distance and construct tuples from (x, y)
for x in x_vals:
    temp = sd.get(x)
    low_y_lim = low_y + abs(x-ctr[0])
    hi_y_lim = hi_y - abs(x-ctr[0])
    y_vals = temp[temp.bisect(low_y_lim) : temp.bisect(hi_y_lim)]
    points_in_range.extend([(x, y) for y in y_vals])

print(points_in_range)

for p in points_in_range:
    print(f'{pos_dict.get(p)} is in range at location {p}')

产量:

[(1, 2), (1, 3), (2, 2), (3, 2)]
b is in range at location (1, 2)
c is in range at location (1, 3)
d is in range at location (2, 2)
f is in range at location (3, 2)

其他概念...

根据字典的大小和范围的值，您可能能够接近线性时间。如果 rng 的值很小，那么构造一组“在范围内”的点并将其与字典中的一组键相交非常容易，并且如果 rng 是“小”，则接近线性。

set_of_in_rng = {(x,y)      for x in range(ctr[0]-rng, ctr[0]+rng+1) 
                            for y in range(low_y+abs(x-2), hi_y-abs(x-2)+1)}

points_in_range = set_of_in_rng.intersection(set(pos_dict.keys()))

for p in points_in_range:
    print(f'{pos_dict.get(p)} is in range at location {p}')

产生相同的结果:

b is in range at location (1, 2)
f is in range at location (3, 2)
c is in range at location (1, 3)
d is in range at location (2, 2)