(VC++ 実装)を使用してstd::mapいますが、マップの find メソッドを介したルックアップが少し遅くなります。
キーの種類はstd::string.
std::mapマップのカスタム キー比較オーバーライドを使用して、このルックアップのパフォーマンスを向上させることはできますか? たとえば、 < 比較は、データを比較する前にstd::string単純な比較を考慮していないのでしょうか?string::size()
比較をスピードアップするための他のアイデアはありますか？
私の状況では、マップには常に 15 未満の要素が含まれますが、ノンストップでクエリが実行されており、パフォーマンスが重要です。たぶん、私が使用できるより高速なデータ構造がありますか?
更新: マップにはファイル パスが含まれています。
Update2: マップの要素は頻繁に変更されます。
まず、すべてのプロファイリング スイッチと DEBUG スイッチをオフにします。これらはSTLを非常に遅くする可能性があります。
そうでない場合、文字列の最初の 80 ～ 90% が同一であることが問題の一部である可能性があります。これはマップにとって必ずしも悪いことではありませんが、文字列の比較には問題があります。この場合、検索に時間がかかる場合があります。
たとえば、このコードで find() を実行すると、文字列の比較が 2 回行われる可能性がありますが、それぞれが「david」までの最初の文字を比較した後に戻り、次に最初の 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 が説明するようなサイズ チェックが大いに役立ちます。
代替アルゴリズムを考えるときに考慮すべきことは、取得する「ヒット」の数です。ほとんどの find() 呼び出しは end() またはヒットを返しますか? ほとんどの find() が end() (ミス) を返す場合、毎回マップ全体を検索しています (2logn 文字列比較)。
Hash_map は良い考えです。ヒットの検索時間を約半分に短縮する必要があります。ミスのためにもっと。
パス文字列の性質上、特に上記のコードのようにデータ セットに共通の祖先がある場合は、カスタム アルゴリズムが必要になることがあります。
考慮すべきもう 1 つの点は、検索文字列を取得する方法です。それらを再利用している場合は、比較しやすいものにエンコードすると役立つ場合があります。それらを一度使用して破棄すると、このエンコード手順はおそらくコストがかかりすぎます。
文字列検索を最適化するために、ハフマン コーディング ツリーのようなものを 1 回 (かなり前に) 使用しました。そのようなバイナリ文字列検索ツリーは、場合によってはより効率的かもしれませんが、あなたのような小さなセットではかなり高価です.
最後に、代替の std::map 実装を調べます。VC の stl コードのパフォーマンスの一部について悪いことを聞いたことがあります。特に DEBUG ライブラリは、すべての呼び出しであなたをチェックするのが苦手です。 StlPortは良い代替手段でしたが、ここ数年は試していません。ブーストも昔から大好きです。
でも言ったように、 a で使用される演算子setは<not==です。
文字列の順序を気にしない場合は、通常のless-thansetよりもパフォーマンスの高いカスタム コンパレータを渡すことができます。set
たとえば、多くの文字列に同様のプレフィックスがある場合 (ただし、長さは異なります)、文字列の長さで並べ替えることができます (string.length速度が一定であるため)。
そうする場合は、よくある間違いに注意してください。
struct comp {
bool operator()(const std::string& lhs, const std::string& rhs)
{
if (lhs.length() < rhs.length())
return true;
return lhs < rhs;
}
};
この演算子は、厳密な弱い順序付けを維持しません。これは、2 つの文字列を互いに小さいものとして扱うことができるためです。
string a = "z";
string b = "aa";
ロジックに従うと、 と が表示されcomp(a, b) == trueますcomp(b, a) == true。
正しい実装は次のとおりです。
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 を使用してみてください。標準の文字列比較では最初にサイズがチェックされないのは正しいことですが (辞書式に比較するため)、独自のマップ コードを作成することは避けたほうがよいでしょう。 . あなたの質問から、範囲を反復する必要はないようです。その場合、 map には hash_map にないものはありません。
また、マップにあるキーの種類によっても異なります。彼らは通常非常に長いですか？また、「少し遅い」とはどういう意味ですか? コードのプロファイリングを行っていない場合は、別の部分に時間がかかっている可能性があります。
更新: うーん、プログラムのボトルネックは map::find ですが、マップの要素は常に 15 未満です。これは、プロファイルが何らかの形で誤解を招くのではないかと疑っています。なぜなら、この小さな地図での発見は決して遅くはないからです. 実際、 map::find は非常に高速である必要があり、プロファイリングのオーバーヘッドは find 呼び出し自体よりも大きくなる可能性があります。もう一度お聞きしたいのですが、これが本当にあなたのプログラムのボトルネックなのですか? 文字列はパスだと言いますが、このループでは、OS 呼び出し、ファイル システム アクセス、ディスク アクセスなどを行っていませんか? それらのいずれも、小さなマップで map::find よりも桁違いに遅くなるはずです。実際には、文字列を取得する方法は map::find よりも遅くなるはずです。
ソートされたベクトルを使用してみることができます (ここに 1 つのサンプルがあります)。
高速になると考える理由:
遅くなると考える理由:
stringの削除と追加は、メモリ内で文字列を移動することを意味しますswap。std::map のコンパレーターは std::equal_to ではありません。それは std::less です。< 比較を短絡して、組み込みのものよりも高速になるようにする最善の方法がわかりません。
要素が常に 15 個未満の場合、おそらく std::string 以外のキーを使用できますか?
モッティには良い解決策があります。ただし、15 個未満の要素の場合、適切なハッシュ スキームを使用した単純なルックアップ テーブルのオーバーヘッドよりも常にオーバーヘッドが大きくなるため、マップは正しい方法ではないと確信しています。あなたの場合、長さだけでハッシュするだけで十分かもしれません。それでも衝突が発生する場合は、同じ長さのすべてのエントリに対して線形検索を使用します。
私が正しいかどうかを確認するには、もちろんベンチマークが必要ですが、その結果については確信があります。
文字列のハッシュを事前に計算し、それをマップに保存することを検討してください。そうすることで、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;}
};
これには、構築時に文字列のハッシュを 1 回計算するという利点があります。この後、比較関数を実装できます。
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 にそのように格納されます。そのため、天文学的に高い割合で非常に迅速に比較 (整数比較) を行うことができます。ハッシュは等しいです。
文字列をマップのキーとして使用する前に、文字列を逆にすることはできますか? 各文字列の最初の数文字が同一である場合に役立ちます。
std::tr1::unordered_map を試してください (ヘッダー <tr1/unordered_map> にあります)。これはハッシュ マップであり、要素の並べ替え順序は維持されませんが、通常のマップよりもはるかに高速になる可能性があります。
コンパイラが TR1 をサポートしていない場合は、新しいバージョンを入手してください。MSVC と gcc はどちらも TR1 をサポートしており、他のほとんどのコンパイラの最新バージョンもサポートしていると思います。残念ながら、多くのライブラリ リファレンス サイトが更新されていないため、TR1 はほとんど知られていないテクノロジのままです。
C++0x が同じ方法でないことを願っています。
編集: tr1::unordered_map のデフォルトのハッシュ方法は tr1::hash であることに注意してください。これはおそらく UDT で動作するように特化する必要があります。
共通部分文字列が長い場合、マップや hash_map よりもトライの方が優れたデータ構造である可能性があります。ただし、「可能性がある」とは言いましたが、hash_map はすでにルックアップごとに 1 回しかキーをトラバースしないため、かなり高速になるはずです。他の人がすでに話しているので、これ以上説明しません。
一部のキーが他のキーよりも頻繁に検索される場合は、スプレイ ツリーを検討することもできますが、もちろん、これにより最悪の場合の検索はバランスの取れたツリーよりも悪くなります。たとえば、リーダー/ライター ロック。
変更よりもルックアップのパフォーマンスに関心がある場合は、赤黒よりも AVL ツリーの方が適している可能性があります。これは、STL 実装が一般的にマップに使用するものだと思います。通常、AVL ツリーはよりバランスが取れているため、ルックアップごとに必要な比較は平均して少なくなりますが、その差はごくわずかです。
あなたが満足しているこれらの実装を見つけることは問題かもしれません. Boost のメイン ページを検索すると、splay と AVL のツリーはあるが、トライはないことがわかります。
あなたはコメントで、何も見つからないルックアップは決してないと述べました。したがって、理論的には最終比較をスキップできます。これにより、15 < 2^4 要素のツリーでは、他に何もせずに 20 ～ 25% の速度向上が得られます。実際には、等しい文字列は比較が最も遅いため、それ以上になる可能性があります。この最適化のためだけに独自のコンテナーを作成する価値があるかどうかは、別の問題です。
また、参照の局所性を考慮することもできます。小さなヒープからキーとノードを割り当てることで、時折発生するページ ミスを回避できるかどうかはわかりません。一度に約 15 エントリしか必要としない場合、ファイル名の制限が 256 バイト未満であると仮定すると、ルックアップ中にアクセスされるすべてのものが単一の 4k ページに収まるようにすることができます (もちろん、ルックアップされるキーは別として)。文字列の比較は、数回のページ読み込みに比べれば重要ではないかもしれません。ただし、これがボトルネックである場合は、膨大な数のルックアップが行われているに違いないため、すべてが CPU にかなり近いと思います。たぶん、チェックする価値があります。
別の考え: 多くの競合がある構造で悲観的ロックを使用している場合 (コメントで、プログラムは大規模なマルチスレッドであると述べました)、プロファイラーが何を伝えようとも (CPU サイクルが費やされているコード) 、事実上 1 つのコアに制限することで、思ったよりも多くのコストがかかる可能性があります。リーダー/ライター ロックを試しますか?
考慮できる事項を次に示します。
0) これがパフォーマンスのボトルネックであると確信していますか? Quantify、Cachegrind、gprof などの結果が好きですか? そのような smap マップでのルックアップはかなり高速である必要があるため...
1) std::map<> でキーを比較するために使用されるファンクターをオーバーライドできます。それを行うための 2 番目のテンプレート パラメーターがあります。ただし、operator< よりもはるかに優れているとは思えません。
2) マップの内容は大きく変化していますか? そうでない場合、マップのサイズが非常に小さい場合、ソートされたベクトルとバイナリ検索を使用すると、より良い結果が得られる可能性があります (たとえば、メモリの局所性をより適切に活用できるため)。
3) 要素はコンパイル時に認識されていますか? その場合は、完全なハッシュ関数を使用してルックアップ時間を改善できます。Web で gperf を検索します。
4) 何も見つからないルックアップがたくさんありますか? もしそうなら、おそらくコレクションの最初と最後の要素を比較することで、毎回完全な検索を行うよりも多くの不一致を迅速に排除できるかもしれません。
これらはすでに提案されていますが、より詳細には次のとおりです。
5) 文字列が少ないので、別のキーを使用できます。たとえば、キーはすべて同じサイズですか? 文字の固定長配列を含むクラスを使用できますか? 文字列を数値または数値のみのデータ構造に変換できますか?
使用例に応じて、使用できる他の手法がいくつかあります。たとえば、100 万を超えるさまざまなファイル パスに対応する必要があるアプリケーションがありました。これらのファイル パスの小さなマップを保持する必要があるオブジェクトが何千もあるという問題がありました。
新しいファイル パスをデータ セットに追加する操作はめったに行われないため、パスがシステムに追加されると、マスター マップが検索されました。パスが見つからない場合は、パスが追加され、新しいシーケンス整数 (1 から始まる) が返されます。パスが既に存在する場合は、以前に割り当てられた整数が返されました。次に、各オブジェクトによって維持される各マップが、文字列ベースのマップから整数マップに変換されました。これにより、パフォーマンスが大幅に向上しただけでなく、文字列の重複コピーがあまりないため、メモリ使用量が削減されました。
確かに、これは非常に具体的な最適化です。しかし、パフォーマンスの向上に関して言えば、特定の問題に合わせたソリューションを作成しなければならないことがよくあります。
そして、私は文字列が嫌いです:) 比較するのが遅いわけではありませんが、高性能ソフトウェアのCPUキャッシュを本当に破壊する可能性があります.
hash_mapは標準ではありませんunordered_map。tr1 で利用可能 (ツール チェーンにない場合は boost で利用可能) を使用してみてください。
文字列の数が少ない場合は、通常はツリーとして実装されるため、vectorを使用したほうがよい場合があります。map
代わりにハッシュテーブルを使用しないのはなぜですか? boost::unordered_map できます。または、独自のソリューションを展開して、文字列自体の代わりに文字列の crc を保存することもできます。または、さらに良いことに、文字列に #defines を配置し、それらをルックアップに使用します。
#define "STRING_1" STRING_1