27

プログラムのすべてのスポットを最適化すべきではないことを理解しているので、この質問は「学術的な」ものと考えてください。

私は最大100個の文字列とそれぞれの整数を持っています。

MSFT 1
DELL 2
HP   4
....
ABC  58

このセットは事前に初期化されているため、一度作成されると変更されることはありません。セットが初期化された後、私はそれをかなり集中的に使用するので、高速な検索ができると便利です。文字列はかなり短く、最大 30 文字です。マッピングintも制限されており、1 ～ 100 の間です。

少なくとも、文字列が事前に初期化され、決して変更されないことを知っていれば、「1 バスケット 1 アイテム」マッピングになるハッシュ関数を「見つける」ことができるはずですが、おそらく他のハックがあります。

私が想像できる1つの最適化-最初のシンボルのみを読み取ることができます。たとえば、「D」で始まる文字列が「DELL」だけで、「D***」のような文字列を受け取った場合、その文字列を読み取る必要さえありません。それは明らかに「DELL」です。このようなルックアップは、「ハッシュマップ ルックアップ」よりも大幅に高速でなければなりません。(ここでは、ハッシュのシンボルのみを受け取ると仮定しましたが、常にそうであるとは限りません)

私の問題に対して、すぐに使用できる、または簡単に実装できるソリューションはありますか? 私はc ++とブーストを使用しています。

更新チェックしたところ、ティッカーの交換制限は、上記の 30 シンボルではなく 12 シンボルであることがわかりました。ただし、他の取引所では少し長いシンボルが許可される場合があるため、最大 20 文字の長さのティッカーで動作し続けるアルゴリズムを持つことは興味深いことです。

4

7 に答える 7

38

ハッシュテーブル[1]は、原則として最速の方法です。

ただし、完全なドメインを事前に知っていれば、完全ハッシュ関数をコンパイルできます。

完全なハッシュを使用すると、衝突が発生する必要がないため、ハッシュ テーブルを線形配列に格納できます。

適切な微調整を行うと、次のことができます

  • すべてのハッシュ要素を限られたスペースに収め、直接アドレス指定を潜在的なオプションにする
  • O(1) で逆引きを行う

完全ハッシュ関数を生成するための「昔ながらの」ツールはgperf(1)です。ウィキペディアには、この件に関するより多くのリソースがリストされています。

すべての議論のために、私はデモを実行しました:

NASDAQ ティッカー シンボルをダウンロードし、そのセットから 100 個のランダム サンプルを取得し、次のように gperf を適用します。

gperf -e ' \015' -L C++ -7 -C -E -k '*,1,$' -m 100 selection > perfhash.cpp

のハッシュ値 MAX_HASH_VALUE157と、同じ数のアイテムの直接文字列ルックアップ テーブルが生成されます。デモンストレーション用のハッシュ関数を次に示します。

inline unsigned int Perfect_Hash::hash (register const char *str, register unsigned int len) {
  static const unsigned char asso_values[] = {
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156,  64,  40,   1,  62,   1,
       41,  18,  47,   0,   1,  11,  10,  57,  21,   7,
       14,  13,  24,   3,  33,  89,  11,   0,  19,   5,
       12,   0, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156
    };
  register int hval = len;

  switch (hval) {
      default: hval += asso_values[(unsigned char)str[4]];   /*FALLTHROUGH*/
      case 4:  hval += asso_values[(unsigned char)str[3]];   /*FALLTHROUGH*/
      case 3:  hval += asso_values[(unsigned char)str[2]+1]; /*FALLTHROUGH*/
      case 2:  hval += asso_values[(unsigned char)str[1]];   /*FALLTHROUGH*/
      case 1:  hval += asso_values[(unsigned char)str[0]];   break;
  }
  return hval;
}

それは実際にはそれほど効率的ではありません。github で完全なソースを見てください: https://gist.github.com/sehe/5433535

これも完全なハッシュであるため、衝突は発生しません。

Q. [...]明らかに「DELL」です。このようなルックアップは、「ハッシュマップ ルックアップ」よりも大幅に高速でなければなりません。

A:単純なものを使用するとstd::map、正味の効果はプレフィックス検索になります (最初の文字の不一致に対する辞書式文字列比較のショートカットのため)。ソートされたコンテナーでの二分探索についても同じことが言えます。

[1] 追伸。std::search100 個の文字列の場合、 orを使用した文字列の並べ替えられた配列は、Locality of Referencestd::lower_boundの改善により、潜在的に高速/高速になります。これが当てはまるかどうかを確認するには、プロファイルの結果を参照してください。

于 2013-04-22T07:02:15.830 に答える
19

sehe の投稿への小さな追加:

単純なものを使用するとstd::map、正味の効果はプレフィックス検索になります (最初の文字の不一致に対する辞書式文字列比較のショートカットのため)。ソートされたコンテナーでの二分探索についても同じことが言えます。

プレフィックス検索を利用して、はるかに効率的にすることができます。単純なバイナリ検索の両方の問題は、std::map個々の比較ごとに同じプレフィックスを冗長に読み取り、全体的な検索が O( m log n ) になることです。ここで、mは検索文字列の長さです。

これが、大規模なセットに対してハッシュマップがこれら 2 つの方法よりも優れている理由です。ただし、冗長なプレフィックス比較を実行しないデータ構造があり、実際には各プレフィックスを 1 回だけ比較する必要があります。より一般的にはtrieとして知られるプレフィックス (検索) ツリーで、長さmの単一の文字列を検索することが可能です。 O( m ) では、完全なハッシュを使用したハッシュ テーブルに対して得られるのと同じ漸近的なランタイムです。

完全なハッシュを使用したトライまたは (直接参照) ハッシュ テーブルのどちらが目的に対してより効率的であるかは、プロファイリングの問題です。

于 2013-04-22T08:06:40.210 に答える
0

文字列をバイナリ ツリーに格納して、そこで検索することもできます。これにはO(log n)理論上のパフォーマンスがありますが、実際には、非常に長く、最初の数文字がすでに異なるキーがいくつかある場合は、はるかに高速になる可能性があります。

つまり、ハッシュ関数を計算するよりもキーを比較する方が安価な場合です。

さらに、CPU キャッシュ効果などがあります。

ただし、かなり安価なハッシュ関数を使用すると、ハッシュ テーブルに勝るものはありません。

于 2013-04-22T07:02:25.323 に答える
-2

コンパイル時に文字列がわかっている場合は、列挙型を使用できます。

enum
{
  Str1,
  Str2
};

const char *Strings = {
  "Str1",
  "Str2"
};

いくつかのマクロ トリックを使用すると、(ファイル インクルードと を使用して) 2 つの場所でテーブルを再作成する冗長性を取り除くことができます#undef。

次に、配列にインデックスを付けるのと同じくらい速く検索を実行できます。

const char *string = Strings[Str1]; // set to "Str1"

これにより、最適なルックアップ時間と参照の局所性が得られます。

于 2013-04-22T07:09:49.107 に答える