为什么 unordered_map 和 map 提供相同的性能？

Question

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

更新：我已经根据以下答案和评论更改了我的代码。我删除了字符串操作以减少对分析的影响。现在我也只测量 find() ，它在我的代码中占据了 CPU 的近 40%。配置文件显示 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 点）。
10,000 例太少了。在这个规模上，其他考虑因素可能会压倒您正在衡量的内容，尤其是当您正在衡量一切时。

Answer 2

我们喜欢获得 minimal, complete and verifiable 个示例是有原因的。这是我的代码：

#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

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

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

Answer 3

树 (std::map) 还是哈希映射 (std::unordered_map) 更快实际上取决于条目的数量和键的特征（值的可变性、比较和散列函数等）

但是理论上,树比哈希映射慢因为二叉树内部的插入和搜索是O(log2(N)) 在哈希映射中插入和搜索时的复杂度大约是 O(1) 的复杂度。

您的测试没有显示它，因为：

你循环调用了rand()。与地图插入相比，这需要很长时间。它会为您正在测试的两个地图生成不同的值，从而进一步扭曲结果。使用重量更轻的发电机，例如minstd LCG.
您需要更高分辨率的时钟和更多的迭代，以便每个测试运行至少需要 几百毫秒 .
您需要确保编译器不会重新排序您的代码，以便计时调用发生在它们应该发生的地方。这并不总是那么容易。定时测试周围的内存栅栏通常有助于解决这个问题。
你的 find() 调用很有可能被优化掉，因为你没有使用它们的值（我只是碰巧知道至少 GCC 在 -O2 模式下没有这样做，所以我保持原样）。
相比之下，字符串连接也很慢。

这是我的更新版本：

#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>>());
}

Compiled with -O2，结果如下：

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

因此在 这种特殊情况下 使用 unordered_map 会快 ~20-25%。

Answer 4

unordered_map 不仅查找速度更快。这个稍微修改过的测试还比较了填充时间。

我做了一些修改：

样本量增加
两个地图现在使用相同的随机数序列。

-

#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

为什么 unordered_map 和 map 提供相同的性能？

Why is unordered_map and map giving the same performance?

c++

performance

unordered-map

data-structures