我对矢量查找与地图查找感到好奇,并为它编写了一个小测试程序。它看起来矢量总是比我使用它的方式更快。这里还有什么我应该考虑的吗?测试是否有任何偏差?运行的结果在底部......以纳秒为单位,但 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
我一点也不惊讶载体测试比其他任何东西都好。它的 asm 代码(实际反汇编)分解为(在我的 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”已完全优化,结果是使用递减寄存器有效地扫描数组,以计算全局递增的次数。这就是正在做的全部事情;在此过程中没有进行任何形式的搜查。
所以是的,这就是你如何使用它。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)