Python 字典键。 "In"复杂度

Question

快速提问，主要满足我对该主题的好奇心。

我正在编写一些带有 SQlite 数据库后端的大型 python 程序，并且将来会处理大量记录，因此我需要尽可能优化。

对于一些功能，我正在通过字典中的键进行搜索。我一直在使用“in”关键字进行原型(prototype)设计，并计划稍后返回并优化这些搜索，因为我知道“in”关键字通常是 O(n)(因为这只是转换为 python 遍历整个列表并进行比较每个元素)。但是，作为一个 python dict 基本上只是一个 HashMap ，python 解释器是否足够聪明来解释:

if(key in dict.keys()):
    ...code...

到:

if(dict[key] != None):
    ...code...

这基本上是相同的操作，但顶部是 O(n)，底部是 O(1)。

在我的代码中使用底层版本对我来说很容易，但后来我只是好奇并想我会问。

Answer 1

首先，key in d.keys() 保证为您提供与任何dict d 中的key in d 相同的值。

以及 dict 上的 in 操作，或调用 keys() 得到的 dict_keys 对象> 在它上面(在 3.x 中)，不是 O(N)，它是 O(1)。

没有真正的“优化”；只是使用哈希是在哈希表上实现 __contains__ 的明显方式，就像实现 __getitem__ 的明显方式一样。

---

你可能会问这是在哪里保证的。

好吧，事实并非如此。 Mapping Types基本上将 dict 定义为 collections.abc.Mapping 的哈希表实现.没有什么能阻止某人创建映射的哈希表实现，但仍提供 O(N) 搜索。但做出如此糟糕的实现将是额外的工作，那他们为什么会这样做呢？

如果您真的需要向自己证明这一点，您可以测试您关心的每个实现(使用分析器，或者使用带有自定义 __hash__ 和 __eq__ 的某种类型> 记录调用，或...)，或读取源代码。

---

在 2.x 中，您不想调用 keys，因为这会生成一个键的 list，而不是 KeysView .您可以使用 iterkeys，但这可能会生成一个迭代器或其他不是 O(1) 的东西。因此，只需将 dict 本身用作序列即可。

即使在 3.x 中，您也不想调用 keys，因为没有必要。迭代一个dict，检查它的__contains__，一般来说把它当作一个序列来处理总是相当于对它的键做同样的事情，所以何必？ (当然，构建微不足道的 KeyView 并通过它进行访问，会增加几纳秒的运行时间和一些击键次数。)

(不清楚使用序列操作对于 d.keys()/d.iterkeys() 和 d 是等价的2.x. 除了性能问题之外，它们在每个 CPython、Jython、IronPython 和 PyPy 实现中都是等效的，但似乎在任何地方都没有像 3.x 中那样说明。没关系；只需使用 key in d。)

---

当我们这样做时，请注意:

if(dict[key] != None):

... 是行不通的。如果 key 不在 dict 中，这将引发 KeyError，而不返回 None。

另外，你不应该检查 None 与 == 或 !=;总是使用 is。

你可以用 try 来做到这一点——或者，更简单地说，if dict.get(key, None) is not None。但同样，没有理由这样做。此外，这不会处理 None 是完全有效的项目的情况。如果是这种情况，您需要执行类似 sentinel = object(); 之类的操作。如果 dict.get(key, sentinel) 不是哨兵:.

---

所以，正确的写法是:

if key in d:

---

更一般地说，这是不正确的:

I know the "in" keyword is generally O(n) (as this just translates to python iterating over an entire list and comparing each element

in 运算符，与大多数其他运算符一样，只是对 __contains__ 方法的调用(或 C/Java/.NET/RPython 内置的等效方法) . list 通过迭代列表并比较每个元素来实现它； dict 通过散列值并查找散列来实现它； blist.blist 通过遍历 B+Tree 来实现；等等。所以，它可能是 O(n)、O(1)、O(log n) 或完全不同的东西。