key=dictionary.get的效率是多少？

Question

我有一本字典，我想找到优雅而有效的方法来查找 key:value 对，其中字典中的值最小（最小值之一，如果存在的话）。除了明显的 for 循环方法外，我还在 Whosebug 中发现了其他几种方法：

第一种方法：

  temporary = [x for x in myDictionary.items()] # list is created just for using sorted()
  foundKey, minimalValue = sorted(temporary, key=lambda x: x[1]) [0]

第二种方法：

  minimalValue = min(myDictionary.values())
  foundKey = min(myDictionary, key=myDictionary.get)

对于包含数千项的 myDictionary，第二个运行速度稍快一些，但是...我找不到 key=myDictionary.get 构造的解释。不能将两分钟合二为一 foundKey, minimalValue = ... 吗？

Answer 1

第二种方法可以更好地表述为

foundKey = min(myDictionary, key=myDictionary.get)
minValue = myDictionary[foundKey]

方法 get 检索与被检查的键对应的值，因此不是比较 key1、key2，而是比较 myDictionary.get[key1]、myDictionary.get[key2].

您同样可以使用 __getitem__。它可能会更快，但看起来不会那么漂亮：

foundKey = min(myDictionary, key=myDictionary.__getitem__)

顺便说一下，第一种方法有两个可能的改进：

temporary = list(myDictionary.items())
foundKey, minimalValue = sorted(temporary, key=lambda x: x[1])[0]

或

temporary = [x[::-1] for x in myDictionary.items()]
foundKey, minimalValue = min(temporary)

或

foundKey, minimalValue = min(zip(myDictionary.values(), myDictionary.keys()))

时机

让我们制作一个大小为 n 的字典：

from random import shuffle

values = list(range(n))
shuffle(values)
myDictionary = dict(zip(map('{:08d}'.format, range(n)), values))

n=10000 的时间：

%%timeit
... temporary = [x for x in myDictionary.items()]
... foundKey, minimalValue = sorted(temporary, key=lambda x: x[1])[0]
5.76 ms ± 32.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%%timeit
... minimalValue = min(myDictionary.values())
... foundKey = min(myDictionary, key=myDictionary.get)
1.85 ms ± 3.57 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

很明显运行 min (O(n)) 比 sorted (O(n log n)) 快。

%%timeit
... foundKey = min(myDictionary, key=myDictionary.get)
... minValue = myDictionary[foundKey]
1.36 ms ± 10.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

所以运行 min 并且查找比运行 min 快两次。

%timeit foundKey, minimalValue = min(zip(myDictionary.values(), myDictionary.keys()))
1.32 ms ± 6.82 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

运行 min 没有查找更快。

%%timeit
... foundKey = min(myDictionary, key=myDictionary.__getitem__)
... minValue = myDictionary[foundKey]
1.27 ms ± 2.77 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

使用 __getitem__ 查找更快。

TL;DR

这里显示的最快方法似乎是

foundKey = min(myDictionary, key=myDictionary.__getitem__)
minValue = myDictionary[foundKey]

key=dictionary.get的效率是多少？

What is efficiency of key=dictionary.get?

python

dictionary

min

python-3.x