2

私は学生と一緒に、有限状態マシンの簡単なデモを作成していました。

s2 = {}
s1 = {}
s1["0"] = s2
s1["1"] = s1
s2["0"] = s1
s2["1"] = s2
machine = {"start": s1, "accepting": [s1]}

def recognize(fsm, in_string):
    return do_recognize(fsm, fsm["start"], in_string)

def do_recognize(fsm, current, in_string):
    if len(in_string) == 0:
        return current in fsm["accepting"]

   return do_recognize(fsm, current[in_string[0]] ,
                 in_string[1:])

print (recognize(machine, "0"))

このマシンは、偶数の 0 を含む文字列を認識し、「適切な」文字列 (「1」や「010」など) で正常に動作します。しかし、上記のような「悪い」文字列では、無限ループに入り、fsm["accepting"] の戻り電流でスタック オーバーフローが発生します。

問題は 2 つの状態の比較にあると判断できました。実際、s1 == s2 と書くだけで、まったく同じバグを生成できます。しかし、s1 == s1 (良い状態) は問題なく動作します。

何が起こっているのかについての私の最善の推測は、それが深い比較を行っており、循環している s2 のすべての参照をたどろうとしているということです。しかし、なぜ非対称なのですか (つまり、s1 == s1 で同じ問題が発生しないのはなぜですか)? どうすればそれを回避できますか？

4

2 に答える 2

4

s1この問題は、との間の循環参照に関係していs2ます。

s1これは、比較することを不可能にしますs2(cmp()関係する限り、2 つの辞書は無限の深さを持っています)。次の点を考慮してください。

print s1 == s1 # immediately returns True, probably due to equal object ids
print s1 == s2 # RuntimeError: maximum recursion depth exceeded in cmp

これは、なぜs1 in fsm["accepting"]機能し、s2 in fsm["accepting"]壊れるのかを説明しています。

これを修正する簡単な方法は、交換することです

return current in fsm["accepting"]

と

return id(current) in map(id, fsm["accepting"])

これは、無限に深い 2 つの辞書を値で比較しようとするのではなく、ID で状態を比較します。

于 2012-11-28T16:35:18.687 に答える
2

ディクショナリを比較すると、ディクショナリ内の各項目 (キーと値のペア) も比較されるため、循環参照が同じキーを含むディクショナリ間に循環参照がある場合、それらを比較すると、この最大再帰深度超過エラーが発生します。 :

たとえば、 と がある場合s1 == {'0': s2}、s2 == {'0': s1}試行s1 == s2すると次の比較が行われ、再帰がどのように発生するかが示されます。

s1 == s2 --> s1['0'] == s2['0'] --> s2 == s1 --> s2['0'] == s1['0'] --> s1 == s2 --> ...

s1 in [s2]またはのような封じ込めテストs2 in [s1]でも、この等値比較が行われます。これが、 のコードで発生する理由current in fsm["accepting"]です。

この再帰の問題は、等値比較の代わりに ID 比較を使用することで回避できcurrent in fsm["accepting"]ます。次のように置き換えてください。

any(s is current for s in fsm["accepting"])

より良い解決策は、状態がオブジェクト自体ではなく識別子を参照するようにして、循環参照を使用しないことです。たとえば、次のような構造を持つことができます。

states = {"s1": {"0": "s2", "1": "s1"},
          "s2": {"0": "s1", "1": "s2"}}
machine = {"start": "s1", "accepting": ["s1"]}

def recognize(fsm, in_string):
    return do_recognize(fsm, fsm["start"], in_string)

def do_recognize(fsm, current, in_string):
    if len(in_string) == 0:
        return current in fsm["accepting"]
    return do_recognize(fsm, states[current][in_string[0]], in_string[1:])
于 2012-11-28T16:49:47.887 に答える