キータイプstd :: stringを使用してマップルックアップのパフォーマンスを向上させるにはどうすればよいですか？

StackOverflow https://stackoverflow.com/questions/256038

質問

std::map（VC ++実装）を使用していますが、マップのfindメソッドを介した検索には少し時間がかかります。

キータイプはstd::stringです。

マップのカスタムキー比較オーバーライドを使用して、このstring::size()ルックアップのパフォーマンスを向上させることはできますか？たとえば、<=> <！> lt; compareは、データを比較する前に単純な<=>比較を考慮しませんか？

比較を高速化する他のアイデアはありますか？

私の状況では、マップには常に<！> ltが含まれます。 15個の要素がありますが、ノンストップでクエリされており、パフォーマンスが重要です。使用できるより高速なデータ構造がありますか？

更新：マップにはファイルパスが含まれています。

Update2：マップの要素は頻繁に変更されています。

役に立ちましたか？

解決

まず、すべてのプロファイリングとDEBUGスイッチをオフにします。これらはSTLを非常に遅くする可能性があります。

それ以外の場合、問題の一部は、文字列の最初の80〜90％で文字列が同一である可能性があります。これはマップにとって必ずしも悪いことではありませんが、文字列の比較にとっては悪いことです。この場合、検索にさらに時間がかかる可能性があります。

たとえば、このコードでは、find（）は2、3の文字列比較を行う可能性がありますが、それぞれが<！> quot; david <！> quot;まで最初の文字を比較した後、最初の3文字を返しますチェックされます。したがって、呼び出しごとに最大5文字がチェックされます。

map<string,int> names;
names["larry"] = 1;
names["david"] = 2;
names["juanita"] = 3;

map<string,int>::iterator iter = names.find("daniel");

一方、次のコードでは、find（）はおそらく135文字以上をチェックします：

map<string,int> names;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/wilma"] = 1;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/fred"] = 2;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/barney"] = 3;

map<string,int>::iterator iter = names.find("/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/betty");

これは、各文字列の先頭が同じであるため、一致する文字列をより深く検索する必要があるためです。

比較のために比較のためにsize（）を使用しても、データセットが非常に小さいため、ここではあまり役に立ちません。 std :: mapは、その要素をバイナリ検索で検索できるようにソートされたままになります。 findを呼び出すたびに、ミスの場合は5回未満のストリング比較が行われ、ヒットの場合は平均2回の比較が行われます。ただし、データによって異なります。パス文字列のほとんどが異なる長さである場合、Mottiが説明しているようなサイズチェックは大いに役立ちます。

代替アルゴリズムを考える際に考慮すべきことは、何個の<！> quot; hits <！> quot;あなたが得る。ほとんどのfind（）呼び出しはend（）またはヒットを返しますか？ find（）のほとんどがend（）を返す（欠落する）場合、毎回マップ全体を検索しています（2logn文字列比較）。

Hash_mapは良いアイデアです。ヒットの検索時間が約半分に短縮されるはずです。ミスのために。

特に上記のコードのようにデータセットに共通の祖先がある場合、パス文字列の性質のためにカスタムアルゴリズムが必要になる場合があります。

考慮すべきもう1つの点は、検索文字列を取得する方法です。それらを再利用している場合、比較しやすいものにエンコードすることが役立つ場合があります。一度使用して破棄すると、おそらくこのエンコード手順は非常に高価になります。

文字列検索を最適化するために、ハフマンコーディングツリーのようなものを1回（かなり前に）使用しました。そのようなバイナリ文字列検索ツリーは、場合によってはより効率的かもしれませんが、あなたのような小さなセットにはかなり高価です。

最後に、代替のstd :: map実装を調べます。 VCのstlコードのパフォーマンスについて悪いことを聞いたことがあります。特にDEBUGライブラリーは、呼び出しごとにユーザーをチェックするのが悪いです。 StlPort は以前は優れた代替手段でしたが、数年前に試していません。 ブーストも大好きです。

他のヒント

As Even は、setで使用される演算子は<ではなく==であると述べました。

string.length内の文字列の順序を気にしない場合は、comp(a, b) == trueに、通常の less-than よりもパフォーマンスの良いカスタム比較子を渡すことができます。

たとえば、多くの文字列に同様の接頭辞が付いている場合（ただし長さは異なります）、文字列の長さでソートできます（comp(b, a) == trueは一定の速度であるため）。

その場合、よくある間違いに注意してください：

struct comp {
    bool operator()(const std::string& lhs, const std::string& rhs)
    {
        if (lhs.length() < rhs.length())
            return true;
        return lhs < rhs;
    }
};

この演算子は厳密な弱い順序を維持しません。それぞれより小さい。

string a = "z";
string b = "aa";

ロジックに従うと、<=>および<=>が表示されます。

正しい実装は次のとおりです。

struct comp {
    bool operator()(const std::string& lhs, const std::string& rhs)
    {
        if (lhs.length() != rhs.length())
            return lhs.length() < rhs.length();
        return lhs < rhs;
    }
};

