1

問題は次のとおりです。

ユーザーが式を作成できるように、XPathのような言語をユーザーに提供する式評価エンジンを開発しました。次に、これらの式が解析され、式ツリーとして保存されます。論理（and / or / not）、リレーショナル（=、！=、>、<、> =、<=）、算術（+、-、*、/）、if / then /など、さまざまな種類の式があります。 else式。

これらの操作に加えて、式には定数（数値、文字列、日付など）を含めることができ、XPathと同様の構文を使用してJavaオブジェクトのツリー内を移動することにより、外部情報にアクセスすることもできます。

上記を前提として、次のような式を作成できます。

/some/value and /some/other/value

/some/value or /some/other/value

if (<evaluate some expression>) then 
    <evaluate some other expression> 
else 
    <do something else>

if-then-else式のthen-partとelse-partはそれ自体が式であり、すべてが式と見なされるため、他のif-then-elseを含め、何でもそこに表示でき、ユーザーはビルドできます。 if-then-elseをネストすることによる大きな決定木。

これらの式は手動で作成され、人為的エラーが発生しやすいため、一般的な外部データの分析に基づいて、これらの式ツリーを最適化できる自動学習プロセスを作成することにしました。例：上記の最初の式（/ some/valueおよび/some/ other / value）で、/ some / other / valueの結果がほとんどの場合falseである場合、このブランチが短絡評価を利用するための左側の分岐（左側はすでに結果を決定しているため、ANDの右側は評価されません）。

もう1つの可能な最適化は、ネストされたif-then-else式（決定木）を再配置することです。これにより、使用される最も一般的な外部データに基づいて最も頻繁に使用されるパスが、将来、一部のブランチの不要な評価を回避して、より早く実行されます。回数。

これらの式ツリーのこの自動リファクタリングを実行するために使用するのに最適または推奨されるアプローチ/アルゴリズムについて何かアイデアはありますか？

4

1 に答える 1

1

あなたが説明しているのはコンパイラの最適化だと思います。これは、

  • インライン展開
  • デッドコードの排除
  • 絶え間ない伝播
  • ループ変換

基本的に、コード/xpathの機能を維持することが保証されている多くの書き換えルールがあります。

ネストされた if-else の再配置に関する質問では、機械学習に頼る必要はないと思います。1 つの (最適だと思う) 方法は、リンクのハフマン コーディングを使用することです 。このツリーは、ハフマン ツリーを作成したのと同じ分布を持つ (十分な大きさの) サンプルで実行される評価が最も少なくなります。

「ある式を評価する」式に制限がある場合、または計算コストが異なる場合などは、おそらく別のアプローチが必要です。

そして、最適化に関してはいつものように注意して、本当に重要なことだけを行う必要があることを忘れないでください。

于 2013-01-06T11:12:47.563 に答える