为什么的hash_map和unordered_map我的机器是非常慢?(Why hash_map a

2019-09-21 23:53发布

我测试了他们与此代码(在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:地图:0.289 unordered_map:10.738的hash_map:10.58按任意键继续。 。 。

在发布:地图:0.101 unordered_map:0.463的hash_map:0.429按任意键继续。 。 。

Answer 1:

  1. 你只有在插入每个地图65536项 - 不是为O(log N)和O(1)之间的差异意味着一大堆足够大。
  2. 插入项目,没有做任何搜索之后。
  3. 你的钥匙是为了增加所有连续整数 - 不适合任何如何地图通常会被使用。

底线:这是不可能告诉你很多关于有问题的数据结构。



Answer 2:

这是摊销VS的算法的最坏情况下的成本的一个例子。

的std ::地图使用具有O(logN)的插入复杂红黑树。
的std ::的hash_map使用具有O(1)摊销插入复杂的哈希表。

然而,该哈希表具有O(N)的最坏情况的复杂性时,它具有以调整表以及重新表。

在你的情况,你最终做了很多老调重弹,所以哈希表的插入是打是最坏的情况,以至于树刀片变得更快 - O(N)> 0(10即)。

如果你的初始化用的hash_map一个足够大的表,则使用哈希表绝不会打它的最坏的情况下,它会更快然后树 - O(1)<O(logn)时间。



文章来源: Why hash_map and unordered_map on my machine are extremely slow?