python - 使用 cython 加速 itertools 组合

我有以下代码可以使用 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 是否已经如此优化以至于它的速度不能有任何更大的改进？

最佳答案

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

因为我很想知道 itertools 的通用实现如何对抗老派技巧，让我们来看看这个 Cython 实现的“n 中的所有子集 k”:

%%cython

ctypedef unsigned long long ull

cdef ull next_subset(ull subset):
   cdef ull smallest, ripple, ones
   smallest = subset& -subset
   ripple = subset + smallest
   ones = subset ^ ripple
   ones = (ones >> 2)//smallest
   subset= ripple | ones
   return subset


cdef subset2list(ull subset, int offset, int cnt):
    cdef list lst=[0]*cnt #pre-allocate
    cdef int current=0;
    cdef int index=0
    while subset>0:
        if((subset&1)!=0):
            lst[index]=offset+current
            index+=1
        subset>>=1
        current+=1
    return lst

def all_k_subsets(int start, int end, int k):
    cdef int n=end-start
    cdef ull MAX=1L<<n;
    cdef ull subset=(1L<<k)-1L;
    lst=[]
    while(MAX>subset):
         lst.append(subset2list(subset, start, k))
         subset=next_subset(subset)
    return lst

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

如果我们比较两种方法:

>>> %timeit x(1,45,6)
2.52 s ± 108 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

>>> %timeit all_k_subsets(1,45,6)
1.29 s ± 5.16 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

因子 2 的加速非常令人失望。

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

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

关于python - 使用 cython 加速 itertools 组合，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/50198393/