-1

Web サーバー用のセッション ストアを実装しています。キーは文字列で、格納されたオブジェクトはポインターです。map を使用してみましたが、もっと速いものが必要です。挿入よりも 5 ～ 20 倍頻繁にオブジェクトを検索します。

hash-map を使用しようとしましたが、失敗しました。自由時間よりも制約が多いように感じました。

Linux で c/c++ をコーディングしています。私のWebサーバーはboostよりも長持ちするので、boostにコミットしたくありません。:)

ハードウェア (SSD ディスク) は急速に変化しているため、これは非常に重要な質問です。正しい解決策は2年後にはありません。

4

3 に答える 3

5

私は を提案するつもりでしたがmap、あなたはすでにこれを除外しているようです。

map を使用してみましたが、もっと速いものが必要です。

これらは、ウィキペディアのページの好意による std::map パフォーマンスの境界です。

  • 要素の検索には O(log n) 時間がかかります
  • 新しい要素の挿入には O(log n) 時間がかかります
  • イテレータのインクリメント/デクリメントには O(log n) 時間がかかります
  • マップのすべての要素を反復処理するには O(n) 時間かかります
  • 単一のマップ要素を削除するには、O(log n) 時間かかります
  • マップ全体をコピーするには、O(n log n) 時間かかります。

マップが十分に最適化されていないことをどのように測定し、判断しましたか? あなたが見ているボトルネックがコードの他の部分にある可能性は十分にあり、 amapは完全に適切です。

上記の境界は、最も厳しいスケーラビリティ要件を除いて、すべてに適合するように思われます。

于 2009-05-08T04:58:37.013 に答える
2

使用されるデータ構造のタイプは、アクセスするデータによって決まります。あなたが尋ねるべきいくつかの質問：

  1. セッションストアにはいくつのアイテムがありますか? 50? 100000? 10000000000?
  2. ストア内の各アイテムのサイズ (バイト サイズ) は?
  3. キーにはどのような文字列入力が使用されますか? アスキー-7? UTF-8? UCS2? ...

一般に、ハッシュ テーブルはルックアップに非常に適しています。自分で作成することで、速度を大幅に最適化できます（もちろん、テーブルのサイズを変更できます）。ハッシュ テーブルを使用してパフォーマンスを向上させるための提案:

  1. 適切なハッシュ関数を選択してください! これはできればハッシュ テーブル間で均等に分散され、計算に時間がかかりません (これはキー入力の形式によって異なります)。
  2. バケットを使用している場合は、長さが 6 を超えないようにしてください。バケットが 6 を超えた場合は、ハッシュ関数が十分に均等に分散されていない可能性があります。3 未満のバケット長が推奨されます。
  3. オブジェクトの割り当て方法に注意してください。可能であれば、参照の局所性を利用するために、メモリ内でそれらを互いに近くに割り当てるようにしてください。必要に応じて、独自のサブアロケーター/ヒープ マネージャーを記述します。また、アクセス速度を向上させるために、アライメントされた境界を維持します (アライメントはプロセッサ/バスに依存するため、特定のプロセッサ タイプをターゲットにするかどうかを決定する必要があります)。

BTree も非常に優れており、一般的に優れたパフォーマンスを発揮します。(誰かがここに btree に関する情報を挿入できます)。

保存しているデータを調べて、データができるだけ小さいことを確認することをお勧めします。必要に応じて、short、unsigned char、bit フィールドを使用します。構造体を割り当てると同時に、構造体の最後に文字列データを割り当てるなど、パフォーマンスを向上させる方法は他にもあります。すなわち

struct foo {
  int a;
  char my_string[0]; // allocate an instance of foo to be 
                     // sizeof(int) + sizeof(your string data) etc
}

独自の文字列比較ルーチンを実装すると、実際にはパフォーマンスが大幅に向上することもありますが、これは入力データによって異なります。

于 2009-05-08T05:08:52.837 に答える
1

自作も可能です。ただし、boost や std::tr1::unordered_map で問題が発生することはありません。

三項トライは、要素数が少ない場合、ハッシュ マップよりも高速な場合があります。

于 2009-05-08T04:56:59.280 に答える