最初にできることはhash_mapを使用することです-標準の文字列比較では最初にサイズをチェックしません（辞書式に比較するため）避けるほうが良い。あなたの質問から、範囲を繰り返す必要はないようです。その場合、マップにはhash_mapにはないものがあります。

また、マップにあるキーの種類にも依存します。それらは通常非常に長いですか？また、<！> quot;やや遅い<！> quot;平均？コードのプロファイルを作成していない場合、別の部分に時間がかかっている可能性があります。

更新：うーん、プログラムのボトルネックはmap :: findですが、マップの要素は常に15未満です。これは、この小さな地図での検索が遅くなるべきではないため、プロファイルが何らかの形で誤解を招く可能性があると疑っています。実際、map :: findは非常に高速である必要があります。プロファイリングのオーバーヘッドは、find呼び出し自体よりも大きい場合があります。もう一度質問する必要がありますが、これが本当にあなたのプログラムのボトルネックですか？文字列はパスであると言いますが、このループではOS呼び出し、ファイルシステムアクセス、ディスクアクセスを一切行っていませんか？それらはどれも、map :: findが小さな地図よりもはるかに遅いはずです。実際、文字列を取得する方法はmap :: findよりも遅いはずです。

ソートされたベクターの使用を試みることができます（ここに1つのサンプルがあります） 、これはより高速になることがあります（必ず確認してください）。

より速くなると思う理由：

  1. 少ないメモリ割り当てと割り当て解除（ベクトルは使用される最大サイズに拡張され、解放されたメモリを再利用します）。
  2. ランダムアクセスを使用したバイナリ検索は、ツリートラバーサルよりも高速である必要があります（特にデータの局所性による）。

遅くなると思う理由：

  1. 削除と追加は、stringのswapが効率的であり、データセットのサイズが小さいため、メモリ内で文字列を移動することを意味します。これは問題ではない可能性があります。

std :: mapのコンパレーターはstd :: equal_toではなくstd :: lessで、<！> lt;を短絡させる最善の方法はわかりません。組み込みのものよりも速くなるように比較してください。

常に<！> ltがある場合; 15要素、おそらくstd :: string以外のキーを使用できますか？

Mottiには良い解決策があります。ただし、<！> lt;マップのオーバーヘッドは常に適切なハッシュスキームを備えた単純なルックアップテーブルのオーバーヘッドよりも大きいため、マップは正しい方法ではありません。あなたの場合、長さだけでハッシュするだけでも十分かもしれません。それでも衝突が発生する場合は、同じ長さのすべてのエントリで線形検索を使用してください。

自分が正しいかどうかを確認するには、もちろんベンチマークが必要ですが、その結果は確かです。

文字列のハッシュを事前計算し、それをマップに保存することを検討できます。そうすることで、std :: mapツリーでの検索中に文字列比較ではなくハッシュ比較の利点が得られます。

class HashedString
{
  unsigned m_hash;
  std::string m_string;

public:
  HashedString(const std::string& str)
    : m_hash(HashString(str))
    , m_string(str)
  {};
  // ... copy constructor and etc...

  unsigned GetHash() const {return m_hash;}
  const std::string& GetString() const {return m_string;}
};

これには、構築時に文字列のハッシュを一度計算するという利点があります。この後、比較関数を実装できます：

struct comp
{
  bool operator()(const HashedString& lhs, const HashedString& rhs)
  {
    if(lhs.GetHash() < rhs.GetHash()) return true;
    if(lhs.GetHash() > rhs.GetHash()) return false;
    return lhs.GetString() < rhs.GetString();
  }
};

ハッシュはHashedString構成で計算されるようになったため、std :: mapにそのように格納されるため、比較は天文学的に高い割合で非常に迅速に（整数比較）発生し、フォールバックしますハッシュが等しいときに標準文字列で比較します。

おそらく、文字列をマップのキーとして使用する前に逆にすることができますか？これは、各文字列の最初の数文字が同じ場合に役立ちます。

検討できるいくつかの事項を次に示します。

0）これがパフォーマンスのボトルネックであると確信していますか？ Quantify、Cachegrind、gprofなどの結果と同様ですか？そのようなsmapマップでの検索はかなり高速である必要があるため...

1）std :: map <！> lt; <！> gt;のキーの比較に使用されるファンクターをオーバーライドできます。これを行うための2番目のテンプレートパラメーターがあります。ただし、operator <！> lt;よりもはるかに良い結果が得られるとは思いません。

2）マップの内容は大きく変化していますか？そうではなく、マップのサイズが非常に小さい場合、ソートされたベクトルとバイナリ検索を使用すると、より良い結果が得られる可能性があります（たとえば、メモリの局所性をよりうまく活用できるためです）。

3）コンパイル時に要素は既知ですか？その場合、完全なハッシュ関数を使用してルックアップ時間を改善できます。ウェブでgperfを検索します。

4）何も見つけられないルックアップがたくさんありますか？その場合、コレクション内の最初と最後の要素と比較することで、毎回の完全検索よりも多くの不一致を迅速に解消できる可能性があります。

これらはすでに提案されていますが、詳細は次のとおりです。

