为什么 unordered_map 和 map 具有相同的性能？

Question

这是我的代码，我的

unordered_map

和

map

的行为相同，并且执行时间相同。我是否遗漏了这些数据结构的某些内容？

更新：我根据以下答案和评论更改了我的代码。我删除了字符串操作以减少分析的影响。另外，现在我只测量

find()

，它在我的代码中占用了近 40% 的 CPU。配置文件显示

unordered_map

快了 3 倍，但是，还有其他方法可以使此代码更快吗？

#include <map>
#include <unordered_map>
#include <stdio.h>

struct Property {
    int a;
};

int main() {
    printf("Performance Summery:\n");
    static const unsigned long num_iter = 999999;
    
    std::unordered_map<int, Property > myumap;
    for (int i = 0; i < 10000; i++) {
        int ind = rand() % 1000;
        Property p;
        p.a = i;
        myumap.insert(std::pair<int, Property> (ind, p));
    }
    
    clock_t tStart = clock();
    for (int i = 0; i < num_iter; i++) {
        int ind = rand() % 1000;
        std::unordered_map<int, Property >::iterator itr = myumap.find(ind);
    }
    
    printf("Time taken unordered_map: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
    
    std::map<int, Property > mymap;
    for (int i = 0; i < 10000; i++) {
        int ind = rand() % 1000;
        Property p;
        p.a = i;
        mymap.insert(std::pair<int, Property> (ind, p));
    }
    
    tStart = clock();
    for (int i = 0; i < num_iter; i++) {
        int ind = rand() % 1000;
        std::map<int, Property >::iterator itr = mymap.find(ind);
    }
    
    printf("Time taken map: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
}

输出在这里

Performance Summary:
Time taken unordered_map: 0.12s
Time taken map: 0.36s

Answer 1

在不深入你的代码的情况下，我会做一些一般性评论。

1. 您到底在测量什么？您的分析包括填充和扫描数据结构。考虑到（大概）填充有序映射需要更长的时间，测量这两者都违背了有序映射的增益（或其他）的想法。弄清楚您正在测量什么，然后进行测量。
2. 代码中还有很多可能与您正在分析的内容相关的内容：有大量对象创建、字符串连接等。这可能是您实际测量的内容。仅专注于分析您想要测量的内容（请参阅第 1 点）。
3. 10,000 例太小了。在这种规模下，其他考虑因素可能会压倒您所测量的内容，尤其是当您测量所有内容时。

Answer 2

我们喜欢获得“最少、完整且可验证”的示例是有原因的。这是我的代码：

#include <map>
#include <unordered_map>
#include <stdio.h>

struct Property {
    int a;
};

static const unsigned long num_iter = 100000;
int main() {
    printf("Performance Summery:\n");
    clock_t tStart = clock();
    std::unordered_map<int, Property> myumap;

    for (int i = 0; i < num_iter; i++) {
        int ind = rand() % 1000;
        Property p;
        //p.fileName = "hello" + to_string(i) + "world!";
        p.a = i;
        myumap.insert(std::pair<int, Property> (ind, p));
    }

    for (int i = 0; i < num_iter; i++) {
        int ind = rand() % 1000;
        myumap.find(ind);
    }

    printf("Time taken unordered_map: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);

    tStart = clock();
    std::map<int, Property> mymap;

    for (int i = 0; i < num_iter; i++) {
        int ind = rand() % 1000;
        Property p;
        //p.fileName = "hello" + to_string(i) + "world!";
        p.a = i;
        mymap.insert(std::pair<int, Property> (ind, p));
    }

    for (int i = 0; i < num_iter; i++) {
        int ind = rand() % 1000;
        mymap.find(ind);
    }

    printf("Time taken map: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
}

运行时间为：

Performance Summery:
Time taken unordered_map: 0.04s
Time taken map: 0.07s

请注意，我运行的迭代次数是您运行的迭代次数的 10 倍。

我怀疑你的版本有两个问题。首先是您运行的迭代太少，无法产生影响。第二个是您在计数循环内执行昂贵的字符串操作。运行字符串操作所需的时间大于使用无序映射节省的时间，因此您看不到性能差异。

Answer 3

std::map

) 还是哈希映射 (

std::unordered_map

) 更快实际上取决于条目数量和键的特征（值的可变性、比较和哈希函数等）但是

理论上

，树比哈希映射慢，因为在二叉树中插入和搜索是O(log2(N))复杂度，而在哈希映射中插入和搜索是大致O (1) 复杂性。 您的测试未显示它，因为：

您循环调用
1. rand()

   。与地图插入相比，这需要很长时间。它会为您正在测试的两张地图生成不同的值，从而进一步扭曲结果。使用重量较轻的发电机，例如

   minstd

   LCG。

您需要更高分辨率的时钟和更多的迭代，以便每次测试运行至少需要
2. 几百毫秒

   。

您需要确保编译器不会
3. 重新排序您的代码

   ，以便定时调用发生在它们应该发生的地方。这并不总是那么容易。围绕定时测试的内存栅栏通常有助于解决这个问题。

您的
4. find()

   调用很有可能被优化掉，因为您没有使用它们的值（我只是碰巧知道至少 -O2 模式下的 GCC 不会这样做，所以我将其保留原样） .

相比之下，字符串连接也非常慢。
这是我的更新版本：

#include <atomic>
#include <chrono>
#include <iostream>
#include <map>
#include <random>
#include <string>
#include <unordered_map>

using namespace std;
using namespace std::chrono;

struct Property {
  string fileName;
};

const int nIter = 1000000;

template<typename MAP_TYPE>
long testMap() {
  std::minstd_rand rnd(12345);
  std::uniform_int_distribution<int> testDist(0, 1000);
  auto tm1 = high_resolution_clock::now();
  atomic_thread_fence(memory_order_seq_cst);
  MAP_TYPE mymap;

  for (int i = 0; i < nIter; i++) {
    int ind = testDist(rnd);
    Property p;
    p.fileName = "hello" + to_string(i) + "world!";
    mymap.insert(pair<int, Property>(ind, p));
  }
  atomic_thread_fence(memory_order_seq_cst);

  for (int i = 0; i < nIter; i++) {
    int ind = testDist(rnd);
    mymap.find(ind);
  }

  atomic_thread_fence(memory_order_seq_cst);
  auto tm2 = high_resolution_clock::now();
  return (long)duration_cast<milliseconds>(tm2 - tm1).count();
}

int main()
{
  printf("Performance Summary:\n");
  printf("Time taken unordered_map: %ldms\n", testMap<unordered_map<int, Property>>());
  printf("Time taken map: %ldms\n", testMap<map<int, Property>>());
}

用

-O2

编译，给出以下结果：

Performance Summary:
Time taken unordered_map: 348ms
Time taken map: 450ms

因此，在

这种特殊情况

中使用

unordered_map

会快约 20-25%。

Answer 4

我做了一些修改：

增加样本量

1. 两张地图现在都使用相同的随机数序列。
-

#include <map>
#include <unordered_map>
#include <vector>
#include <stdio.h>

struct Property {
    int a;
};

struct make_property : std::vector<int>::const_iterator
{
    using base_class = std::vector<int>::const_iterator;
    using value_type = std::pair<const base_class::value_type, Property>;
    using base_class::base_class;

    decltype(auto) get() const {
        return base_class::operator*();
    }

    value_type operator*() const
    {
        return std::pair<const int, Property>(get(), Property());
    }
};

int main() {
    printf("Performance Summary:\n");
    static const unsigned long num_iter = 9999999;

    std::vector<int> keys;
    keys.reserve(num_iter);
    std::generate_n(std::back_inserter(keys), num_iter, [](){ return rand() / 10000; });


    auto time = [](const char* message, auto&& func)
    {
        clock_t tStart = clock();
        func();
        clock_t tEnd = clock();
        printf("%s: %.2gs\n", message, double(tEnd - tStart) / CLOCKS_PER_SEC);
    };

    std::unordered_map<int, Property > myumap;
    time("fill unordered map", [&]
    {
        myumap.insert (make_property(keys.cbegin()),
                       make_property(keys.cend()));
    });


    std::map<int, Property > mymap;
    time("fill ordered map",[&]
         {
             mymap.insert(make_property(keys.cbegin()),
                          make_property(keys.cend()));
         });

    time("find in unordered map",[&]
         {
             for (auto k : keys) { myumap.find(k); }
         });

    time("find in ordered map", [&]
         {
             for (auto k : keys) { mymap.find(k); }
         });
}

示例输出：

Performance Summary:
fill unordered map: 3.5s
fill ordered map: 7.1s
find in unordered map: 1.7s
find in ordered map: 5s