python - 使用 cython 加速 itertools 组合

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 和创建列表上。

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

%%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 是可能的。如果必须将所有子集都作为列表，那么您不能指望有很大的加速。