首页    技术博客    PHP教程    数据库技术    前端开发   HTML5    Nginx    php论坛
新用户注册 | 会员登录
9赞
228
当前位置:  开发笔记 > 编程语言 > 正文

在实践中,unordered_map真的比地图快吗？

作者：黄可麟66032 | 来源：互联网 | 2023-03-19 05:21
如何解决《在实践中,unordered_map真的比地图快吗？》经验，为你挑选了2个好方法。

当然,unordered_map的查找性能平均是常量,并且映射的查找性能是O(logN).

但是当然为了在unordered_map中找到一个对象,我们必须:

    哈希我们想要找到的密钥.

    equality_compare键与同一个桶中的每个键.

而在地图中,我们只需要将所搜索的密钥与log2(N)密钥进行比较,其中N是地图中的项目数.

我想知道真正的性能差异是什么,假设散列函数增加了开销并且equality_compare不比less_than比较便宜.

我写了一个测试,而不是用一个我可以自己回答的问题打扰社区.

我已经分享了下面的结果,以防其他人发现这个有趣或有用.

如果有人能够并且愿意添加更多信息,当然会邀请更多答案.



1> Richard Hodg..：

在回答有关错过搜索次数的性能问题时,我重构了测试以对此进行参数化.

示例结果:

searches=1000000 set_size=      0 miss=    100% ordered=   4384 unordered=  12901 flat_map=    681
searches=1000000 set_size=     99 miss=  99.99% ordered=  89127 unordered=  42615 flat_map=  86091
searches=1000000 set_size=    172 miss=  99.98% ordered= 101283 unordered=  53468 flat_map=  96008
searches=1000000 set_size=    303 miss=  99.97% ordered= 112747 unordered=  53211 flat_map= 107343
searches=1000000 set_size=    396 miss=  99.96% ordered= 124179 unordered=  59655 flat_map= 112687
searches=1000000 set_size=    523 miss=  99.95% ordered= 132180 unordered=  51133 flat_map= 121669
searches=1000000 set_size=    599 miss=  99.94% ordered= 135850 unordered=  55078 flat_map= 121072
searches=1000000 set_size=    695 miss=  99.93% ordered= 140204 unordered=  60087 flat_map= 124961
searches=1000000 set_size=    795 miss=  99.92% ordered= 146071 unordered=  64790 flat_map= 127873
searches=1000000 set_size=    916 miss=  99.91% ordered= 154461 unordered=  50944 flat_map= 133194
searches=1000000 set_size=    988 miss=   99.9% ordered= 156327 unordered=  54094 flat_map= 134288

键:

searches = number of searches performed against each map
set_size = how big each map is (and therefore how many of the searches will result in a hit)
miss = the probability of generating a missed search. Used for generating searches and set_size.
ordered = the time spent searching the ordered map
unordered = the time spent searching the unordered_map
flat_map = the time spent searching the flat map

note: time is measured in std::system_clock::duration ticks.

TL; DR

结果:只要地图中有数据,unordered_map就会显示其优越性.唯一一次表现出比有序地图更差的表现是地图是空的.

这是新代码:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

// this sets the length of the string we will be using as a key.
// modify this to test whether key complexity changes the performance ratios
// of the various maps
static const size_t key_length = 20;

// the number of keys we will generate (the size of the test)
const size_t nkeys = 1000000;



// use a virtual method to prevent the optimiser from detecting that
// our sink function actually does nothing. otherwise it might skew the test
struct string_user
{
    virtual void sink(const std::string&) = 0;
    virtual ~string_user() = default;
};

struct real_string_user : string_user
{
    virtual void sink(const std::string&) override
    {

    }
};