5）文字列が非常に少ないため、別のキーを使用できます。たとえば、鍵はすべて同じサイズですか？文字の固定長配列を含むクラスを使用できますか？文字列を数字または数字のみのデータ構造に変換できますか？

使用例に応じて、使用できる他のテクニックがいくつかあります。たとえば、100万を超えるさまざまなファイルパスに対応する必要があるアプリケーションがありました。問題は、これらのファイルパスの小さなマップを保持する必要があるオブジェクトが何千もあったことです。

新しいファイルパスをデータセットに追加することはまれな操作であったため、パスがシステムに追加されたときにマスターマップが検索されました。パスが見つからなかった場合は追加され、新しいシーケンス整数（1から始まる）が返されました。パスが既に存在する場合、以前に割り当てられた整数が返されました。次に、各オブジェクトが保持する各マップは、文字列ベースのマップから整数マップに変換されました。これによりパフォーマンスが大幅に改善されただけでなく、文字列のコピーがあまり多くないため、メモリ使用量が削減されました。

もちろん、これは非常に具体的な最適化です。しかし、パフォーマンスの改善に関しては、特定の問題に合わせたソリューションを作成する必要があることがよくあります。

そして、私は文字列が嫌いです:)それらは比較するのが遅いわけではありませんが、高性能ソフトウェアのCPUキャッシュを本当に破壊する可能性があります。

std :: tr1 :: unordered_mapを試してください（ヘッダー<！> lt; tr1 / unordered_map <！> gt;にあります）。これはハッシュマップであり、要素の並べ替え順序は維持されませんが、通常のマップよりもはるかに高速です。

コンパイラがTR1をサポートしていない場合は、新しいバージョンを入手してください。 MSVCとgccは両方ともTR1をサポートし、他のほとんどのコンパイラの最新バージョンもサポートしていると思います。残念ながら、多くのライブラリリファレンスサイトは更新されていないため、TR1はほとんど不明な技術のままです。

C ++ 0xが同じ方法ではないことを願っています。

編集：tr1 :: unordered_mapのデフォルトのハッシュ方式はtr1 :: hashであることに注意してください。これはおそらくUDTで動作するように特化する必要があります。

長い共通部分文字列がある場合、トライはマップまたはhash_mapよりも優れたデータ構造である可能性があります。 <！> quot; might <！> quot;と言いましたが、hash_mapはすでにルックアップごとに1回だけキーをトラバースするため、かなり高速です。他の人がすでに持っているので、これ以上は説明しません。

一部のキーが他のキーよりも頻繁にルックアップされる場合、スプレイツリーを検討することもできますが、もちろんこれにより、最悪の場合のルックアップはバランスのとれたツリーよりも悪くなり、ルックアップは操作を変化させます。 'を使用しています読み取り/書き込みロック。

修正よりもルックアップのパフォーマンスを重視する場合、赤黒よりもAVLツリーの方がうまくいくかもしれません。これは、STL実装が一般的にマップに使用するものだと思います。通常、AVLツリーはバランスがとれているため、ルックアップごとの平均比較回数は少なくなりますが、差はわずかです。

あなたが満足しているこれらの実装を見つけることは問題かもしれません。 Boostのメインページを検索すると、それらにはスプレーとAVLツリーがあるが、トライはないことが示唆されます。

コメントで、何も見つからないルックアップがないことを述べました。したがって、理論的には15のツリーで最終的な比較をスキップできます<！> lt; 2 ^ 4要素を使用すると、他に何もせずに20〜25％の高速化を実現できます。実際、等しい文字列は比較が最も遅いため、それ以上の可能性があります。この最適化のためだけに独自のコンテナを作成する価値があるかどうかは、別の質問です。

参照の局所性も考慮する必要があります-キーとノードを小さなヒープから割り当てることで、時々ページのミスを回避できるかどうかわかりません。一度に約15エントリしか必要ない場合、ファイル名の制限を256バイト未満にすると、ルックアップ中にアクセスされるすべてが単一の4kページに収まることを保証できます（もちろん、検索されるキーは別として）。文字列を比較することは、数回のページ読み込みと比較して重要ではない可能性があります。ただし、これがボトルネックである場合は、膨大な数のルックアップが実行されている必要があるため、すべてが合理的にCPUに近いと思います。たぶんチェックする価値あり。

別の考え：多くの競合がある構造で悲観的なロックを使用している場合（コメントでプログラムが非常にマルチスレッドであると言った場合）、プロファイラーが何を伝えるか（CPUサイクルがどのコードであるか）で費やした場合、1コアに効果的に制限することで、考えている以上にコストがかかる可能性があります。リーダーライターロックをお試しください？

hash_mapは標準ではありません。tr1で使用可能なunordered_mapを使用してみてください（ツールチェーンにない場合はboostで使用可能です）。

vectorは通常ツリーとして実装されるため、少数の文字列の場合はmapを使用した方がよい場合があります。

代わりにハッシュテーブルを使用しませんか？ boost :: unordered_mapでできます。または、独自のソリューションを展開し、文字列自体の代わりに文字列のcrcを保存できます。または、さらに良いことに、文字列に#definesを付けて、ルックアップに使用します。たとえば、

#define "STRING_1" STRING_1
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top