什么是itertools的更快替代品？

Question

k = 7
n = 30

def f(k,n):
    p = []
    for i in range(n):
        p.append(len(list(itertools.combinations([x for x in range(2**k)],i)))

上面的代码的工作缓慢，并且对于较大的变量值，会因错误而中断的问题。我尝试了sklearn.cartesian，但是当需要组合时得到了permutationa。我知道有一种方法可以使它与numpy一起更快地工作，但是我还没有弄清楚如何实现它。 Similar question有关于numpy的答案，但我不知道np.column_stack((np.repeat(a, b.size),np.tile(b, a.size)))应该如何工作。正如我现在所看到的，我将是数组的许多成员，并且会改变，而我并没有完全理解如何处理这个事实。

Answer 1

[我猜想当f和k足够大时，您的n遇到内存错误。这种变化应该获得长度而不会耗尽（太多）内存

In [167]: def f1(k,n): 
     ...:     p = [] 
     ...:     for i in range(n): 
     ...:         g = itertools.combinations([x for x in range(2**k)],i) 
     ...:         cnt = 0 
     ...:         for x in g: cnt += 1 
     ...:         p.append(cnt) 
     ...:     return p 

它返回与您的f相同的计数：

In [168]: f1(5,5)                                                                              
Out[168]: [1, 32, 496, 4960, 35960]
In [169]: f(5,5)                                                                               
Out[169]: [1, 32, 496, 4960, 35960]

虽然比较慢。

In [170]: timeit f1(5,5)                                                                       
3.47 ms ± 14 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In [171]: timeit f(5,5)                                                                        
2.72 ms ± 122 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [175]: timeit -r1 -n1 f1(5,5)                                                               
3.66 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)
In [176]: timeit -r1 -n1 f1(6,5)                                                               
61.4 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)
In [177]: timeit -r1 -n1 f1(7,5)                                                               
1.01 s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)
In [178]: timeit -r1 -n1 f1(8,5)                                                               
14.6 s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

尝试为f重复这些时间，我马上得到了killed。我应该从另一端尝试过：

In [179]: timeit -r1 -n1 f(8,5)                                                                
Killed

无论如何，它的确显示了我在不累积的情况下处理的值大于您的方法，即使它的开始速度较慢。

Answer 2

使用number of combinations的公式，您可以像这样简单地迭代进行此计算：

def f(k, n):
    p = [1]
    f = 1 << k
    for i in range(1, n):
        p.append((p[-1] * f) // i)
        f -= 1
    return p

# For comparison
def f_orig(k, n):
    import itertools
    p = []
    for i in range(n):
        p.append(len(list(itertools.combinations([x for x in range(2 ** k)],i))))
    return p

# Test
k = 4
n = 5
print(f(k, n))
# [1, 16, 120, 560, 1820]
print(f_orig(k, n))
# [1, 16, 120, 560, 1820]