5

文字列を保存し、それぞれに一意の ID 番号を発行したいと考えています (インデックスで問題ありません)。各文字列のコピーが 1 つだけ必要であり、迅速な検索が必要です。パフォーマンスの低下に気付くほど頻繁に文字列がテーブルに存在するかどうかを確認します。これに使用するのに最適なコンテナは何ですか?文字列が存在する場合、どのように検索しますか?

4

8 に答える 8

9

tr1::unordered_map をお勧めします。これはハッシュマップとして実装されるため、ルックアップの予想される複雑さは O(1) で、最悪の場合は O(n) になります。コンパイラが tr1 をサポートしていない場合は、boost の実装もあります。

#include <string>
#include <iostream>
#include <tr1/unordered_map>

using namespace std;

int main()
{
    tr1::unordered_map<string, int> table;

    table["One"] = 1;
    table["Two"] = 2;

    cout << "find(\"One\") == " << boolalpha << (table.find("One") != table.end()) << endl; 
    cout << "find(\"Three\") == " << boolalpha << (table.find("Three") != table.end()) << endl; 

    return 0;
}
于 2009-02-21T01:38:01.687 に答える
7

これを試して：

代替テキスト
(出典: adrinael.net )

于 2009-02-21T17:00:43.200 に答える
5

std::map を試してください。

于 2009-02-21T01:51:02.153 に答える
4

何よりもまず、選択肢を定量化できなければなりません。また、あなたが興味を持っている主な使用パターンは、挿入ではなくlookupであると教えてくれました。

Nをテーブルにあると予想される文字列の数にしC、上記のテーブル (またはテーブルに対してチェックされる文字列) に存在する任意の文字列の平均文字数を とします。

  1. ハッシュベースのアプローチの場合、ルックアップごとに次の費用がかかります。

    • O(C)- 検索しようとしている文字列のハッシュを計算する
    • O(1 x C)との間。はハッシュ キーに基づいてバケットをトラバースすることで予想されるコストです。ここでは を掛けてO(N x C)、ルックアップ キーに対して各文字列の文字を再チェックします。1..NC
    • 合計時間: ～のO(2 x C)間O((N + 1) x C)

  2. にstd::map基づくアプローチ(赤黒木を使用) の場合、ルックアップごとに次のコストを支払います。

    • 合計時間: ～の間O(1 x C)-O(log(N) x C)ここO(log(N))で、 は最大ツリー トラバーサル コストであり、O(C)はツリー トラバーサル中にルックアップ キーを再チェックするためにstd::map一般的な実装にかかる時間です。less<>

の値が大きくN、log(N) 未満の衝突を保証するハッシュ関数がない場合、または単に安全にプレイしたい場合は、ツリーベースの ( std::map) アプローチを使用することをお勧めします。N が小さい場合は、必ずハッシュベースのアプローチを使用してください (ハッシュの衝突が少ないことを確認しながら)。

ただし、決定を下す前に、次のことも確認する必要があります。

于 2009-02-21T04:03:14.723 に答える
2

インデックスが配列へのインデックスである場合、配列は問題なく機能するように聞こえます。存在するかどうかを確認するには、インデックスが配列の境界内にあり、そのエントリが NULL でないことを確認してください。

編集:リストを並べ替える場合は、高速検索が必要なバイナリ検索を常に使用できます。

編集: また、文字列を検索する場合は、いつでも astd::map<std::string, int>も使用できます。これにより、適切な検索速度が得られるはずです。

于 2009-02-21T01:38:34.647 に答える
2

検索する文字列は静的に利用できますか? 完全なハッシュ関数を見たいと思うかもしれません

于 2009-02-21T01:52:46.173 に答える
1

std::map を使用するのが最も簡単です。

それはこのように動作します：

#include <map>
using namespace std;

...

   map<string, int> myContainer;
   myContainer["foo"] = 5; // map string "foo" to id 5
   // Now check if "foo" has been added to the container:
   if (myContainer.find("foo") != myContainer.end())
   {
       // Yes!
       cout << "The ID of foo is " << myContainer["foo"];
   }
   // Let's get "foo" out of it
   myContainer.erase("foo")
于 2009-02-21T01:59:18.967 に答える
0

おそらくGoogleのスパースハッシュ

于 2009-02-21T16:56:21.277 に答える