回答这个问题我遇到了一个有趣的情况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以获取value每个key.第二种解决方案只是遍历OrderedDictionary键值对,它们必须打包成元组.
第二种解决方案慢2倍.
这是为什么？
我最近观看了这个视频,其中Raymond Hettinger说Python倾向于重用元组,因此没有额外的分配.
那么,这个性能问题归结为什么呢？
我想详细说明我为什么要问.
第一个解决方案是字典查找.它意味着采用key哈希,然后通过此哈希查找bin,然后从该bin获取密钥(希望不会发生密钥冲突),然后获取与该密钥相关联的值.
第二个解决方案只是通过所有箱子并产生这些箱子中的所有钥匙.它一个接一个地遍历所有的箱子而没有计算的开销.是的,它必须访问与这些键关联的值,但该值只是键的一步,而第一个解决方案必须通过hash-bin-key-value链来获取需要它的值.每个解决方案都必须获取值,第一个获取它通过hash-bin-key-value链,第二个获取它在访问key时再跟随一个指针.第二种解决方案的唯一开销是它必须将该值与密钥一起存储在元组中.事实证明,这种存储是开销的主要原因.鉴于所谓的"元组重用"(参见上面提到的视频),我仍然不完全理解为什么会这样.
在我看来,第二种解决方案必须与密钥一起保存价值,但它避免了我们必须进行哈希bin密钥计算和访问以获得该密钥的值.
性能差异主要是由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, self[k])
看看我们发现了什么:self[k].
您的第二个解决方案无法帮助我们避免哈希bin密钥计算.而dict更确切地说,items.iteritems().next()如果items是a 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,iteritems' 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 {
result = PyTuple_New(2);
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)1.第一个解决方案的平均时间复杂度与第二个解决方案的时间复杂度相同.它们都是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
1为dict对象列出的平均大小写时间假定对象的散列函数足够强大,以使冲突不常见.平均情况假定参数中使用的密钥是从所有密钥集中随机均匀选择的.请参阅TimeComplexity.
| 归档时间： |
|
| 查看次数： |
389 次 |
| 最近记录： |