STL中关联数组(map)的速度

Speed of associative array (map) in STL

写了一个简单的程序来测量STL的速度。以下代码显示在我的 Corei7-2670QM PC(2.2GHz 和 Turbo 3.1GHz)上花费了 1.49 秒。如果我删除循环中的 Employees[buf] = i%1000; 部分,只需要 0.0132 秒。所以散列部分用了 1.48 秒。为什么这么慢?

#include <string.h>
#include <iostream>
#include <map>
#include <utility>
#include <stdio.h>
#include <sys/time.h>
using namespace std;

extern "C" {
int get(map<string, int> e, char* s){
    return e[s];
}
int set(map<string, int> e, char* s, int value) {
    e[s] = value;
}
}

double getTS() {
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec + tv.tv_usec/1000000.0;
}

int main()
{
    map<string, int> Employees;
    char buf[10];
    int i;
    double ts = getTS();
    for (i=0; i<1000000; i++) {
        sprintf(buf, "%08d", i);
        Employees[buf] = i%1000;
    }
    printf("took %f sec\n", getTS() - ts);
    cout << Employees["00001234"] << endl;
    return 0;
}

这是您的代码的 C++ 版本。请注意,在 get/set.[=18= 中传递地图时,您应该 显然 通过引用获取地图]

更新 更进一步,认真优化给定的测试用例:

Live On Coliru

#include <iostream>
#include <boost/container/flat_map.hpp>
#include <chrono>
using namespace std;

using Map = boost::container::flat_map<string, int>;

int get(Map &e, char *s) { return e[s]; }
int set(Map &e, char *s, int value) { return e[s] = value; }

using Clock = std::chrono::high_resolution_clock;

template <typename F, typename Reso = std::chrono::microseconds, typename... Args> 
Reso measure(F&& f, Args&&... args) {
    auto since = Clock::now();
    std::forward<F>(f)(std::forward<Args>(args)...);
    return chrono::duration_cast<Reso>(Clock::now() - since);
}

#include <boost/iterator/iterator_facade.hpp>

using Pair = std::pair<std::string, int>;

struct Gen : boost::iterators::iterator_facade<Gen, Pair, boost::iterators::single_pass_traversal_tag, Pair>
{
    int i;
    Gen(int i = 0) : i(i) {}

    value_type dereference() const { 
        char buf[10];
        std::sprintf(buf, "%08d", i);
        return { buf, i%1000 }; 
    }
    bool equal(Gen const& o) const { return i==o.i; }
    void increment() { ++i; }
};

int main() {
    Map Employees;
    const auto n = 1000000;

    auto elapsed = measure([&] {
            Employees.reserve(n);
            Employees.insert<Gen>(boost::container::ordered_unique_range, {0}, {n});
        });

    std::cout << "took " << elapsed.count() / 1000000.0 << " sec\n";

    cout << Employees["00001234"] << endl;
}

版画

took 0.146575 sec
234

旧答案

这只是在适当的地方使用了 C++

Live On Coliru

#include <iostream>
#include <map>
#include <chrono>
#include <cstdio>
using namespace std;

int get(map<string, int>& e, char* s){
    return e[s];
}
int set(map<string, int>& e, char* s, int value) {
    return e[s] = value;
}

using Clock = std::chrono::high_resolution_clock;

template <typename Reso = std::chrono::microseconds>
Reso getElapsed(Clock::time_point const& since) {
    return chrono::duration_cast<Reso>(Clock::now() - since);
}

int main()
{
    map<string, int> Employees;
    std::string buf(10, '[=12=]');

    auto ts = Clock::now();
    for (int i=0; i<1000000; i++) {
        buf.resize(std::sprintf(&buf[0], "%08d", i));
        Employees[buf] = i%1000;
    }
    std::cout << "took " << getElapsed(ts).count()/1000000.0 << " sec\n";
    cout << Employees["00001234"] << endl;
}

打印:

took 0.470009 sec
234

"slow"的概念当然要看和什么比较。

我 运行 你在 MSVC2013 上的基准测试(使用标准 chrono::high_resolution_clock 而不是 gettimeofday() ),在 Corei7-920 上以 2.67 GHz 发布配置,发现非常相似的结果(1.452 秒) .

在你的代码中,你基本上做了 100 万次:

  • 在地图中插入:Employees\[buf\]
  • 在地图中更新(将新元素复制到现有元素):= i%1000

所以我试图更好地理解时间花在了哪里:

  • 首先,map needs to store the ordered keys, which is typically implemented with a binary tree. So I tried to use an unordered_map 使用更平坦的散列 table 并为其提供非常大的存储桶大小以避免碰撞和重新散列。结果是 1.198 s.
    因此,大约需要 20% 的时间(此处)才能对地图数据进行排序访问(即,您可以使用键的顺序遍历地图:您需要这个?)

  • 其次,调整插入顺序确实会显着影响时间。正如 Thomas Matthews 在评论中指出的那样:出于基准测试目的,您应该使用 运行dom 顺序。

  • 然后,使用 emplace_hint() 进行仅优化的数据插入(不搜索不更新)将我们带到 1.100 秒的时间。
    所以 75% 的时间用于分配和插入数据

  • 最后,详细说明之前的测试,如果在emplace_hint()之后添加额外的搜索和更新,那么时间会略高于原来的时间(1.468 秒)。这证实了对地图的访问只用了一小部分时间,而插入所需的大部分执行时间。

这里测试上面的点:

chrono::high_resolution_clock::time_point ts = chrono::high_resolution_clock::now();
for (i = 0; i<1000000; i++) {
    sprintf(buf, "%08d", i);
    Employees.emplace_hint(Employees.end(), buf, 0);
    Employees[buf] = i % 1000;  // matters for 300 
}
chrono::high_resolution_clock::time_point te = chrono::high_resolution_clock::now();
cout << "took " << chrono::duration_cast<chrono::milliseconds>(te - ts).count() << " millisecs\n";

现在您的基准测试不仅取决于地图的性能:您需要执行 100 万次 sprintf() 来设置缓冲区,以及执行 100 万次转换为字符串的操作。如果您改为使用地图,您会注意到整个测试只需要 0.950 秒而不是 1.450 秒:

  • 30% 的基准测试时间不是由地图造成的,而是由您处理的许多字符串造成的!

当然,这一切都比向量慢得多。但是向量不会对其元素进行排序,也无法提供关联存储。