7

私は、AZのセットからX、Y、Zのサブセットを取得するという非常に単純な確率計算を行っています（対応する確率x、y、zを使用）。

そして、数式が非常に重いため、それらを処理するために、sympyを使用してこれらの多項式を単純化しようとしています（または収集または因数分解します-正確な定義はわかりません） 。

だから..これを持っている（対応する確率x、y、zを持つAZのセットからX、Y、Zのサブセットを取得する非常に単純な確率計算式）

import sympy as sp

x, y, z = sp.symbols('x y z')

expression = (
    x * (1 - x) * y * (1 - x - y) * z +
    x * (1 - x) * z * (1 - x - z) * y +

    y * (1 - y) * x * (1 - y - x) * z +
    y * (1 - y) * z * (1 - y - z) * x +

    z * (1 - z) * y * (1 - z - y) * x +
    z * (1 - z) * x * (1 - z - x) * y
)

こんなものが欲しい

x * y * z * (6 * (1 - x - y - z) + (x + y) ** 2 + (y + z) ** 2 + (x + z) ** 2)

可能な限り少ない操作（ 、、、、、 ...）を持つよう+に書き直されたポリ-***

、、、してみましfactor()た。しかし、結果は私の期待とは異なります。ほとんど私は得るcollect()simplify()

2*x*y*z*(x**2 + x*y + x*z - 3*x + y**2 + y*z - 3*y + z**2 - 3*z + 3)

sympyは多項式を単純な形に組み合わせることができることを私は知っています：

sp.factor(x**2 + 2*x*y + y**2)  # gives (x + y)**2

しかし、上記の式から多項式を組み合わせるためにsympyを作成するにはどうすればよいですか？

これがsympyで不可能なタスクである場合、他のオプションはありますか？

4

3 に答える 3

7

いくつかの方法をまとめると、今回は良い答えが得られます。この戦略が、生成した方程式でより頻繁に機能するかどうか、または名前が示すように、これが今回の幸運な結果であるかどうかを確認するのは興味深いことです。

def iflfactor(eq):
    """Return the "I'm feeling lucky" factored form of eq."""
    e = Mul(*[horner(e) if e.is_Add else e for e in
        Mul.make_args(factor_terms(expand(eq)))])
    r, e = cse(e)
    s = [ri[0] for ri in r]
    e = Mul(*[collect(ei.expand(), s) if ei.is_Add else ei for ei in
        Mul.make_args(e[0])]).subs(r)
    return e

>>> iflfactor(eq)  # using your equation as eq
2*x*y*z*(x**2 + x*y + y**2 + (z - 3)*(x + y + z) + 3)
>>> _.count_ops()
15

ところで、factor_termsとgcd_termsの違いは、factor_termsは、手動で行うのと同じように、式の元の構造を維持しながら、共通の用語を引き出すのに一生懸命働くことです（つまり、引き出すことができるAddsで共通の用語を探す） 。

>>> factor_terms(x/(z+z*y)+x/z)
x*(1 + 1/(y + 1))/z
>>> gcd_terms(x/(z+z*y)+x/z)
x*(y*z + 2*z)/(z*(y*z + z))

それが価値があるもののために、

クリス

于 2013-03-04T02:54:22.830 に答える
3

私の知る限り、それを正確に行う機能はありません。実はとても難しい問題だと思います。簡単な式の説明については、単純な式の演算数を減らすを参照してください。

ただし、SymPyには、試すことができる簡略化関数がかなりあります。別の結果をもたらすあなたが言及していないものはgcd_terms、拡張を行わずにシンボリックgcdを因数分解するです。それは与えます

>>> gcd_terms(expression)
x*y*z*((-x + 1)*(-x - y + 1) + (-x + 1)*(-x - z + 1) + (-y + 1)*(-x - y + 1) + (-y + 1)*(-y - z + 1) + (-z + 1)*(-x - z + 1) + (-z + 1)*(-y - z + 1))

もう1つの便利な関数は.count_ops、式の演算数をカウントするです。例えば

>>> expression.count_ops()
47
>>> factor(expression).count_ops()
22
>>> e = x * y * z * (6 * (1 - x - y - z) + (x + y) ** 2 + (y + z) ** 2 + (x + z) ** 2)
>>> e.count_ops()
18

（SymPyはにを自動的に配布するためe.count_ops()、これは自分で数えたものと同じではないことに注意してください）。6*(1 - x - y - z)6 - 6*x - 6*y - 6*z

その他の便利な機能：

  • cse：式に対して共通部分式除去を実行します。場合によっては、個々のパーツを単純化してから、元に戻すことができます。これは、一般的に重複した計算を回避するのにも役立ちます。

  • horner：ホーナースキームを多項式に適用します。これにより、多項式が1つの変数に含まれる場合、演算の数が最小限に抑えられます。

  • factor_terms：に似ていgcd_termsます。実際、違いが何であるかは完全にはわかりません。

デフォルトでは、simplifyいくつかの簡略化を試み、によって最小化されたものを返すことに注意してくださいcount_ops。

于 2013-03-03T22:25:39.743 に答える
1

私も同様の問題を抱えており、これに遭遇する前に独自のソリューションを実装することになりました。鉱山は、操作の数を減らすことではるかに良い仕事をしているようです。ただし、私の場合は、変数のすべての組み合わせに対してブルートフォーススタイルのコレクションセットも実行します。したがって、実行時間は変数の数で超指数関数的に増加します。OTOH、私はそれを7つの変数を持つ方程式で、不合理ではない（しかしリアルタイムからはほど遠い）時間で実行することができました。

ここでいくつかの検索ブランチを整理する方法がいくつかある可能性がありますが、私はそれを気にしませんでした。さらなる最適化を歓迎します。

def collect_best(expr, measure=sympy.count_ops):
    # This method performs sympy.collect over all permutations of the free variables, and returns the best collection
    best = expr
    best_score = measure(expr)
    perms = itertools.permutations(expr.free_symbols)
    permlen = np.math.factorial(len(expr.free_symbols))
    print(permlen)
    for i, perm in enumerate(perms):
        if (permlen > 1000) and not (i%int(permlen/100)):
            print(i)
        collected = sympy.collect(expr, perm)
        if measure(collected) < best_score:
            best_score = measure(collected)
            best = collected
    return best

def product(args):
    arg = next(args)
    try:
        return arg*product(args)
    except:
        return arg

def rcollect_best(expr, measure=sympy.count_ops):
    # This method performs collect_best recursively on the collected terms
    best = collect_best(expr, measure)
    best_score = measure(best)
    if expr == best:
        return best
    if isinstance(best, sympy.Mul):
        return product(map(rcollect_best, best.args))
    if isinstance(best, sympy.Add):
        return sum(map(rcollect_best, best.args))

パフォーマンスを説明するために、このペーパー（paywalled、申し訳ありません）には、最大29の項と拡張形式の158の操作を持つ7つの変数の5次多項式である7つの式があります。rcollect_bestと@smichrの両方を適用した後iflfactor、7つの数式の演算数は次のようになります。

[6, 15, 100, 68, 39, 13, 2]

と

[32, 37, 113, 73, 40, 15, 2]

それぞれ。 数式の1iflfactorつよりも433％多くの操作があります。rcollect_bestまた、展開された数式の演算数は次のとおりです。

[39, 49, 158, 136, 79, 27, 2]
于 2019-09-06T20:36:41.063 に答える