7

再帰的な構文解析を行っています。

現在、私は偽のスタックを持っており、有限状態マシンの状態を格納しているので、再帰的にドリルダウンするときに、現在の状態をプッシュし、再帰的なテキストの処理が終了した後でポップします。

次のような「状態ID」スタックを使用する方が高速でしょうか。

 int* stack = 0
 int top = 0;
 // ...
 // drill down bit
 if (stack == 0)
     stack = (int*)malloc(STACK_JUMP_SIZE);
 else if (top % STACK_JUMP_SIZE == 0)
     stack = (int*)realloc(stack, (top+STACK_JUMP_SIZE) * sizeof(int));
 stack[top++] = currentState;
 // ...
 // pop up later
 {currentState = stack[--top]; {
 if (top == 0) {
     free(stack);
     stack = 0;
 } else if ((top+1) % STACK_JUMP_SIZE == 0) {
     stack = (int*)realloc(stack, (top+1)*sizeof(int));
 }

または、物事を適切な関数に分割して、C++にスタックについて心配させる方が速いでしょうか。

（誰かが「それはCであり、C ++ではない」と言うことを知っているので、先制的に答えます。私のプログラムのc ++ですが、多くのcが含まれています）。

4

1 に答える 1

9

実装によって異なります。事前に言う方法はありません。関数呼び出しが安価なマシン（SPARCなど）では、関数スタックの方がおそらく高速ですが、ローカリゼーションなどの問題が発生します。（マシンスタックは、シミュレートされたスタックよりも多くの情報をスタックするため、より多くのスペースを必要とします。）私は物事を適切な再帰関数に分割し、これがボトルネックであることが判明した場合にのみ手動スタック管理を試みます。ただし...手動スタック管理には、エラー処理という1つの重要な利点があります。マシンスタックオーバーフローは未定義の動作です。nullポインタを返すmallocかrealloc返す場合、少なくともエラーをきれいに報告できます。

スタックをシミュレートする場合は、//ではなく、の使用を検討する必要がstd::vectorあります。例外が発生した場合に節約でき、少し速くなる可能性もあります。スタックサイズに上限を設定でき、それが不当に大きくない場合は、スタックをCスタイルの配列として宣言する方がさらに高速です。mallocreallocfree

于 2012-02-17T10:41:55.893 に答える