python - 了解性能差异

Question

接听this question我遇到了一个有趣的情况 2 个相似的代码片段执行起来完全不同。我问这里只​​是为了了解其中的原因并提高我对此类情况的直觉。

我将为 Python 2.7 调整代码片段(在 Python 3 中，性能差异是相同的)。

from collections import OrderedDict
from operator import itemgetter
from itertools import izip

items = OrderedDict([('a', 10), ('b', 9), ('c', 4), ('d', 7), ('e', 3), ('f', 0), ('g', -5), ('h', 9)])

def f1():
    return min(items, key=items.get)

def f2():
    return min(items.iteritems(), key=itemgetter(1))[0]


from timeit import Timer
N = 100000

print(Timer(stmt='f1()', setup='from __main__ import f1').timeit(number = N))
print(Timer(stmt='f2()', setup='from __main__ import f2').timeit(number = N))

输出:

0.603327797248
1.21580172899

第一个解决方案必须在 OrderedDictionary 中进行查找以获取每个 key 的 value。第二种解决方案只是遍历 OrderedDictionary 键值对，这些键值对必须打包到元组中。

第二个解决方案慢 2 倍。

这是为什么？

我最近看了this video ，其中 Raymond Hettinger 说 Python 倾向于重用元组，因此没有额外的分配。

那么，这个性能问题归结为什么呢？

---

我想详细说明一下我为什么要问。

第一个解决方案有字典查找。这意味着获取 key 哈希，然后通过该哈希找到 bin，然后从该 bin 中获取 key (希望不会发生 key 冲突)，然后获取与该 key 关联的值。

第二种解决方案只是遍历所有容器并生成这些容器中的所有 key 。它一个接一个地检查所有 bin，而无需计算要占用哪个 bin 的开销。是的，它必须访问与这些键关联的值，但值距离键只有一步，而第一个解决方案必须通过 hash-bin-key-value 链才能在需要时获取值。每个解决方案都必须获取值，第一个通过 hash-bin-key-value 链获取它，第二个在访问 key 时跟随一个指针获取它。第二种解决方案的唯一开销是它必须将此值与 key 一起临时存储在元组中。事实证明，这种存储是开销的主要原因。鉴于存在所谓的“元组重用”(参见上面提到的视频)，我仍然不完全理解为什么会这样。

在我看来，第二种解决方案必须将值与 key 一起保存，但它避免了我们必须进行 hash-bin-key 计算和访问以获取该 key 的值。

Answer 1

性能差异主要是由OrderedDict引起的。
OrderedDict 使用dict 的get 和__getitem__，但重新定义了它自己的__iter__和 iteritems .

    def __iter__(self):
        'od.__iter__()  iter(od)'
        # Traverse the linked list in order.
        root = self.__root
        curr = root[1]                                  # start at the first node
        while curr is not root:
            yield curr[2]                               # yield the curr[KEY]
            curr = curr[1]                              # move to next node

    def iteritems(self):
        'od.iteritems -> an iterator over the (key, value) pairs in od'
        for k in self:
            yield (k, <b>self[k]</b>)

看看我们发现了什么:self[k]。
您的第二个解决方案没有帮助我们避免 hash-bin-key 计算。而 dict 生成的迭代器，更准确地说，items.iteritems().next()如果 items 是一个 dict，则不进行该计算。

此外，iteritems 也更昂贵。

from timeit import Timer
N = 1000

d = {i:i for i in range(10000)}

def f1():
    for k in d: pass

def f2():
    for k in d.iterkeys(): pass

def f3():
    for v in d.itervalues(): pass

def f4():
    for t in d.iteritems(): pass

print(Timer(stmt='f1()', setup='from __main__ import f1').timeit(number=N))
print(Timer(stmt='f2()', setup='from __main__ import f2').timeit(number=N))
print(Timer(stmt='f3()', setup='from __main__ import f3').timeit(number=N))
print(Timer(stmt='f4()', setup='from __main__ import f4').timeit(number=N))

输出

0.256800375467
0.265079360645
0.260599391822
0.492333103788

与 iterkeys 比较' dictiter_iternextkey和 itervalues' dictiter_iternextvalue , 迭代项' dictiter_iternextitem有额外的部分。

    if (result->ob_refcnt == 1) {
        Py_INCREF(result);
        Py_DECREF(PyTuple_GET_ITEM(result, 0));
        Py_DECREF(PyTuple_GET_ITEM(result, 1));
    } else {
        <b>result = PyTuple_New(2);</b>
        if (result == NULL)
            return NULL;
    }
    di->len--;
    key = ep[i].me_key;
    value = ep[i].me_value;
    Py_INCREF(key);
    Py_INCREF(value);
    PyTuple_SET_ITEM(result, 0, key);
    PyTuple_SET_ITEM(result, 1, value);

