c++ - 为什么 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 Summery:
Time taken unordered_map: 0.12s
Time taken map: 0.36s

Answer 1

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

1. 你到底在测量什么？您的分析包括填充和扫描数据结构。鉴于(大概)填充有序 map 需要更长的时间，根据有序 map 的 yield (或其他方面)的想法来衡量这两种方法。弄清楚您要测量的是什么，然后测量它。
2. 您在代码中还有很多事情可能与您正在分析的内容有关:有很多对象创建、字符串连接等。这可能是您实际测量的内容。只专注于分析您想要衡量的内容(参见第 1 点)。
3. 10,000 个案例太少了。在这种规模下，其他考虑因素可能会压倒您正在衡量的内容，尤其是当您正在衡量一切时。