首頁 >後端開發 >Python教學 >如何讓整數分區的 Python 程式碼更優雅、更有效率?

如何讓整數分區的 Python 程式碼更優雅、更有效率?

Patricia Arquette
Patricia Arquette原創
2024-11-05 16:49:02917瀏覽

How Can Python Code for Integer Partitioning Be Made More Elegant and Efficient?

重溫整數分區的優雅Python 代碼

在追求代碼優雅的過程中,程式設計師常常尋求簡潔高效的複雜問題解決方案。其中一個挑戰是整數分區,即查找給定整數的所有分區為更小的正整數的任務。

完善解決方案

雖然之前的嘗試提供了有效的解決方案,但他們缺乏所需的優雅程度。匿名貢獻者提出的更完善的解決方案既緊湊又速度快:

<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中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn