定时向量vs地图vs unordered_map查找 [英] Timed vector vs map vs unordered_map lookup

问题描述

我对矢量查找与地图查找感到好奇，并为此编写了一个小测试程序.它似乎矢量总是比我使用它的方式更快.测试有任何偏见吗?运行的结果在底部.它以纳秒为单位，但是gcc在我的平台上似乎不支持它.

I was curious on vector lookup vs map lookup and wrote a little test program for it.. its seems like vector is always faster the way I'm using it.. is there something else I should take into consideration here? Is the test biased in any way? The results of a run is at the bottom.. its in nanoseconds, but gcc doesn't seem to support it on my platform.

使用字符串进行查找当然会改变很多事情.

Using string for the lookup would of course change things a lot.

我正在使用的编译行是:g ++ -O3 --std = c ++ 0x -o lookup lookup.cpp

The compile line I'm using is this: g++ -O3 --std=c++0x -o lookup lookup.cpp

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <chrono>
#include <algorithm>

unsigned dummy = 0;

class A
{
public:
    A(unsigned id) : m_id(id){}

    unsigned id(){ return m_id; }
    void func()
    {
        //making sure its not optimized away
        dummy++;
    }
private:
    unsigned m_id;
};

class B
{
public:
    void func()
    {
        //making sure its not optimized away
        dummy++;
    }
};

int main()
{
    std::vector<A> v;
    std::unordered_map<unsigned, B> u;
    std::map<unsigned, B> m;

    unsigned elementCount = 1;

    struct Times
    {
        unsigned long long v;
        unsigned long long u;
        unsigned long long m;
    };
    std::map<unsigned, Times> timesMap;

    while(elementCount != 10000000)
    {
        elementCount *= 10;
        for(unsigned i = 0; i < elementCount; ++i)
        {
            v.emplace_back(A(i));
            u.insert(std::make_pair(i, B()));
            m.insert(std::make_pair(i, B()));
        }


        std::chrono::time_point<std::chrono::steady_clock> start = std::chrono::high_resolution_clock::now();
        for(unsigned i = 0; i < elementCount; ++i)
        {
            auto findItr = std::find_if(std::begin(v), std::end(v),
                                        [&i](A & a){ return a.id() == i; });

            findItr->func();
        }
        auto tp0 = std::chrono::high_resolution_clock::now()- start;
        unsigned long long vTime = std::chrono::duration_cast<std::chrono::nanoseconds>(tp0).count();

        start = std::chrono::high_resolution_clock::now();
        for(unsigned i = 0; i < elementCount; ++i)
        {
            u[i].func();
        }
        auto tp1 = std::chrono::high_resolution_clock::now()- start;
        unsigned long long uTime = std::chrono::duration_cast<std::chrono::nanoseconds>(tp1).count();

        start = std::chrono::high_resolution_clock::now();
        for(unsigned i = 0; i < elementCount; ++i)
        {
            m[i].func();
        }
        auto tp2 = std::chrono::high_resolution_clock::now()- start;
        unsigned long long mTime = std::chrono::duration_cast<std::chrono::nanoseconds>(tp2).count();

        timesMap.insert(std::make_pair(elementCount ,Times{vTime, uTime, mTime}));
    }

    for(auto & itr : timesMap)
    {
        std::cout << "Element count: " << itr.first << std::endl; 
        std::cout << "std::vector time:        " << itr.second.v << std::endl;
        std::cout << "std::unordered_map time: " << itr.second.u << std::endl;
        std::cout << "std::map time:           " << itr.second.m << std::endl;
        std::cout << "-----------------------------------" << std::endl;
    }

    std::cout << dummy;
}

---

./lookup 
Element count: 10
std::vector time:        0
std::unordered_map time: 0
std::map time:           1000
-----------------------------------
Element count: 100
std::vector time:        0
std::unordered_map time: 3000
std::map time:           13000
-----------------------------------
Element count: 1000
std::vector time:        2000
std::unordered_map time: 29000
std::map time:           138000
-----------------------------------
Element count: 10000
std::vector time:        22000
std::unordered_map time: 287000
std::map time:           1610000
-----------------------------------
Element count: 100000
std::vector time:        72000
std::unordered_map time: 1539000
std::map time:           8994000
-----------------------------------
Element count: 1000000
std::vector time:        746000
std::unordered_map time: 12654000
std::map time:           154060000
-----------------------------------
Element count: 10000000
std::vector time:        8001000
std::unordered_map time: 123608000
std::map time:           2279362000
-----------------------------------
33333330

推荐答案

首先，您似乎没有在两次测试之间清除容器.因此，它们不包含您认为的内容.

First, you don't seem to clear your containers between tests. So they don't contain what you think they do.

第二，根据您的时间，向量具有线性时间，这是不可能的，因为算法中的复杂度为O(N * N).可能它已经被优化了.建议不要关闭优化，而是建议将其关闭.

Second, according to your times, your vector exhibits linear time, which is something that just can't be, as complexity is O(N*N) in your algorithm. Probably it WAS optimized away. Instead of trying to combat optimization, I would suggest just turning it off.

第三，您的值对于矢量来说太可预测了.这可能会对其产生重大影响.尝试随机值(或random_shuffle())

Third, your values are too predictable for a vector. This can impact it dramatically. Try random values (or a random_shuffle())

这篇关于定时向量vs地图vs unordered_map查找的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！