python - 列表查找比集合查找慢

Question

我目前正在做一个项目，其中我必须多次检查给定的 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:
#    ...

第二个代码的执行速度要快得多。为什么会这样？

Answer 1

首先，您必须考虑 __contains__ 的实现方法调用__getitem__ 两次(因为您有一个列表列表)，每个列表的复杂度为 0(1)，并且会评估两个链式比较( 0 <= r < self.h 和 0 <= c < self.w )；在最坏的情况下，自 and 开始计算所有表达式只会在第一个 False 上短路。前一行中的可迭代解包会带来额外的开销。属性查找还添加了少量内容。

集合的成员资格查找只是简单的 0(1)，所以我不知道你的代码如何能够击败它。