by zieckey
map hash_map unordered_map 性能测试
先给结论：
1. std::tr1::unordered_map 与 std::ext/hash_map
相对而言，遍历、查找等操作unordered_map要优于hash_map。hash_map的删除操作稍稍优于unordered_map。插入操作随着数据量的变化，10000以内时hash_map稍稍占优，10000以上的数据时，unordered_map 要稍稍快于hash_map。
2. std::tr1::unordered_map 与 std::map
unordered_map在元素个数小于1000的时候，遍历性能稍稍低于map 25%左右，一旦大于元素个数大于1000，起遍历所花时间较map多2~3倍。
因此，当我们遍历较多时，请考虑使用map而不是unordered_map。另外，当我们需要一个有序的关联容器的时候，我们必须选择map，因为 unordered_map 内部元素不是有序的，这一点从名字都可以看出来。
测试条件：
gcc version 4.2.1 20070719 [FreeBSD]
FreeBSD 7.2-RELEASE #0: Fri May 1 07:18:07 UTC 2009 root@driscoll.cse.buffalo.edu:/usr/obj/usr/src/sys/GENERIC amd64
Intel(R) Xeon(R) CPU E5620 @ 2.40GHz 16核
Intel(R) Xeon(R) CPU E5620 @ 2.40GHz 16核
测试程序说明：
先准备好n个字符串随机的MD5字符串做为key，然后分别对3个容器进行插入、遍历、查找、删除操作。
例如，n=100的时候，插入是指插入100个随机MD5 key；遍历是指对容器遍历一次；查找是指分别对这个100个随机的MD5 key做查找操作（即查找100次）；删除是指挨个删除这个100个随机MD5 key。
测试数据如下表：
| 插入，单位us | 100 | 1K | 10K | 100K | 1M | 10M |
| std::map | 272 | 3485 | 43767 | 538052 | 3938154 | 45533490 |
| std::ext/hash_map | 71 | 1021 | 10315 | 104186 | 1248504 | 13433655 |
| std::tr1::unordered_map | 127 | 1177 | 11728 | 76864 | 1040697 | 16458108 |
| 遍历，单位us | 100 | 1K | 10K | 100K | 1M | 10M |
| std::map | 9 | 70 | 644 | 5401 | 53625 | 532577 |
| std::ext/hash_map | 24 | 236 | 2486 | 27212 | 363523 | 3710704 |
| std::tr1::unordered_map | 12 | 97 | 969 | 10421 | 144206 | 1699897 |
| 查找，单位us | 100 | 1K | 10K | 100K | 1M | 10M |
| std::map | 148 | 2038 | 26213 | 209723 | 2499951 | 28973101 |
| std::ext/hash_map | 46 | 461 | 4934 | 35967 | 457870 | 5254755 |
| std::tr1::unordered_map | 35 | 403 | 3692 | 29146 | 392346 | 4132001 |
| 删除，单位us | 100 | 1K | 10K | 100K | 1M | 10M |
| std::map | 230 | 3149 | 40542 | 362716 | 4114198 | 48995221 |
| std::ext/hash_map | 55 | 545 | 5739 | 65101 | 642365 | 7980524 |
| std::tr1::unordered_map | 62 | 674 | 6363 | 68268 | 705815 | 8129359 |
附录：贴上源代码
说明：与测试程序稍有区别，这里的源码里没有MD5相关的代码以确保其他人能比较方便的直接拿去编译运行。
如有错误还请跟帖指出，非常感谢。
#include <iostream>
#include <string>
#include <sstream>
#include <list>
#include <map>
#include <sys/time.h>
#include <ext/hash_map>
#include <tr1/unordered_map>
#include <tr1/unordered_set>
namespace zl
{ //{{{
struct equal_to
{
bool operator ()( const char * s1 , const char * s2 ) const
{
return strcmp ( s1, s2 ) == 0;
}
};
struct hash_string
: public std :: unary_function< std ::string , std:: size_t >
{
std ::size_t
operator ()(const std:: string & __s ) const
#ifdef __linux__
{ return std :: tr1:: Fnv_hash <>::hash ( __s. data (), __s . length()); }
#else
{ return std :: tr1:: _Fnv_hash <>::hash ( __s. data (), __s . length()); }
#endif
};
struct hash_charptr
: public std :: unary_function< const char *, std:: size_t >
{
std ::size_t
operator ()(const char* __s ) const
#ifdef __linux__
{ return std :: tr1:: Fnv_hash <>::hash ( __s, strlen (__s )); }
#else
{ return std :: tr1:: _Fnv_hash <>::hash ( __s, strlen (__s )); }
#endif
};
} //}}}
typedef std :: list< std ::string > string_list;
typedef std :: map< std ::string , int> string_map ;
typedef __gnu_cxx :: hash_map< std ::string , int, zl ::hash_string > string_hash_map;
typedef std :: tr1:: unordered_map <std :: string, int > string_unordered_map ;
void fill_list ( string_list& slist , size_t count);
uint64_t current_usec ();
int main ( int argc , char * argv[] )
{
if ( argc != 2 && argc != 3)
{
fprintf (stderr , “Usage:%s test_count rehash\n” , argv [0]);
fprintf (stderr , “For example:%s 10000 rehash\n” , argv [0]);
return -1;
}
size_t count = atoi ( argv[1]);
bool rehash = false ;
if ( argc == 3)
{
rehash = true ;
}
string_map smap ;
string_hash_map shash_map ;
string_unordered_map sunordered_map ;
if ( rehash )
{
sunordered_map .rehash ( count);
}
string_list slist ;
fill_list( slist , count );
uint64_t start = 0;
uint64_t end = 0;
uint64_t map_insert_us = 0;
uint64_t hash_map_insert_us = 0;
uint64_t unordered_map_insert_us = 0;
uint64_t map_traverse_us = 0;
uint64_t hash_map_traverse_us = 0;
uint64_t unordered_map_traverse_us = 0;
uint64_t map_find_us = 0;
uint64_t hash_map_find_us = 0;
uint64_t unordered_map_find_us = 0;
uint64_t map_delete_us = 0;
uint64_t hash_map_delete_us = 0;
uint64_t unordered_map_delete_us = 0;
// Insert test
{ //{{{
string_list ::iterator it( slist .begin ());
string_list ::iterator ite( slist .end ());
//map insert
start = current_usec ();
for (int i = 0; it != ite ; ++ it, ++ i )
{
smap [*it ] = i;
}
end = current_usec ();
map_insert_us = end - start;
//hash_map insert
it = slist . begin();
start = current_usec ();
for (int i = 0; it != ite ; ++ it, ++ i )
{
shash_map [*it ] = i;
}
end = current_usec ();
hash_map_insert_us = end - start;
//unordered_map insert
it = slist . begin();
start = current_usec ();
for (int i = 0; it != ite ; ++ it, ++ i )
{
sunordered_map [*it ] = i;
}
end = current_usec ();
unordered_map_insert_us = end - start;
} //}}}
// Traverse test
{ //{{{
//map traverse
{
string_map ::iterator it( smap .begin ());
string_map ::iterator ite( smap .end ());
start = current_usec ();
for (int i = 0; it != ite ; ++ it)
{
i ++;
}
end = current_usec ();
map_traverse_us = end - start;
}
//hash_map traverse
{
string_hash_map ::iterator it( shash_map .begin ());
string_hash_map ::iterator ite( shash_map .end ());
start = current_usec ();
for (int i = 0; it != ite ; ++ it)
{
i ++;
}
end = current_usec ();
hash_map_traverse_us = end - start;
}
//unordered_map traverse
{
string_unordered_map ::iterator it( sunordered_map .begin ());
string_unordered_map ::iterator ite( sunordered_map .end ());
start = current_usec ();
for (int i = 0; it != ite ; ++ it)
{
i ++;
}
end = current_usec ();
unordered_map_traverse_us = end - start;
}
} //}}}
// Find test
{ //{{{
string_list ::iterator it( slist .begin ());
string_list ::iterator ite( slist .end ());
//map find
start = current_usec ();
for (int i = 0; it != ite ; ++ it, ++ i )
{
smap [*it ] = i;
}
end = current_usec ();
map_find_us = end - start;
//hash_map find
it = slist . begin();
start = current_usec ();
for (int i = 0; it != ite ; ++ it, ++ i )
{
shash_map [*it ] = i;
}
end = current_usec ();
hash_map_find_us = end - start;
//unordered_map find
it = slist . begin();
start = current_usec ();
for (int i = 0; it != ite ; ++ it, ++ i )
{
sunordered_map [*it ] = i;
}
end = current_usec ();
unordered_map_find_us = end - start;
} //}}}
// Delete test
{ //{{{
string_list ::iterator it( slist .begin ());
string_list ::iterator ite( slist .end ());
//map delete
start = current_usec ();
for (int i = 0; it != ite ; ++ it, ++ i )
{
smap .erase (* it);
}
end = current_usec ();
map_delete_us = end - start;
//hash_map delete
it = slist . begin();
start = current_usec ();
for (int i = 0; it != ite ; ++ it, ++ i )
{
shash_map .erase (* it);
}
end = current_usec ();
hash_map_delete_us = end - start;
//unordered_map delete
it = slist . begin();
start = current_usec ();
for (int i = 0; it != ite ; ++ it, ++ i )
{
sunordered_map .erase (* it);
}
end = current_usec ();
unordered_map_delete_us = end - start;
} //}}}
//stat output
std:: cout << “ insert, count “ << count << std ::endl ;
std:: cout << “ std::map “ << map_insert_us << ” us\n” ;
std:: cout << “ std::ext/hash_map “ << hash_map_insert_us << ” us\n” ;
std:: cout << “std::tr1::unordered_map “ << unordered_map_insert_us << ” us\n” ;
std:: cout << “\n” ;
std:: cout << “ traverse, count “ << count << std ::endl ;
std:: cout << “ std::map “ << map_traverse_us << ” us\n” ;
std:: cout << “ std::ext/hash_map “ << hash_map_traverse_us << ” us\n” ;
std:: cout << “std::tr1::unordered_map “ << unordered_map_traverse_us << ” us\n”;
std:: cout << “\n” ;
std:: cout << “ find, count “ << count << std ::endl ;
std:: cout << “ std::map “ << map_find_us << ” us\n” ;
std:: cout << “ std::ext/hash_map “ << hash_map_find_us << ” us\n” ;
std:: cout << “std::tr1::unordered_map “ << unordered_map_find_us << ” us\n” ;
std:: cout << “\n” ;
std:: cout << “ delete, count “ << count << std ::endl ;
std:: cout << “ std::map “ << map_delete_us << ” us\n” ;
std:: cout << “ std::ext/hash_map “ << hash_map_delete_us << ” us\n” ;
std:: cout << “std::tr1::unordered_map “ << unordered_map_delete_us << ” us\n” ;
return 0;
}
void fill_list ( string_list& slist , size_t count)
{
for ( size_t i = 0; i < count ; ++i )
{
std ::ostringstream oss;
oss << i ;
//slist.push_back(MD5::hex(oss.str().c_str(), oss.str().length()));
slist .push_back ( oss. str ());//
}
}
uint64_t current_usec ()
{
struct timeval tv ;
gettimeofday( & tv , NULL );
return tv .tv_sec * 1000 * 1000 + tv. tv_usec ;
}
评论关闭 (0 views)