Python字典键。 “在”复杂性
快速的问题主要满足我对这个话题的好奇心。
我正在用SQlite数据库后端编写一些大型的python程序，将来会处理大量的logging，所以我需要尽可能地进行优化。
对于一些function，我正在通过字典中的键进行search。 我一直在使用“in”关键字进行原型devise，并计划在之后的时间内返回并优化这些search，因为我知道“in”关键字通常是O（n）（因为这只是将python遍历整个列表并进行比较每个元素）。 但是，作为一个python字典基本上只是一个哈希映射，是python解释器足够聪明来解释：
if(key in dict.keys()): ...code... 至：
if(dict[key] != None): ...code...
它基本上是相同的操作，但顶部将是O（n），底部将是O（1）。
在我的代码中使用底部版本很容易，但是我只是好奇，想我会问。
首先， key in d.keys()可以保证给出与key in d相同的值。
in dict in操作，或者你从它（在3.x中）调用keys()返回的dict_keys对象不是 O（N），它是O（1）。
没有真正的“优化”正在进行; 只是使用散列是在散列表上实现__contains__的明显方式，就像实现__getitem__的明显方式一样。
你可能会问这是保证。
那么，不是的。 映射types基本上定义了dict作为collections.abc.Mapping的哈希表实现。 没有什么能阻止某人创build映射的哈希表实现，但仍然提供O（N）search。 但是做这样一个糟糕的实现会是额外的工作，那为什么呢？
如果你真的需要certificate自己，你可以testing你关心的每一个实现（使用一个分析器，或者使用某种types的自定义__hash__和__eq__来logging调用，或者…），或者读取源代码。
在2.x中，您不想调用keys ，因为这会生成密钥list ，而不是KeysView 。 你可以使用iterkeys ，但是这可能会产生一个迭代器或其他不是O（1）的东西。 所以，只要使用字典本身作为一个序列。
即使是3.x，你也不想拨打电话，因为没有必要。 迭代一个dict ，检查它的__contains__ ，通常把它当作一个序列来对待， 总是相当于对它的键做同样的事情，所以为什么要麻烦呢？ （当然，构build简单的KeyView ，并通过它访问，将会为您的程序运行时间和几个按键增加几个纳秒。）
（使用顺序操作对于d.keys() / d.iterkeys()和d是相当不明确的。除了性能问题，它们在每个CPython，Jython，IronPython和PyPy实现中是等价的，但似乎没有在3.x中的任何地方说出来，而且没关系，只要使用key in d ）。
虽然我们在这，但请注意这一点：
if(dict[key] != None):
…不会工作。 如果key不在dict ，则会引发KeyError ，不会返回None 。
另外，你不应该用==或!=检查None ; 总是用。
你可以用try -or来做到这一点，更简单的， if dict.get(key, None) is not None 。 但是，再次，没有理由这样做。 此外，这不会处理None是完全有效的项目的情况。 如果是这样的话，你需要做一些像sentinel = object(); if dict.get(key, sentinel) is not sentinel: 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 +树blist.blist实现它; 所以，它可能是O（n），O（1），O（log n），或者完全不同的东西。
在Python 2中， dict.keys()创build了整个键的列表，这就是为什么它是O(N)操作，而key in dict是O(1)操作。
if(dict[key] != None)在字典中没有findKeyError将会引发KeyError ，所以它不等于第一个代码。
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 3中， dict.keys()返回一个视图对象，它比Python 2的keys()更快，但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
正确的做法是这样的
if key in dict: do stuff
in运算符是O（1）用于字典和python集。
字典的in运算符的平均情况时间复杂度为O（1）。 有关其他dict（）方法的时间复杂性的详细信息，请访问此链接 。
