Я предполагаю, что ваш 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
В любом случае, он показывает, что мой подсчет без накопления обрабатывает большие значения, чем ваш метод, даже если он начинается медленнее.