Python字典键."在"复杂性

Question

快速提问主要是为了满足我对这个话题的好奇心.

我正在编写一些带有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).

我很容易在我的代码中使用底部版本,但后来我只是好奇并且想我会问.

Answer 1

首先,key in d.keys()保证给你与key in d任何字典相同的价值d.

in对a 的操作dict,或者dict_keys你从keys()它上面调用的对象(在3.x中)的操作不是 O(N),它是O(1).

没有真正的"优化"正在进行; 只是使用哈希是在__contains__哈希表上实现的明显方法,就像它是显而易见的实现方式一样__getitem__.

你可能会问这是有保证的.

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

如果您确实需要自己证明,可以测试您关心的每个实现(使用分析器,或使用某种类型的自定义__hash__和__eq__日志调用,或者......),或者阅读源代码.

在2.x中,您不想调用keys,因为它会生成一个list键,而不是一个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用==或检查!=; 总是用is.

您可以使用try-or,更简单地执行此操作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 /爪哇/ .NET/RPython内建).list通过迭代列表并比较每个元素来实现它; dict通过散列值并查找哈希来实现它; blist.blist通过走B +树实现它; 因此,它可能是O(n),O(1),O(log n)或完全不同的东西.

Answer 2

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

if(dict[key] != None)KeyError如果在dict中找不到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 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

Answer 3

这样做的正确方法是

if key in dict:
    do stuff

的在操作者是在python字典和集O(1).