struct real_string_user_print : string_user
{
    virtual void sink(const std::string& s) override
    {
        cout < make_sink(const std::string& name)
{
    if (name == "print")
    {
        return make_unique();
    }
    if (name == "noprint")
    {
        return make_unique();
    }
    throw logic_error(name);
}

// generate a random key, given a random engine and a distribution
auto gen_string = [](auto& engine, auto& dist)
{
    std::string result(key_length, ' ');
    generate(begin(result), end(result), [&] {
        return dist(engine);
    });
    return result;
};

// comparison predicate for our flat map.
struct pair_less
{
    bool operator()(const pair& l, const string& r) const {
        return l.first & r) const {
        return l 
auto time_test(F&& f, const vector keys)
{
    auto start_time = chrono::system_clock::now();

    for (auto const& key : keys)
    {
        f(key);
    }

    auto stop_time = chrono::system_clock::now();
    auto diff =  stop_time - start_time;
    return diff;
}

struct report_key
{
    size_t nkeys;
    int miss_chance;
};

std::ostream& operator<<(std::ostream& os, const report_key& key)
{
    return os <<"miss=" < unordered;
    map ordered;
    vector> flat_map;

    // a vector of all keys, which we can shuffle in order to randomise
    // access order of all our maps consistently
    vector keys;
    unordered_set keys_record;

    // generate keys
    auto eng = std::default_random_engine(std::random_device()());
    auto alpha_dist = std::uniform_int_distribution('A', 'Z');
    auto prob_dist = std::uniform_real_distribution(0, 1.0 - std::numeric_limits::epsilon());

    auto generate_new_key = [&] {
        while(true) {
            // generate a key
            auto key = gen_string(eng, alpha_dist);
            // try to store it in the unordered map
            // if it already exists, force a regeneration
            // otherwise also store it in the ordered map and the flat map
            if(keys_record.insert(key).second) {
                return key;
            }
        }
    };

    for (size_t i = 0 ; i = miss_prob) {
            unordered.emplace(key, value);
            flat_map.emplace_back(key, value);
            ordered.emplace(key, std::move(value));
        }
        // record the key for later use
        keys.emplace_back(std::move(key));
    }
    // turn our vector 'flat map' into an actual flat map by sorting it by pair.first. This is the key.
    sort(begin(flat_map), end(flat_map),
         [](const auto& l, const auto& r) { return l.first second);
        }
    };

    auto ordered_lookup = [&](auto& key) {
        auto i = ordered.find(key);
        if (i != end(ordered)) {
            sink.sink(i->second);
        }
    };

    auto flat_map_lookup = [&](auto& key) {
        auto i = lower_bound(begin(flat_map),
                             end(flat_map),
                             key,
                             pair_less());
        if (i != end(flat_map) && i->first == key) {
            sink.sink(i->second);
        }
    };

    // spawn a thread to time access to the unordered map
    auto unordered_future = async(launch::async,
                                  [&]()
                                  {
                                      return time_test(unordered_lookup, keys);
                                  });

    // spawn a thread to time access to the ordered map
    auto ordered_future = async(launch::async, [&]
                                {
                                    return time_test(ordered_lookup, keys);
                                });

    // spawn a thread to time access to the flat map
    auto flat_future = async(launch::async, [&]
                             {
                                 return time_test(flat_map_lookup, keys);
                             });

    // synchronise all the threads and get the timings
    auto ordered_time = ordered_future.get();
    auto unordered_time = unordered_future.get();
    auto flat_time = flat_future.get();

    cout <<"searches=" <> arg;
    auto puser = make_sink(arg);

    for (double chance = 1.0 ; chance >= 0.0 ; chance -= 0.0001)
    {
        run_test(*puser, 1000000, chance);
    }


    return 0;
}



2> Richard Hodg..：

在下面的测试中，我使用-O3在Apple clang上进行了编译，我采取了一些措施来确保测试是公平的，例如：

    通过vtable调用每次接收结果的接收器函数，以防止优化程序内联整个搜索！

    在3种不同的包含相同数据的地图上，以相同的顺序并行运行测试。这意味着，如果一个测试开始“领先”，它将开始为搜索集输入缓存缺失区域（请参见代码）。这意味着没有人会遇到遇到“热”缓存的不公平优势。

    参数化密钥大小（以及复杂度）

    参数化地图大小

    测试了三种不同类型的地图（包含相同的数据）-unordered_map，地图和键/值对的排序向量。

    检查汇编器输出，以确保优化器由于死代码分析而无法优化掉整个逻辑块。

这是代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

// this sets the length of the string we will be using as a key.
// modify this to test whether key complexity changes the performance ratios
// of the various maps
static const size_t key_length = 20;

// the number of keys we will generate (the size of the test)
const size_t nkeys = 1000000;


// the types of map we will test
unordered_map unordered;
map ordered;
vector> flat_map;

// a vector of all keys, which we can shuffle in order to randomise
// access order of all our maps consistently
vector keys;

// use a virtual method to prevent the optimiser from detecting that
// our sink function actually does nothing. otherwise it might skew the test
struct string_user
{
    virtual void sink(const std::string&) = 0;
    virtual ~string_user() = default;
};

struct real_string_user : string_user
{
    virtual void sink(const std::string&) override
    {

    }
};

struct real_string_user_print : string_user
{
    virtual void sink(const std::string& s) override
    {
        cout < make_sink(const std::string& name)
{
    if (name == "print")
    {
        return make_unique();
    }
    if (name == "noprint")
    {
        return make_unique();
    }
    throw logic_error(name);
}

// generate a random key, given a random engine and a distribution
auto gen_string = [](auto& engine, auto& dist)
{
    std::string result(key_length, ' ');
    generate(begin(result), end(result), [&] {
        return dist(engine);
    });
    return result;
};

// comparison predicate for our flat map.
struct pair_less
{
    bool operator()(const pair& l, const string& r) const {
        return l.first & r) const {
        return l > arg;
    auto puser = make_sink(arg);

    // generate keys
    auto eng = std::default_random_engine(std::random_device()());
    auto alpha_dist = std::uniform_int_distribution('A', 'Z');

    for (size_t i = 0 ; i sink(unordered.at(key));
                                      }

                                      auto stop_time = chrono::system_clock::now();
                                      auto diff =  stop_time - start_time;
                                      return diff;
                                  });

    // spawn a thread to time access to the ordered map
    auto ordered_future = async(launch::async, [&]
                                {

                                    auto start_time = chrono::system_clock::now();

                                    for (auto const& key : keys)
                                    {
                                        puser->sink(ordered.at(key));
                                    }

                                    auto stop_time = chrono::system_clock::now();
                                    auto diff =  stop_time - start_time;
                                    return diff;
                                });

    // spawn a thread to time access to the flat map
    auto flat_future = async(launch::async, [&]
                                {

                                    auto start_time = chrono::system_clock::now();

                                    for (auto const& key : keys)
                                    {
                                        auto i = lower_bound(begin(flat_map),
                                                               end(flat_map),
                                                               key,
                                                               pair_less());
                                        if (i != end(flat_map) && i->first == key)
                                            puser->sink(i->second);
                                        else
                                            throw invalid_argument(key);
                                    }

                                    auto stop_time = chrono::system_clock::now();
                                    auto diff =  stop_time - start_time;
                                    return diff;
                                });

    // synchronise all the threads and get the timings
    auto ordered_time = ordered_future.get();
    auto unordered_time = unordered_future.get();
    auto flat_time = flat_future.get();

    // print
    cout <<"  ordered time: " <


结果：



  ordered time: 972711
unordered time: 335821
 flat map time: 559768




如您所见，unordered_map令人信服地击败了地图和排序对向量。对向量的速度是映射解的两倍。这很有趣，因为lower_bound和map :: at具有几乎相等的复杂性。



TL; DR



在此测试中，无序图的速度（查找）大约是有序图的3倍，排序后的向量令人信服地击败了图。



实际上，我对它的速度感到震惊。

        
看起来您的“平面地图”测试实际上在搜索排序后的向量和有序地图。所以我感到奇怪的是它的时机相同。实际上-这可能与同时运行测试有关。如果不同时运行测试以消除争用作为一个因素，我个人会感觉更好。此外，平面地图测试不应对“有序”对象进行任何操作（除非我误解了）。
推荐阅读
author-avatar
黄可麟66032
这个家伙很懒，什么也没留下！
Tags | 热门标签
RankList | 热门文章
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有