Python 字典的键。“在”复杂性中-IT科技

Python 字典的键。“在”复杂性中

2025-03-20 08:47:00

admin

原创

摘要：问题描述：问一个简单的问题，主要是为了满足我对这个话题的好奇心。我正在使用 SQlite 数据库后端编写一些大型 python 程序，将来会处理大量记录，因此我需要尽可能地进行优化。对于一些函数，我正在字典中搜索键。我一直在使用“in”关键字进行原型设计，并计划稍后返回并优化这些搜索，因为我知道“in”关键字...

问题描述：

问一个简单的问题，主要是为了满足我对这个话题的好奇心。

我正在使用 SQlite 数据库后端编写一些大型 python 程序，将来会处理大量记录，因此我需要尽可能地进行优化。

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

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

到：

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

它基本上是相同的操作，但顶部为 O（n），底部为 O（1）。

我可以轻松地在我的代码中使用底部版本，但我只是好奇并想问一下。

解决方案 1：

首先，key in d.keys()保证给你key in d与任何 dict相同的值d。

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

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

您可能会问哪里能保证这一点。

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

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

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

即使在 3.x 中，您也不想调用keys，因为没有必要。迭代dict，检查其__contains__，并且通常将其视为序列，始终等同于对其键执行相同的操作，所以为什么要费心呢？（当然，构建简单的KeyView，并通过它进行访问，将使您的运行时间增加几纳秒，并为您的程序增加一些击键次数。）

（目前还不太清楚在 2.x 中使用序列操作是否等同于d.keys()/d.iterkeys()和d。除了性能问题之外，它们在每个 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(); 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) 或完全不同的东西。

解决方案 2：

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

if(dict[key] != None)`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

仅使用：