Что является более быстрой альтернативой 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, но я пока не выяснил, как это реализовать. Подобный вопрос имеет ответ о numpy, но я не понимаю, как это np.column_stack((np.repeat(a, b.size),np.tile(b, a.size))) должно работать в моем случае. Как я вижу сейчас, я буду в некотором роде массивом и буду меняться, и я не до конца понимаю, что делать с этим фактом.

Answer 1

Используя формулу для числа комбинаций , вы можете выполнить это вычисление итеративно, просто так:

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)

Разница увеличивается с увеличением числа, и это также не требует дополнительной памяти.

Answer 2

Самое быстрое решение дает @jdehesa, которая использует мультипликативную формулу для вычисления (рекурсивно) биномиальных коэффициентов . Ниже приведено несколько других попыток:

from itertools import accumulate
from scipy.special import binom, comb
import math

def f_math_comb(k, n):
    # works with python 3.8
    N = 1 << k  # N = 2**k
    return [math.comb(N, i) for i in range(n)]

def f_scipy_comb(k, n):
    N = 1 << k 
    return [comb(N, i, exact=True) for i in range(n)]

def f_scipy_binom(k, n):
    N = 1 << k 
    return list(map(int, binom(N, range(n))))

def f_itertools_accumulate(k, n):
    N = 1 << k
    p = (N + 1) / np.arange(1, n) - 1
    int_round = lambda x: int(round(x))
    return [1] + list(map(int_round, accumulate(p, mul)))

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

Тест:

k = 8
n = 2**k + 1

%timeit f_math_comb(k, n)
3.32 ms ± 45 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit f_scipy_comb(k, n)
3.23 ms ± 75.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit f_scipy_binom(k, n)
189 µs ± 2.15 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%timeit f_itertools_accumulate(k, n)
1.03 ms ± 12.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%timeit f_multip(k, n)
102 µs ± 10.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Одним из возможных улучшений является использование соотношения симметрии:

Редактировать : к сожалению, binom от scipy не всегда возвращает точные результаты, потому что он использует некоторую аппроксимацию для вычисления биномиальных коэффициентов для больших значений N. Аналогично, f_itertools_accumulate, из-за на округление вопросов для больших значений N, не дает точных результатов.

Answer 3

Я предполагаю, что ваш 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

В любом случае, он показывает, что мой подсчет без накопления обрабатывает большие значения, чем ваш метод, даже если он начинается медленнее.