我目前正在做一个项目,其中我必须多次检查给定的 2D 点是否“合法”,即它是否在网格的边界内以及之前是否未被访问过。网格具有固定的H x W
尺寸,所以我想我可以不将它们存储在集合中,而是存储在二维查找表中。令我惊讶的是,它比检查它是否出现在集合中要慢得多,即使它(理论上)是一个 O(logn)
操作,而不是 O(1)
使用简单的数组查找。
第一次尝试:
class PointSet:
def __init__(self, h, w):
if h <= 0 or w <= 0:
raise ValueError("Invalid size")
self.h = h
self.w = w
self.lookup = [[False for _ in range(w)] for _ in range(h)]
self.size = 0
def add(self, point):
r, c = point
self.lookup[r][c] = True
self.size += 1
def remove(self, point):
r, c = point
self.lookup[r][c] = False
self.size -= 1
def __contains__(self, point):
r, c = point
return 0 <= r < self.h and 0 <= c < self.w and self.lookup[r][c]
def __bool__(self):
return self.size != 0
def __len__(self):
return self.size
# H, W = ...
# pointset = PointSet(H, W)
# if (3, 5) in pointset:
# ...
第二次尝试:
# pointset = set()
# if (3, 5) in pointset:
# ...
第二个代码的执行速度要快得多。为什么会这样?
最佳答案
首先,您必须考虑 __contains__
的实现方法调用__getitem__
两次(因为您有一个列表列表),每个列表的复杂度为 0(1),并且会评估两个链式比较( 0 <= r < self.h
和 0 <= c < self.w
);在最坏的情况下,自 and
开始计算所有表达式只会在第一个 False
上短路。前一行中的可迭代解包会带来额外的开销。属性查找还添加了少量内容。
集合的成员资格查找只是简单的 0(1),所以我不知道你的代码如何能够击败它。
关于python - 列表查找比集合查找慢,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41343902/