STL に取り入れられなかったものの一つに Hash があり、それを使った set や map が STLport や C++0x, Boost で取り込まれていますが、Poco にも Poco::HashSet や Poco::HashMap として実装されています。
Poco::HashSet や Poco::HashMap は、std::set や std::map と（iterator が Iteratorだったりする以外は）ほとんど同様に使えるので、今回は使い方ではなく、std::set と Poco::HashSet の速度を比較してみたいと思います。
HashSetTest.cpp
・Poco::Random で 262,144 個の乱数を発生させ、
そのまま Poco::UInt32 をキーにした場合
16 進数の文字列（8 文字）に変換した std::string をキーにした場合
のそれぞれで、
insert を 262,144 回
find を 262,144 回
erase を 262,144 回
順次実行して、std::set と Poco::HashSet の速度を比較。
#include <Poco/Format.h> #include <Poco/Random.h> #include <Poco/HashSet.h> #include <string> #include <vector> #include <set> #include <iostream> #include "ScopedElapsedTime.h" #include "PrepareConsoleLogger.h" enum MethodSel { eInsert = 0 , eFind , eErase , eNumMethod }; template <class Tc, class Tk> void TestInsert(Tc& container, const Tk& key) { container.insert(key); } template <class Tc, class Tk> void TestFind(Tc& container, const Tk& key) { container.find(key); } template <class Tc, class Tk> void TestErase(Tc& container, const Tk& key) { container.erase(key); } template <class Tc, class Tk> void TestMethod( Tc& container , MethodSel sel , const std::string& title , const std::vector<Tk>& keyVector , bool needsNewLine=false) { if(eNumMethod <= sel) return; typedef void (*CallMethod)(Tc& container, const Tk& key); CallMethod methodVector[] = { TestInsert<Tc, Tk> , TestFind<Tc, Tk> , TestErase<Tc, Tk> }; CallMethod method = methodVector[sel]; { ScopedElapsedTime msg(title, "start", "end" + std::string(needsNewLine ? "\n":"")); for(std::size_t i=0; i<keyVector.size(); ++i) { method(container, keyVector[i]); } } } template <class Tk> void TestAll(std::vector<Tk>& keyVector) { std::set<Tk> stdSet; Poco::HashSet<Tk> pocoHashSet; TestMethod(stdSet, eInsert, "std::set insert ", keyVector); TestMethod(pocoHashSet, eInsert, "HashSet insert ", keyVector, true); TestMethod(stdSet, eFind, "std::set find ", keyVector); TestMethod(pocoHashSet, eFind, "HashSet find ", keyVector, true); TestMethod(stdSet, eErase, "std::set erase ", keyVector); TestMethod(pocoHashSet, eErase, "HashSet erase ", keyVector, true); } int main(int /*argc*/, char** /*argv*/) { PrepareConsoleLogger logger(Poco::Logger::ROOT, Poco::Message::PRIO_INFORMATION); const std::string::size_type kNumKeys = 262144; std::vector<Poco::UInt32> intVector(kNumKeys); std::vector<std::string> strVector(kNumKeys); Poco::Random random; for(std::size_t i=0; i<kNumKeys; ++i) { intVector[i] = random.next(); strVector[i] = Poco::format("%08x", intVector[i]); } std::cout << "------------------------------------" << std::endl; std::cout << "Comparison for key type Poco::UInt32" << std::endl; std::cout << "------------------------------------" << std::endl; TestAll(intVector); std::cout << "----------------------------------------------" << std::endl; std::cout << "Comparison for key type std::string (length=8)" << std::endl; std::cout << "----------------------------------------------" << std::endl; TestAll(strVector); return 0; } |
Results of execution
・Mac mini (Mac OS X 10.6.3, 2GHz Core 2 Duo, RAM 2GB, gcc 4.2.1) で実行。
| std::set（基準） | Poco::HashSet | 比較 | |
|---|---|---|---|
| insert | 191.453 mSec | 286.784 mSec | 1.498 倍 |
| find | 150.107 mSec | 36.377 mSec | 0.242 倍 |
| erase | 262.271 mSec | 117.745 mSec | 0.449 倍 |
| Total | 603.831 mSec | 440.906 mSec | 0.730 倍 |
・Total で 3 割近く Poco::HashSet が早いが、find が約 4 倍速！
・しかし、insert が約 1.5 倍遅い。
| std::set（基準） | Poco::HashSet | 比較 | |
|---|---|---|---|
| insert | 434.074 mSec | 602.558 mSec | 1.388 倍 |
| find | 405.215 mSec | 102.051 mSec | 0.252 倍 |
| erase | 603.113 mSec | 260.250 mSec | 0.432 倍 |
| Total | 1,442.402 mSec | 964.859 mSec | 0.669 倍 |
・Total で 3 割以上 Poco::HashSet が早いが、find が約 4 倍速！
・しかし、insert が約 1.4 倍遅い。
両者とも：
・構築／再構築の回数が少なくて、find を多数回繰り返す用途の場合、Poco::HashSet の利用価値大。
------------------------------------ Comparison for key type Poco::UInt32 ------------------------------------ [0] std::set insert start [0] Elepsed time = 191.453mSec [0] std::set insert end [0] HashSet insert start [0] Elepsed time = 286.784mSec [0] HashSet insert end [0] std::set find start [0] Elepsed time = 150.107mSec [0] std::set find end [0] HashSet find start [0] Elepsed time = 36.377mSec [0] HashSet find end [0] std::set erase start [0] Elepsed time = 262.271mSec [0] std::set erase end [0] HashSet erase start [0] Elepsed time = 117.745mSec [0] HashSet erase end ---------------------------------------------- Comparison for key type std::string (length=8) ---------------------------------------------- [0] std::set insert start [0] Elepsed time = 434.074mSec [0] std::set insert end [0] HashSet insert start [0] Elepsed time = 602.558mSec [0] HashSet insert end [0] std::set find start [0] Elepsed time = 405.215mSec [0] std::set find end [0] HashSet find start [0] Elepsed time = 102.051mSec [0] HashSet find end [0] std::set erase start [0] Elepsed time = 603.113mSec [0] std::set erase end [0] HashSet erase start [0] Elepsed time = 260.250mSec [0] HashSet erase end |
Downloads
・ここをクリックすると、makefile や VC++ プロジェクトなど一式がダウンロードできます。
(2013.05.31 updated)
・2010年5月3日からのダウンロード数：1132
Subversion
・フリーの Subversion ホスティングサービス Assemblaで、ソースコードを管理しています。
Reference
・STLport のハッシュ・コンテナ
・http://pocoproject.org にある Hashing のプレセンテーション。(PDF)
 |
Copyright © 2010 Round Square Inc. All rights reserved. |
|---|
0 Comments.