加速 itertools 与 cython 的组合

Question

我有以下代码可以使用 itertools 生成指定范围内的所有可能组合，但我无法通过使用 cython 代码来提高速度。原始代码是这样的：

from itertools import *

def x(e,f,g):
    a=[]        
    for c in combinations(range(e, f),g):
        d = list((c))
        a.append(d) 

声明 cython 的类型后：

from itertools import *

cpdef x(int e,int f,int g):        
    cpdef tuple c
    cpdef list a
    cpdef list d

    a=[]        
    for c in combinations(range(e, f),g):    
        d = list((c))
        a.append(d)

我将后者保存为test_cy.pyx并使用编译cythonize -a -i test_cy.pyx

编译后，我使用以下代码创建了一个新脚本并运行它：

import test_cy

test_cy.x(1,45,6) 

我没有得到任何显着的速度提升，仍然花费了与原始脚本相同的时间，大约 10.8 秒。

我是否做错了什么，或者 itertools 已经如此优化以至于无法对其速度进行任何更大的改进？

Answer 1

正如评论中已经指出的，您不应期望 cython 能够加速您的代码，因为算法的大部分时间都花在 itertools 和创建列表上。

\n\n

因为我很好奇通用itertools实现如何对抗老式技巧，所以让我们看一下“n 中的所有子集 k”的 Cython 实现：

\n\n

%%cython\n\nctypedef unsigned long long ull\n\ncdef ull next_subset(ull subset):\n   cdef ull smallest, ripple, ones\n   smallest = subset& -subset      \n   ripple = subset + smallest    \n   ones = subset ^ ripple    \n   ones = (ones >> 2)//smallest \n   subset= ripple | ones    \n   return subset\n\n\ncdef subset2list(ull subset, int offset, int cnt):  \n    cdef list lst=[0]*cnt #pre-allocate\n    cdef int current=0;\n    cdef int index=0\n    while subset>0:\n        if((subset&1)!=0):\n            lst[index]=offset+current\n            index+=1\n        subset>>=1\n        current+=1\n    return lst\n\ndef all_k_subsets(int start, int end, int k):\n    cdef int n=end-start      \n    cdef ull MAX=1L<<n;\n    cdef ull subset=(1L<<k)-1L;\n    lst=[]\n    while(MAX>subset):\n         lst.append(subset2list(subset, start, k))\n         subset=next_subset(subset)\n    return lst\n

\n\n

此实现使用了一些众所周知的位技巧，并且有一个限制，即它最多只能用于 64 个元素。

\n\n

如果我们比较这两种方法：

\n\n

>>> %timeit x(1,45,6)\n2.52 s \xc2\xb1 108 ms per loop (mean \xc2\xb1 std. dev. of 7 runs, 1 loop each)\n\n>>> %timeit all_k_subsets(1,45,6)\n1.29 s \xc2\xb1 5.16 ms per loop (mean \xc2\xb1 std. dev. of 7 runs, 1 loop each)\n

\n\n

因子 2 的加速效果相当令人失望。

\n\n

然而，瓶颈在于列表的创建，而不是计算本身 - 很容易检查，如果不创建列表，计算将花费大约 0.1 秒。

\n\n

我的看法是：如果你认真对待速度，你不应该创建这么多列表，而应该动态处理子集（在 cython 中最好）——超过 10 的加速是可能的。如果必须将所有子集作为列表，那么您就不能指望有巨大的加速。

\n