69

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

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

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

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

至：

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

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

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

4

5 回答 5

138

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

对 a的in操作dict，或者dict_keys你调用keys()它返回的对象（在 3.x 中），不是O(N)，而是 O(1)。

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

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

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

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

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

即使在 3.x 中，您也不想调用keys，因为没有必要。迭代 a dict，检查它的__contains__，一般来说把它当作一个序列对待总是等价于对它的键做同样的事情，那么为什么要麻烦呢？（当然，构建琐碎的KeyView，并通过它访问，将为您的运行时间增加几纳秒，并为您的程序增加一些击键。）

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

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

if(dict[key] != None):

......不会工作。如果key不在中dict，这将提高KeyError，而不是返回None。

None此外，您永远不应该检查==or !=; 总是使用is.

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

所以，正确的写法是：

if key in d:

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

我知道“in”关键字通常是 O(n) （因为这只是转换为 python 迭代整个列表并比较每个元素

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

于 2013-07-09T03:30:04.800 回答
14

在 Python 2dict.keys()中，首先创建整个键列表，这就是为什么它是一个O(N)操作，而 whilekey in dict是一个O(1)操作。

if(dict[key] != None)KeyError如果在字典中找不到 key会引发，所以它不等同于第一个代码。

Python 2 结果：

>>> dic = dict.fromkeys(range(10**5))
>>> %timeit 10000 in dic
1000000 loops, best of 3: 170 ns per loop
>>> %timeit 10000 in dic.keys()
100 loops, best of 3: 4.98 ms per loop
>>> %timeit 10000 in dic.iterkeys()
1000 loops, best of 3: 402 us per loop
>>> %timeit 10000 in dic.viewkeys()
1000000 loops, best of 3: 457 ns per loop

在 Python 3dict.keys()中返回一个视图对象，它比 Python 2 快得多，keys()但仍然更慢 simple normal key in dict：

Python 3 结果：

>>> dic = dict.fromkeys(range(10**5))
>>> %timeit 10000 in dic
1000000 loops, best of 3: 295 ns per loop
>>> %timeit 10000 in dic.keys()
1000000 loops, best of 3: 475 ns per loop

仅使用：

if key in dict:
   #code
于 2013-07-09T03:30:13.143 回答
10

正确的方法是

if key in dict:
    do stuff

对于python 中的字典和集合， in运算符为 O(1)。

于 2013-07-09T03:31:00.680 回答
1

dict 的 in 运算符的平均案例时间复杂度为 O(1)。有关其他 dict() 方法的时间复杂度的详细信息，请访问此链接。

于 2017-09-13T16:22:08.000 回答
-2

兄弟你可以这样写......所以你也不需要检查异常，我的方法时间复杂度是 O(1)。

if (dict.get(key) != None):
....code.....enter code here
于 2021-06-26T06:57:18.647 回答