Poco::HashSet

STL に取り入れられなかったものの一つに Hash があり、それを使った set や map が STLportC++0x, Boost で取り込まれていますが、Poco にも Poco::HashSetPoco::HashMap として実装されています。

Poco::HashSetPoco::HashMap は、std::setstd::map と(iterator が Iteratorだったりする以外は)ほとんど同様に使えるので、今回は使い方ではなく、std::setPoco::HashSet の速度を比較してみたいと思います。

HashSetTest.cpp

Poco::Random で 262,144 個の乱数を発生させ、
  そのまま Poco::UInt32 をキーにした場合
  16 進数の文字列(8 文字)に変換した std::string をキーにした場合
 のそれぞれで、
  insert を 262,144 回
  find を 262,144 回
  erase を 262,144 回
 順次実行して、std::setPoco::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) で実行。

Poco::UInt32(整数)キーでの比較
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::string (length=8) キーでの比較
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日からのダウンロード数:817

Subversion

・フリーの Subversion ホスティングサービス Assemblaで、ソースコードを管理しています。

Reference


STLport のハッシュ・コンテナ
http://pocoproject.org にある Hashing のプレセンテーション。(PDF)

Powered by POCO Copyright © 2010 Round Square Inc. All rights reserved.


Leave a Comment


NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>