我认为创建元组会降低性能。

Python 确实倾向于重用元组。
tupleobject.c显示

/* Speed optimization to avoid frequent malloc/free of small tuples */
#ifndef PyTuple_MAXSAVESIZE
#define PyTuple_MAXSAVESIZE     20  /* Largest tuple to save on free list */
#endif
#ifndef PyTuple_MAXFREELIST
#define PyTuple_MAXFREELIST  2000  /* Maximum number of tuples of each size to save */
#endif

这种优化只是意味着 Python 不会从头开始构建一些元组。但是还有很多工作要做。

---

大小写:字典

如果将OrderedDict换成dict，我觉得总体来说第二种方案稍微好一些。
Python 字典是使用哈希表实现的。所以查找速度很快。查找的平均时间复杂度为 O(1)，最差的为 O(n)¹。第一个解决方案的平均时间复杂度与第二个解决方案的时间复杂度相同。它们都是 O(n)。因此，第二种解决方案没有优势，有时甚至更慢，尤其是当输入数据较小时。那样的话，iteritems带来的额外开销就无法补偿了。

from collections import OrderedDict
from operator import itemgetter
from timeit import Timer
from random import randint, random

N = 100000
xs = [('a', 10), ('b', 9), ('c', 4), ('d', 7), ('e', 3), ('f', 0), ('g', -5), ('h', 9)]

od = OrderedDict(xs)
d = dict(xs)

def f1od_min():
    return min(od, key=od.get)

def f2od_min():
    return min(od.iteritems(), key=itemgetter(1))[0]

def f1d_min():
    return min(d, key=d.get)

def f2d_min():
    return min(d.iteritems(), key=itemgetter(1))[0]

def f1od():
    for k in od: pass

def f2od():
    for t in od.iteritems(): pass

def f1d():
    for k in d: pass

def f2d():
    for t in d.iteritems(): pass

print 'min'
print(Timer(stmt='f1od_min()', setup='from __main__ import f1od_min').timeit(number=N))
print(Timer(stmt='f2od_min()', setup='from __main__ import f2od_min').timeit(number=N))
print(Timer(stmt='f1d_min()', setup='from __main__ import f1d_min').timeit(number=N))
print(Timer(stmt='f2d_min()', setup='from __main__ import f2d_min').timeit(number=N))
print
print 'traverse'
print(Timer(stmt='f1od()', setup='from __main__ import f1od').timeit(number=N))
print(Timer(stmt='f2od()', setup='from __main__ import f2od').timeit(number=N))
print(Timer(stmt='f1d()', setup='from __main__ import f1d').timeit(number=N))
print(Timer(stmt='f2d()', setup='from __main__ import f2d').timeit(number=N))

输出

min
0.398274431527
0.813040903243
0.185168156847
0.249574387248    <-- dict/the second solution

traverse
0.251634216081
0.642283865687
0.0565099754298
0.0958057518483

然后将N和xs替换为

N = 50
xs = [(x, randint(1, 100)) for x in range(100000)]

输出

min
1.5148923257
3.47020082161
0.712828585756
0.70823812803    <-- dict/the second solution

traverse
0.975989336634
2.92283956481
0.127676073356
0.253622387762

现在将 N 和 xs 替换为

N = 10
xs = [(random(), random()) for x in range(1000000)]

输出

min
6.23311265817
10.702984667
4.32852708934
2.87853889251    <-- dict/the second solution

traverse
2.06231783648
9.49360449443
1.33297618831
1.73723008092

最后，第二个解决方案开始大放异彩。

---

第一种解决方案的最坏情况:哈希冲突

让

N = 10000
xs = [(2 ** (32 + x) - 2 ** x + 1, 1) for x in range(100)]
# hash(2 ** (32 + x) - 2 ** x + 1) is always 1

输出

min
2.44175265292    <-- lookup is slow
2.76424538594    <-- lookup is slow
2.26508627493    <-- lookup is slow
0.199363955475

traverse
0.200654482623
2.59635966303    <-- lookup is slow
0.0454684184722
0.0733798569371

---

¹ 为 dict 对象列出的平均案例时间假定对象的哈希函数足够稳健，不会发生冲突。平均情况假设参数中使用的 key 是从所有 key 集中随机选择的。参见 TimeComplexity .