为什么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. 你到底在测量什么？您的分析包括填充和扫描数据结构.鉴于(推测)填充有序地图需要更长的时间,测量两者的作用与有序地图的增益(或其他)的想法相反.弄清楚你在测量什么,并测量它.
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倍.

我怀疑你的版本有两个问题.首先,你运行的迭代太少,无法发挥作用.第二个是你在计数循环中进行昂贵的字符串操作.运行字符串操作所花费的时间大于使用无序映射所节省的时间,因此您没有看到性能上的差异.