整数パーティショニング用の Python コードをよりエレガントかつ効率的にするにはどうすればよいでしょうか?

整数分割のためのエレガントな Python コードを再考

コードのエレガントさを追求するため、プログラマは複雑な問題に対する簡潔で効率的な解決策を求めることがよくあります。そのような課題の 1 つが整数分割です。これは、指定された整数のすべての分割をより小さな正の整数に分割するタスクです。

解決策の洗練

これまでの試みでは有効な解決策が提供されてきましたが、 、望ましいレベルの優雅さが欠けていました。匿名の寄稿者によるより洗練されたソリューションは、コンパクトさと速度の両方を提供します。

<code class="python">def partitions(n, I=1):
    yield (n,)
    for i in range(I, n//2 + 1):
        for p in partitions(n-i, i):
            yield (i,) + p</code>

パフォーマンスの比較

このソリューションを Nolen の元のコードに対してベンチマークすると、速度の大幅な利点が明らかになります。

In [10]: %timeit -n 10 r0 = nolen(20)
1.37 s ± 28.7 ms per loop

In [11]: %timeit -n 10 r1 = list(partitions(20))
979 µs ± 82.9 µs per loop

追加のソリューション

計算要求の高いケースでは、accel_asc 関数を使用するとさらに高速なパフォーマンスが得られます。

<code class="python">def accel_asc(n):
    a = [0 for i in range(n + 1)]
    k = 1
    y = n - 1
    while k != 0:
        x = a[k - 1] + 1
        k -= 1
        while 2 * x < y:
            a[k] = x
            y -= x
            k += 1
        l = k + 1
        while x <= y:
            a[k] = x
            a[l] = y
            yield a[:k + 2]
            x += 1
            y -= 1
        a[k] = x + y
        y = x + y - 1
        yield a[:k + 1]</code>

ただし、それだけの価値はあります。このソリューションは、より単純なパーティションの実装よりも多くのメモリを必要とすることに注意してください。

以上が整数パーティショニング用の Python コードをよりエレガントかつ効率的にするにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。