用于搜索集合的最佳数据结构

Question

目前，我有数十万个整数 ID 的集合，并且我正在执行以下任务（假设该集合cache现在存储在列表中）：

cache = list()
# lets say this cache is populated
for x in range(0,1000000):
    if x not in cache:
        #do_something

对于我来说，使用列表来搜索not in某些内容的成本有多高？我会从使用另一种数据结构中受益吗？如果是的话，哪种数据结构最好？

Answer 1

您应该考虑使用set. 虽然最坏情况的时间复杂度x in cache仍然是 O(n)，但平均情况是 O(1) ( source )。