が効率的に

Question

私は、文字列のマップを使用して動作しますC++で簡単なパーサを書いている静的なマップを生成すると、「ハンドラ」関数ポインタに「トリガー」、私の質問は、実装のほとんどの「静的」と効率的な方法であるものです地図へのアクセスとアクセス？

まず、メソッドを考えました。 Parser::add_handler、これはパーサーのマップにトリガ/ハンドラを追加しますが、私が知る限り、コンパイル時にデータが分かっている間はプログラムが実行されるたびに実行する必要があります。 （プラス側にあるが、それらは唯一各インスタンス化パーサに対して一度実行され、必要はないであろう。）

Iが仮想メソッドを使用して考え、例えばParser::get_handlersパーサーのハンドラーマップを返すために派生クラスで実装されます。これは、パーサのマップ生成関数への少なくとも1回の呼び出しで、パーサの作成されたすべてのインスタンスに対して仮想関数呼び出しを必要とするものの、よりうまくカプセル化されたソリューションのようです。

現時点では後者のアプローチが望ましいと思われますが、各実行時に動的に生成されるマップは残っていますが、これを回避するには離れていますか？あなたが動的にマップを構築したくない場合は

Answer 1

は、あなたが（log n）時間Oでそれを検索するstd::lower_boundでソートされた静的な配列を使用することができます。

あなたが利用できる良いハッシュマップの実装を持っている場合、あなたはそれを埋めるのオーバーヘッドはあなたがする必要がどのように多くのルックアップに応じて、実行時のパフォーマンスの向上よりも小さいことを見つけるかもしれません。

Answer 2

まず第一に、それは過度のように見えます。最適化する必要がないものを最適化するために時間を費やそうとしていますか？

関数名がすべてわかっていると、関数の数によって異なります。そのような方法で文字列ポインタの配列を作成して、ポインタをソートしてから手動検索を行うだけでも構いません。リストにいくつかの関数しかない場合、線形検索を行うことができます。多くの場合は、パフォーマンス上の理由から、バイナリ検索を手動で行います（ただし、ポインタはソート順に並べる必要があります）。

実際の作業では、決してstd :: mapを使用しないでください。あなたのケースに合わせて特別に設計されています。挿入は高価ですが、一度地図を作成すると検索は非常に高速です（バイナリ検索）。あなたはきれいな正しいコードを取得します。

Answer 3

超効率的にしたい場合は、普通の古いデータ構造としてparsing treeを作成します。これをうまくやりたい場合は、仕様（つまり、lex/flexがあなたのためにやっていること）から構文解析ツリーを生成するプログラムを作成し、結果として生成されたデータ構造をプログラムにコンパイルします。

コンパイル時にすべてのデータが追加されるため、add_handlerは必要ありません。言われていること

、あなたはおそらく、ほとんどのタスクのための最適化のこのレベルを必要としないので、私はいつも右の最初の機能を取得することをお勧めしますし、後でそのような方法を使用して最適化する方法を見てしまいます。

Answer 4

あなたは、コンパイル時にすべての文字列とそのハンドラを知っていると、実行時にそれらを一致させたい、とあなたは、文字列の多くの地獄を持っていない場合は、それらの長さは、範囲の場合は非常に長くはない、とした場合これらの文字列の可能な文字が巨大ではない（つまりASCIIのように）場合は、テンプレートを使用してコンパイル時に静的なディスパッチテーブルを構築するか、ハードコードするだけで自分自身を作成できます。この方法では、どのような種類の文字列とどれくらいの文字列があるかによって、パフォーマンスが低下する可能性があります。

また、キーがその文字列内の文字（数値表現）の合計である場合、文字列の長さごとに配列を持つことができます。

でも、Googleのdense_hash_mapから始めることをおすすめします。あなたのソフトウェアを早めに最適化するのにあまりにも多くの時間を費やさないでください。プログラムが完了し、パフォーマンスに満足できない場合は、プロファイラを使用してボトルネックがどこにあるかを見つけてパフォーマンスを向上させます。

幸運。

Answer 5

要件に基づいて興味深い解決策がたくさんあります。
より速いメソッドは、各トリガーの関数ポインタメンバーを持つクラスのテンプレートパーサーです。したがって、ランタイムオーバーヘッドはまったくありません。実際、インライン展開を可能にする唯一のソリューションです。 1つのクラスがすべてのハンドラを持つ必要があるという制限があります。

template<class handler> 
struct Parser { 
    void ParseLines() { 
     if (lineBeginsWith('+') 
      handler.lineBeginsPlus(); 
     if (lineBeginsWith('-') 
      handler.lineBeginsMinus(); 
    } 
}; 
struct LineHandlers { 
    void lineBeginsPlus() { 
     printf("handle + line"); 
    } 
    void lineBeginsMinus() { 
     printf("handle - line"); 
    } 
}; 
struct OtherLineHandlers { 
    void lineBeginsPlus() { 
     printf("handle + line differently"); 
    } 
    void lineBeginsMinus() { 
     printf("handle - line differently"); 
    } 
}; 
int main() { 
    Parser<LineHandlers> ParserInstance; 
    ParserInstance.ParseLines(); 
    Parser<OtherLineHandlers> OtherParserInstance; 
    OtherParserInstance.ParseLines(); 
}