大規模な数式 (数百万ノード) に対応する式グラフに共通部分式消去 (CSE) を実装することを検討しています。
これを実行するのに適したアルゴリズムは何ですか? 簡単に実装できるアルゴリズムをインターネットで検索していましたが、何も見つかりませんでした。可能であれば、アルゴリズムは、完全な式グラフのノード数で線形複雑性を持つ必要があります。
質問する
4524 次
1 に答える
10
これらは副作用のない表現ですか？次に、最も簡単な方法は、各部分式のツリーをバケットにハッシュして、部分式除去の候補を決定することです。これは、すべての式が単一の（巨大な）「基本ブロック」にあるCSEの特殊なケースです。（私はこのアイデアを重複コードを検出するための基礎として使用します。）
式に順序と副作用がある場合は、値の番号付けを検討することをお勧めします。
于 2012-07-04T10:50:33.023 に答える