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 ddict相同的值d。

而且，in对dict或操作（从3.x中dict_keys调用）返回的对象的操作 不是 O（N），而是O（1）。keys() __

没有真正的“优化”。只是使用哈希是在__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-或更简单地说，执行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）或完全不同的东西。