python - 有什么比 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，但在需要组合时得到了排列结果。我知道有一种方法可以让它用 numpy 更快地工作，但我还没有弄清楚如何实现它。 Similar question有关于 numpy 的答案，但我不明白 np.column_stack((np.repeat(a, b.size),np.tile(b, a.size))) 应该如何工作就我而言。正如我现在所看到的，我将是数组的许多维度，并且会发生变化，我不完全理解如何处理这个事实。

Answer 1

使用 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]

一个小基准:

k = 5
n = 8
%timeit f(k, n)
# 1.55 µs ± 498 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit f_orig(k, n)
# 528 ms ± 1.15 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

随着数量的增加，差异会变得更大，而且这不需要任何额外的内存。