18

単純な要件があります。 type のマップが必要です。ただし、理論的に可能な最速の検索時間が必要です。

マップと、tr1 から新しく提案された unordered_map の両方を使用しました。少なくとも、ファイルを解析してマップを作成しているときに、要素を一度に挿入することでそれを発見しました。

unordered_map には 5 分かかりましたが、map には 2 分しかかかりませんでした。

これは Hadoop クラスターで実行されるコードの一部になり、最大 1 億のエントリが含まれるため、可能な限り短い取得時間が必要です。

また、別の役立つ情報: 現在、挿入されているデータ (キー) は、1、2、... から 1,000 万までの整数の範囲です。

上記のように最大値を指定して順序を使用するようにユーザーに強制することもできますが、それは私の実装に大きな影響を与えますか? (マップは rb ツリーに基づいており、昇順で挿入するとパフォーマンスが向上する (または最悪の場合) と聞きました)

ここにコードがあります 

map<int,int> Label // this is being changed to unordered_map  
fstream LabelFile("Labels.txt");  


// Creating the map from the Label.txt  
if (LabelFile.is_open())  
{  
    while (! LabelFile.eof() )  
    {             
        getline (LabelFile,inputLine);  
        try  
        {  
            curnode=inputLine.substr(0,inputLine.find_first_of("\t"));  
            nodelabel=inputLine.substr(inputLine.find_first_of("\t")+1,inputLine.size()-1);  
            Label[atoi(curnode.c_str())]=atoi(nodelabel.c_str());  
        }  
        catch(char* strerr)  
        {  
            failed=true;  
            break;  
        }  
    }  
    LabelFile.close(); 
}

暫定的な解決策: コメントと回答を確認した後、実装では密なキーが使用されるため、動的 C++ 配列が最適なオプションになると思います。ありがとう

4

3 に答える 3

10

unordered_map の挿入はO(1)で、取得はおおよそO(1)である必要があります (基本的にはハッシュ テーブルです)。

結果としてのタイミングがOFFになるか、実装または unordered_map の使用に問題があります。

さらに情報を提供する必要があり、場合によってはコンテナの使用方法も提供する必要があります。

n1836 のセクション 6.3 に従って、挿入/取得の複雑さが与えられます。

考慮すべき問題の 1 つは、1億以上のアイテムがあると言うように、実装で構造を継続的に再ハッシュする必要がある場合があることです。その場合、コンテナーをインスタンス化するときに、コンテナーに挿入される「一意の」要素の数について大まかな考えがある場合は、それをパラメーターとしてコンストラクターに渡すことができ、コンテナーはそれに応じてバケットでインスタンス化されます。適切なサイズのテーブル。

于 2010-02-28T06:10:46.583 に答える
2

unordered_map の読み込みに余分な時間がかかるのは、配列の動的なサイズ変更によるものです。サイズ変更スケジュールは、テーブルがその負荷係数を超えると、セルの数をそれぞれ 2 倍にすることです。したがって、空のテーブルから、データ テーブル全体の O(lg n) コピーが期待されます。これらの余分なコピーは、事前にハッシュ テーブルのサイズを変更することで排除できます。具体的には

Label.reserve(expected_number_of_entries / Label.max_load_factor());

max_load_factor で除算すると、ハッシュ テーブルが動作するために必要な空のセルが考慮されます。

于 2012-06-21T17:49:41.277 に答える
1

unordered_map (少なくともほとんどの実装では) は取得が高速ですが、マップに比べて挿入速度が比較的遅くなります。ツリーは通常、データがランダムに並べられているときに最高の状態になり、データが並べ替えられているときに最悪の状態になります (常にツリーの一方の端に挿入すると、リバランスの頻度が高くなります)。

総エントリ数が約 1,000 万であることを考えると、十分な大きさの配列を割り当てて、非常に高速なルックアップを取得できます。スラッシングを引き起こさない十分な物理メモリを想定していますが、最新の標準では大量のメモリではありません。

編集:はい、ベクトルは基本的に動的配列です。

Edit2:いくつかの問題を追加したコード。あなたwhile (! LabelFile.eof() )は壊れています。while (LabelFile >> inputdata)通常、代わりに次のようなことをしたいでしょう。また、データの読み取りがやや非効率的です。明らかに期待しているのは、タブで区切られた 2 つの数字です。その場合、ループを次のように記述します。

while (LabelFile >> node >> label)
    Label[node] = label;
于 2010-02-28T06:12:32.510 に答える