gpt4 book ai didi

c++ - 定时 vector vs map vs unordered_map 查找

转载 作者:太空狗 更新时间:2023-10-29 23:45:56 24 4
gpt4 key购买 nike

我对 vector 查找与 map 查找很好奇,并为它编写了一个小测试程序。它似乎 vector 总是比我使用它的方式更快。这里还有什么我应该考虑的吗?测试是否存在任何偏差?运行结果在底部。以纳秒为单位,但 gcc 在我的平台上似乎不支持它。

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

我使用的编译行是这样的: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

最佳答案

我一点也不震惊 vector 测试比其他任何东西都好。它的汇编代码(实际反汇编)分解为(在我的 Apple LLVM 4.2 上完全选择):

0x100001205:  callq  0x100002696               ; symbol stub for: std::__1::chrono::steady_clock::now()
0x10000120a: testl %r13d, %r13d
0x10000120d: leaq -272(%rbp), %rbx
0x100001214: je 0x100001224 ; main + 328 at main.cpp:78
0x100001216: imull $10, %r14d, %ecx
0x10000121a: incl 7896(%rip) ; dummy
0x100001220: decl %ecx
0x100001222: jne 0x10000121a ; main + 318 [inlined] A::func() at main.cpp:83
main + 318 at main.cpp:83
0x100001224: movq %rax, -280(%rbp)
0x10000122b: callq 0x100002696 ; symbol stub for: std::__1::chrono::

注意“循环”(jne 0x10000121a)。 “find_if”已被完全优化,结果实际上是用递减寄存器扫描数组以计算递增全局的次数。 这就是正在做的一切;在此过程中没有进行任何类型的搜索。

是的,关键在于您如何使用它。

关于c++ - 定时 vector vs map vs unordered_map 查找,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14871315/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com