4

私はゲームを開発しています。ゲームオブジェクトを次のマップに保存します。

std::map<std::string, Object*> mObjects;

std::stringコードでさらに検索するオブジェクトのキー/名前です。次のようないくつかのオブジェクトを指すのは非常に簡単ですmObjects["Player"] = ...。しかし、そのマップでの各検索でstd :: stringが割り当てられるため、速度が低下するのではないかと思います。そこでint、そのマップのキーとして使用することにしました。

最初の質問：それは本当に速いのでしょうか？

次に、アクセスしている現在のタイプのオブジェクトを削除したくないので、crc文字列計算をキーとして格納する方法を見つけました。例えば：

Object *getObject(std::string &key)
{
   int checksum = GetCrc32(key);
   return mObjects[checksum];
}

Object *temp = getOject("Player");

それともこれは悪い考えですか？計算crcには。を使用しますboost::crc。または、これは悪い考えであり、チェックサムの計算は、キータイプを使用してマップを検索するよりもはるかに遅くなりますstd::stringか？

4

4 に答える 4

6

CRCの計算は、文字列の単一の比較よりも確実に遅くなりますが、キーを見つける前にlog2N比較（たとえば、1000キーに対して10回の比較）を行うことが期待できるため、のサイズによって異なりますmap。CRCは衝突を引き起こす可能性もあるため、エラーが発生しやすくなります（衝突は比較的簡単に検出でき、とにかく正しい結果を得るために処理することもできますが、正しく行うには非常に注意する必要があります）。

unordered_map<>C ++環境で提供されている場合は（おそらく呼ばれる）を試すことができhash_mapます。高速である場合とそうでない場合がありますが、反復するとソートされません。ハッシュマップはさらに別の妥協案です。

  • ハッシュする時間はおそらくCRCの時間と似ていますが、
  • その後、法線マップで二分木ウォークを実行する代わりに、値を直接シークできることがよくあります。
  • 衝突を処理するためのロジックを少し事前にバンドルします。

（愚かな点ですが、intを引き続き使用でき、連続している可能性がある場合は、ルックアップをはるかに高速な配列に置き換えることができることを忘れないでください。整数が実際には連続していないが、特にスパースではない場合、スパースインデックスを使用できます。たとえば、1000個のパックされたレコードへのインデックスである10000個の短い整数の配列）。

結論としては、十分に気を配って質問する場合は、これらの代替案を実装してベンチマークを行い、特定のアプリケーションで実際に最適なものを確認し、それらが実際に具体的な違いをもたらすかどうかを確認する必要があります。それらのいずれかが特定の状況で最良である可能性があり、それらを真剣に比較するのに十分気にしない場合、それは明らかにそれらのいずれかが実行することを意味します。

于 2011-04-08T09:58:09.337 に答える
3

実際のパフォーマンスについては、コードのプロファイルを作成して確認する必要があります。しかし、私はhash_mapを使いたくなるでしょう。これはC++標準ライブラリの一部ではありませんが、一般的な実装のほとんどがそれを提供します。それは非常に高速なルックアップを提供します。

于 2011-04-08T09:55:15.797 に答える
3

最初の質問：それは本当に速いのでしょうか？

はい-intを数回比較しているのに対し、任意の長さの文字列の潜在的に大きなマップを数回比較しています。

checksum: Or this is bad idea?

一意であるとは限りません。噛むのを待っているバグです。

私がすること：

複数のコレクションを使用し、型安全性を採用します。

// perhaps this simplifies things enough that t_player_id can be an int?
std::map<t_player_id, t_player> d_players;
std::map<t_ghoul_id, t_ghoul> d_ghouls;
std::map<t_carrot_id, t_carrot> d_carrots;

より高速な検索、より多くの型安全性。小さなコレクション。より小さな割り当て/サイズ変更....そして何度も...あなたのアプリが非常に些細なものであれば、これは問題ではありません。今後はこのアプローチを使用し、プロファイリング後に/既存のプログラムの必要に応じて調整してください。

幸運を

于 2011-04-08T10:01:58.927 に答える
1

本当に知りたい場合は、コードのプロファイルを作成し、関数getObjectにかかる時間を確認する必要があります。個人的には、valgrindとKCachegrindを使用して、UNIXシステムでデータのプロファイルとレンダリングを行っています。

idを使う方が速いと思います。文字列よりもintを比較する方が速いので...

于 2011-04-08T10:01:25.323 に答える