9

指定された整数のすべてのパーティションを生成する必要があります。
私は、ジェローム・ケレハーによるこのアルゴリズムを見つけました。これは、最も効率的なアルゴリズムであると言われています。

def accelAsc(n):
    a = [0 for i in range(n + 1)]
    k = 1
    a[0] = 0
    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]

参照： http： //homepages.ed.ac.uk/jkellehe/partitions.php

ちなみに、あまり効率的ではありません。このような入力の場合40、出力を提供する前に、システム全体が数秒間フリーズします。

再帰的なアルゴリズムだとしたら、キャッシュ機能などで装飾して効率を上げようと思いますが、そういうわけではどうしたらいいのかわかりません。

このアルゴリズムを高速化する方法についていくつか提案がありますか？または、別のアプローチ、または別のアプローチを最初から作成するための別のアプローチを提案できますか？

4

4 に答える 4

12

コンポジションを直接生成するには、次のアルゴリズムを使用できます。

def ruleGen(n, m, sigma):
    """
    Generates all interpart restricted compositions of n with first part
    >= m using restriction function sigma. See Kelleher 2006, 'Encoding
    partitions as ascending compositions' chapters 3 and 4 for details.
    """
    a = [0 for i in range(n + 1)]
    k = 1
    a[0] = m - 1
    a[1] = n - m + 1
    while k != 0:
        x = a[k - 1] + 1
        y = a[k] - 1
        k -= 1
        while sigma(x) <= y:
            a[k] = x
            x = sigma(x)
            y -= x
            k += 1
        a[k] = x + y
        yield a[:k + 1]

このアルゴリズムは非常に一般的であり、さまざまなタイプのパーティションとコンポジションを生成できます。あなたの場合、

ruleGen(n, 1, lambda x: 1)

すべての無制限の構成を生成します。3番目の引数は制限関数と呼ばれ、必要な構成/パーティションのタイプを記述します。生成されたすべてのコンポジションを平均すると、各コンポジションを生成するために必要な労力が一定であるため、この方法は効率的です。Pythonで少し速くしたい場合は、関数sigmaを1に置き換えるのは簡単です。

ここでも注目に値するのは、一定の償却時間アルゴリズムの場合、生成されたオブジェクトを実際に使用することで、オブジェクトの生成コストがほぼ確実に支配されることです。たとえば、すべてのパーティションをリストに格納する場合、この大きなリストのメモリの管理に費やされる時間は、パーティションの生成に費やされる時間よりもはるかに長くなります。

たとえば、何らかの理由で、各パーティションの積を取得したいとします。これに素朴なアプローチをとる場合、関連する処理は部品の数に比例しますが、生成のコストは一定です。処理が生成コストを支配しない組み合わせ生成アルゴリズムのアプリケーションを考えるのは非常に困難です。したがって、実際には、sigma（x）=xでより単純でより一般的なruleGenを使用することと特殊なaccelAscを使用することの間に測定可能な違いはありません。

于 2012-05-01T14:21:09.647 に答える
3

同じ入力に対してこの関数を繰り返し使用する場合でも、戻り値をキャッシュする価値がある可能性があります（別々の実行でこの関数を使用する場合は、結果をファイルに保存できます）。

大幅に高速なアルゴリズムが見つからない場合は、コードをC拡張機能に移動するか（これはおそらくcythonを使用するのが最も簡単です）、あるいは代わりにPyPyを使用することで、これを1桁または2桁高速化できるはずです。 CPythonの（PyPyには欠点があります-Python 3、またはnumpyやscipyなどの一般的に使用されるライブラリはまだサポートされていません）。

この理由は、Pythonは動的に型付けされているため、インタプリタはおそらくほとんどの時間を変数の型のチェックに費やしているためです。インタプリタが知っているすべての場合、操作の1つがx文字列に変わる可能性があります。この場合、次のような式が使用されますx + y。突然非常に異なる意味を持ちます。Cythonは、変数を整数として静的に宣言できるようにすることでこの問題を回避しますが、PyPyには、冗長な型チェックを最小限に抑えるジャストインタイムコンパイラがあります。

于 2012-04-20T10:55:50.130 に答える
2

n=75でテストすると次のようになります。

PyPy 1.8：

w:\>c:\pypy-1.8\pypy.exe pstst.py
1.04800009727 secs.

CPython 2.6：

w:\>python pstst.py
5.86199998856 secs.

Cython + mingw + gcc 4.6.2：

w:\pstst> python -c "import pstst;pstst.run()"
4.06399989128

Psyco（？）との違いは見られませんでした

実行機能：

def run():
    import time
    start = time.time()
    for p in accelAsc(75):
        pass
    print time.time() - start, 'secs.'

CythonのaccelAscの定義を次のように変更した場合：

def accelAsc(int n):
    cdef int x, y, k
    # no more changes..

Cythonの時間を2.27秒に短縮しました。

于 2012-04-20T11:33:11.387 に答える
0

あなたのパフォーマンスの問題はどこかにあると思います。

私はそれを他のアプローチと比較しませんでしたが、それは私には効率的であるように見えます：

import time

start = time.time()
partitions = list(accelAsc(40))
print('time: {:.5f} sec'.format(time.time() - start))
print('length:', len(partitions))

与えた：

time: 0.03636 sec
length: 37338
于 2012-04-20T10:46:28.647 に答える