4

私はこのコードでそれらをテストしました(Visual Studio 2010 sp1上):

#include <ctime>
#include <iostream>
#include <map>
#include <unordered_map>
#include <hash_map>

int main()
{ 
    clock_t time;
    int LOOP = (1 << 16);
    std::map<int, int> my_map;
    std::unordered_map<int, int> map_unordered_map;
    std::hash_map<int, int> my_hash_map;

    time = clock();
    for (int i = 0; i != LOOP; ++i)
    {
        my_map[i] = i;
    }
    std::cout << "map: " << ((double)(clock() - time) / CLOCKS_PER_SEC) << std::endl;

    time = clock();
    for (int i = 0; i != LOOP; ++i)
    {
        map_unordered_map[i] = i;
    }
    std::cout << "unordered_map: " << ((double)(clock() - time) / CLOCKS_PER_SEC) << std::endl;

    time = clock();
    for (int i = 0; i != LOOP; ++i)
    {
        my_hash_map[i] = i;
    }
    std::cout << "hash_map: " << ((double)(clock() - time) / CLOCKS_PER_SEC) << std::endl;

    system("PAUSE");
    return EXIT_SUCCESS;
}

そして結果はとても奇妙です：

DEBUG: map: 0.289 unordered_map: 10.738 hash_map: 10.58 続行するには何かキーを押してください。. .

RELEASE: map: 0.101 unordered_map: 0.463 hash_map: 0.429 続行するには何かキーを押してください。. .

4

2 に答える 2

6
  1. 各マップに挿入しているのは65536アイテムのみです。これは、O（log N）とO（1）の差が全体を意味するほど大きくはありません。
  2. アイテムを挿入するだけで、後で検索することはありません。
  3. キーはすべて昇順で連続する整数です。マップが通常使用される方法に適合しません。

結論：これは、問題のデータ構造について多くを語る可能性は低いです。

于 2012-08-30T16:46:17.197 に答える
1

これは、アルゴリズムの償却コストと最悪ケースのコストの例です。

std::map は、O(logN) 挿入の複雑さを持つ赤黒ツリーを使用します。
std::hash_map は、O(1) の償却された挿入の複雑さを持つハッシュ テーブルを使用します。

ただし、テーブルのサイズを変更してテーブルを再ハッシュする必要がある場合、ハッシュ テーブルの最悪の場合の複雑さは O(N) になります。

あなたの場合、多くの再ハッシュを行うことになるため、ハッシュテーブルの挿入が最悪の場合にヒットし、ツリーの挿入が高速になります-O(N) > O(logN)。

十分な大きさのテーブルで hash_map を初期化すると、ハッシュ テーブルは最悪のケースにヒットすることはなく、ツリーよりも高速になります - O(1) < O(logN)。

于 2012-08-30T17:15:34.010 に答える