可以在Python中更快地对可变长度迭代的简单计算吗?
我正在计算由元组表示的两个向量之间的欧氏距离.
(u[0]-v[0])**2 + (u[1]-v[1])**2 + (u[3]-v[3])**2 ... 这种硬编码方式非常快.但是,我不想对这些载体的长度做出任何假设.这导致了以下解决方案: sum([(a-b)**2 for a,b in izip(u,v)]) # Faster without generator 要么 sum = 0 for i in xrange(len(u)): sum += (u[i]-v[i])**2 结果比第一个版本慢很多(至少两次).是否有一些聪明的方法来优化这一点,而不是诉诸于NumPy / SciPy?我知道这些软件包提供了最快的方式来做这些事情,但目前,我更想尝试优化“裸Python”的经验.我发现快速工作的是动态构建一个定义函数的字符串和exec()它,但这真的是最后的手段,我想说…… 要求: > CPython 2.7 尽管我的问题是关于一般小操作的问题,但您可以在解决方案中假设其中一个向量在多个函数调用中保持相同. 解决方法
我的理解是你不需要更快地编写代码,你只想知道为什么它更慢.要回答这个问题,让我们来看看反汇编.出于本讨论的目的,我将在函数调用中包装每个方法,在每个反汇编中可以忽略u和v的加载以及return命令.
def test1(u,v): return (u[0]-v[0])**2 + (u[1]-v[1])**2 + (u[3]-v[3])**2 dis.dis(test1) 0 LOAD_FAST 0 (u) 3 LOAD_CONST 1 (0) 6 BINARY_SUBSCR 7 LOAD_FAST 1 (v) 10 LOAD_CONST 1 (0) 13 BINARY_SUBSCR 14 BINARY_SUBTRACT 15 LOAD_CONST 2 (2) 18 BINARY_POWER 19 LOAD_FAST 0 (u) 22 LOAD_CONST 3 (1) 25 BINARY_SUBSCR 26 LOAD_FAST 1 (v) 29 LOAD_CONST 3 (1) 32 BINARY_SUBSCR 33 BINARY_SUBTRACT 34 LOAD_CONST 2 (2) 37 BINARY_POWER 38 BINARY_ADD 39 LOAD_FAST 0 (u) 42 LOAD_CONST 4 (3) 45 BINARY_SUBSCR 46 LOAD_FAST 1 (v) 49 LOAD_CONST 4 (3) 52 BINARY_SUBSCR 53 BINARY_SUBTRACT 54 LOAD_CONST 2 (2) 57 BINARY_POWER 58 BINARY_ADD 59 RETURN_VALUE 我以3的长度剪掉了第一个例子,因为它会一遍又一遍地重复相同的模式.您可以快速看到没有函数调用开销,并且几乎解释器正在对这些操作数进行尽可能少的工作以实现您的结果. def test2(u,v): sum((a-b)**2 for a,v)) dis.dis(test2) 0 LOAD_GLOBAL 0 (sum) 3 LOAD_CONST 1 (<code object <genexpr> at 02C6F458,file "<pyshell#10>",line 2>) 6 MAKE_FUNCTION 0 9 LOAD_GLOBAL 1 (izip) 12 LOAD_FAST 0 (u) 15 LOAD_FAST 1 (v) 18 CALL_FUNCTION 2 21 GET_ITER 22 CALL_FUNCTION 1 25 CALL_FUNCTION 1 28 RETURN_VALUE 我们在这里看到的是我们用生成器表达式创建一个函数,加载2个全局变量(sum和izip,全局查找比本地查找慢,我们不能避免它们只进行一次但是如果它们将被调用一个紧密循环,许多人将它们分配给本地,如_izip或_sum),然后连续遭受4个昂贵的字节码操作,调用izip,从生成器获取迭代器,调用生成器创建的函数,然后调用sum函数(将使用迭代器并在返回之前添加每个项目). def test3(u,v): sum = 0 for i in xrange(len(u)): sum += (u[i]-v[i])**2 dis.dis(test3) 0 LOAD_CONST 1 (0) 3 STORE_FAST 2 (sum) 6 SETUP_LOOP 52 (to 61) 9 LOAD_GLOBAL 0 (xrange) 12 LOAD_GLOBAL 1 (len) 15 LOAD_FAST 0 (u) 18 CALL_FUNCTION 1 21 CALL_FUNCTION 1 24 GET_ITER 25 FOR_ITER 32 (to 60) 28 STORE_FAST 3 (i) 31 LOAD_FAST 2 (sum) 34 LOAD_FAST 0 (u) 37 LOAD_FAST 3 (i) 40 BINARY_SUBSCR 41 LOAD_FAST 1 (v) 44 LOAD_FAST 3 (i) 47 BINARY_SUBSCR 48 BINARY_SUBTRACT 49 LOAD_CONST 2 (2) 52 BINARY_POWER 53 INPLACE_ADD 54 STORE_FAST 2 (sum) 57 JUMP_ABSOLUTE 25 60 POP_BLOCK 61 LOAD_CONST 0 (None) 64 RETURN_VALUE 我们在这里看到的是test2中发生的更直接的版本.没有生成器表达式或调用sum,但我们通过执行xrange(len(u))代替@Lucas Malor建议的更快的解决方案,用不必要的函数调用替换了该函数调用开销. def test4(u,v): mysum = 0 for a,v) : mysum += (a-b)**2 return mysum dis.dis(test4) 0 LOAD_CONST 1 (0) 3 STORE_FAST 2 (mysum) 6 SETUP_LOOP 47 (to 56) 9 LOAD_GLOBAL 0 (izip) 12 LOAD_FAST 0 (u) 15 LOAD_FAST 1 (v) 18 CALL_FUNCTION 2 21 GET_ITER 22 FOR_ITER 30 (to 55) 25 UNPACK_SEQUENCE 2 28 STORE_FAST 3 (a) 31 STORE_FAST 4 (b) 34 LOAD_FAST 2 (mysum) 37 LOAD_FAST 3 (a) 40 LOAD_FAST 4 (b) 43 BINARY_SUBTRACT 44 LOAD_CONST 2 (2) 47 BINARY_POWER 48 INPLACE_ADD 49 STORE_FAST 2 (mysum) 52 JUMP_ABSOLUTE 22 55 POP_BLOCK 56 LOAD_FAST 2 (mysum) 59 RETURN_VALUE 以上代表了@Lucas Malor的贡献,它在某些方面更快.它通过解包来替换下标操作,同时将调用次数减少到1.在很多情况下,你可以用你给我们的约束来快速实现. 请注意,如果要调用该函数足够的时间来计算开销,那么仅值得评估运行时生成的字符串,类似于test1中的函数.另请注意,随着u和v的长度变得越来越大(这通常是评估此类算法的方式),其他解决方案的函数调用开销变得越来越小,因此,在大多数情况下,最易读的解决方案非常优越.同时,即使在小的情况下速度较慢,如果序列的长度u和v可能很长,我建议使用生成器表达式而不是列表理解.在大多数情况下,内存节省将导致更快的执行速度(以及更快的gc). 总的来说,我的建议是,在短序列的情况下微小的加速只是不值得增加代码大小和与你正在通过执行微优化看到的其他python实现的不一致行为. “最佳”解决方案几乎肯定是test2. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |