7

学術的な目的で、次のようなユーザー入力式をプロットするアプリケーションを作成する必要があります。f（x）= 1 --exp（3 ^（5 * ln（cosx））+ x）

パーサーを作成するために私が選択したアプローチは、RPNの式をShunting-Yardアルゴリズムで変換し、「cos」などのプリミティブ関数を単項演算子として扱うことです。これは、上記の関数が次のような一連のトークンに変換されることを意味します。

1, x, cos, ln, 5, *,3, ^, exp, -

問題は、関数をプロットするために何度も評価する必要があるため、各入力値にスタック評価アルゴリズムを適用することは非常に非効率的であるということです。どうすればこれを解決できますか？RPNのアイデアを忘れる必要がありますか？

4

9 に答える 9

3

「LOTS 回」はいくらですか？100万？

どのような関数を入力できますか? それらは連続していると仮定できますか？

コードのパフォーマンスを測定してみましたか?

（すみません、質問から始めました！）

以下で簡単に説明する 2 つのアプローチのいずれか (または両方) を試すことができます (おそらく他にもたくさんあります)。

1) 解析ツリー。

解析ツリーを作成できます。次に、ほとんどのコンパイラが式を最適化するために行うこと、定数の折りたたみ、共通の部分式の削除 (共通の式の部分木をリンクして結果をキャッシュすることで実現できます) などを行います。

次に、遅延評価手法を使用して、サブツリー全体を回避できます。たとえば、木がある場合

    *
   / \
  A   B

A が 0 に評価される場合、結果が 0 であることがわかっているため、 B の評価を完全に避けることができます。RPN を使用すると、遅延評価を失うことになります。

2) 補間

関数が連続的であると仮定すると、 Polynomial Interpolationを使用して関数を高い精度で近似できます。このようにして、(選択した多項式の次数に基づいて) 関数の複雑な計算を数回実行し、残りの時間で高速な多項式計算を実行できます。

データの初期セットを作成するには、アプローチ 1 を使用するか、少数の値しか生成しないため、RPN の使用に固執することができます。

したがって、補間を使用すると、RPN を維持できます...

それが役立つことを願っています!

于 2010-02-10T21:07:10.090 に答える
2

なぜ車輪を再発明するのですか？代わりに、高速なスクリプト言語を使用してください。lua のようなものをコードに統合するのは、ほとんど時間がかからず、非常に高速です。

通常、式をバイト コンパイルできます。その結果、非常に高速に実行されるコードが得られます。単純な 1D グラフには十分な速度です。

lua は高速で、他のどのスクリプト言語よりも簡単に C/C++ と統合できるため、お勧めします。別の良いオプションはpythonですが、よく知られていますが、統合するのが難しいことがわかりました.

于 2010-02-10T22:37:28.503 に答える
1

解析ツリー（私は「ツリー」を大まかに使用します。あなたの場合は一連の操作です）を維持し、それに応じて入力変数にマークを付けてみませんか？（たとえば、入力x、y、zなどの場合、「x」に0を付けて最初の入力変数を示し、「y」に1を付けて2番目の入力変数を示します。）

このようにして、式を1回解析し、解析ツリーを保持し、入力の配列を取り込んで、解析ツリーを適用して評価することができます。

評価ステップ（解析ステップと比較して）のパフォーマンスの側面について心配している場合は、ベクトル化（入力のベクトルに解析ツリーを一度に適用する）に取り掛からない限り、それほどうまくいくとは思いません。または、操作を固定関数にハードコーディングします。

于 2010-02-10T19:56:48.390 に答える
1

私がしているのは、シャントアルゴリズムを使用してRPNを生成することです。次に、RPNをトークン化された形式に「コンパイル」します。この形式は、式を再解析せずに（解釈的に）繰り返し実行できます。

于 2010-02-10T22:45:36.653 に答える
1

Michael Anderson はLuaを提案しました。このタスクだけで Lua を試してみたい場合は、私のaeライブラリを参照してください。

于 2010-02-20T00:11:35.463 に答える
0

RPNの単純な解釈は、特に次のものが含まれているため、問題なく機能するはずです。

  • 、、、および（pow、ログを含む）cosなどの数学ライブラリ関数exp^

  • シンボルテーブルルックアップ

うまくいけば、シンボルテーブル（xのような変数を含む）は短くて単純です。

ライブラリ関数はおそらくあなたの最大の時間を取るでしょう、それであなたのインタプリタが不十分に書かれていない限り、それは問題ではありません。

ただし、本当にスピードを上げる必要がある場合は、式をCコードに変換し、コンパイルしてその場でdllにリンクし、ロードすることができます（約1秒かかります）。これに加えて、メモ化されたバージョンの数学関数を使用すると、最高のパフォーマンスが得られます。

PS構文解析の場合、構文はかなりバニラなので、単純な再帰下降パーサー（コードの約1ページ、操車場と同じO（n））で問題なく動作するはずです。実際、解析しながら結果を計算できる場合があり（数学関数がほとんどの時間を費やしている場合）、解析ツリーやRPNなどを気にする必要はありません。

于 2010-02-12T02:20:29.707 に答える
0

どういう意味で非効率？マシンタイムとプログラマータイムがあります。特定のレベルの複雑さで実行する必要がある速度の基準はありますか? 課題を終えて次の課題に進むことの方が重要ですか (完璧主義者は決して終わらないことがあります)?

これらのすべてのステップは、入力値ごとに発生する必要があります。はい、操作のリストをスキャンして少しクリーンアップするヒューリスティックを使用できます。はい、+、* などを高レベル関数として呼び出す代わりに、その一部をアセンブリにコンパイルできます。ベクトル化 (値のベクトルですべての + の次にすべての * などを実行する) を、一度に 1 つの値に対して手順全体を実行することと比較できます。しかし、あなたはする必要がありますか？

つまり、gnuplot や Mathematica で関数をプロットするとどうなると思いますか?

于 2010-02-10T20:11:01.353 に答える
0

この RPN ベースのライブラリは目的に役立つと思います: http://expressionoasis.vedantatree.com/

電卓プロジェクトの 1 つで使用しましたが、うまく機能します。小さくてシンプルですが、拡張可能です。

于 2010-10-29T18:37:10.707 に答える
0

最適化の 1 つは、スタックを値の配列に置き換え、各操作が 2 つ (または 1 つ) の場所からロードされ、3 番目の場所に保存される3 つのアドレス マシンとしてエバリュエーターを実装することです。これにより、非常にタイトなコードになる可能性があります。

struct Op {
  enum {
    add, sub, mul, div,
    cos, sin, tan,
   //....
  } op;
  int a, b, d;
}

void go(Op* ops, int n, float* v) {
  for(int i = 0; i < n; i++) {
    switch(ops[i].op) {
      case add: v[op[i].d] = v[op[i].a] + v[op[i].b]; break;
      case sub: v[op[i].d] = v[op[i].a] - v[op[i].b]; break;
      case mul: v[op[i].d] = v[op[i].a] * v[op[i].b]; break;
      case div: v[op[i].d] = v[op[i].a] / v[op[i].b]; break;
      //...
    }
  }
}

3 アドレスは一般化されているため、RPN から 3 アドレスへの変換は簡単です。

于 2010-10-30T02:03:59.237 に答える