Posted on 2005-12-22 20:42
小明 閱讀(3834)
評論(8) 編輯 收藏 引用 所屬分類:
C/C++
對于性能優(yōu)化，相信喜歡C++的人都是比較重視效率。我準(zhǔn)備寫一個系列，主要是基于我的一些實(shí)踐，至于理論上的東西，不是我的重點(diǎn)。我也講不出來一堆道理:-)。我所說的例子，都將是我以前所遇到的一些案例，記錄一下思路，拿出來跟大家share。
在C++程序中，自從有了STL,很少有人去自己去設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)，當(dāng)然大部分情況STL的效率都是可以的。萬事都有例外。
我接觸到一個需求，是根據(jù)手機(jī)號碼的號段表(位數(shù)不定，一般是七八位）來查出手機(jī)號碼所在的地區(qū)。
比如
1315156 南京
13812345 北京
1366789 上海
025 南京
一種可能的方案是設(shè)計(jì)多個hashmap
map<int,string> seg8; map<int,string> seg7; map<int,string> seg3; ...
每個map分別對應(yīng)不同的位數(shù)。對于一個phone,分別在這些map中查找
但是效率不行。
這里面有個關(guān)鍵，因?yàn)槭謾C(jī)號碼都是數(shù)字，我們可以設(shè)計(jì)出一棵樹，每個節(jié)點(diǎn)都是0-9，他可以有10個節(jié)點(diǎn)，葉子節(jié)點(diǎn)我們就可以儲存數(shù)據(jù)。迅速在大腦里想象一個這樣的模型。
還是看代碼比較明了。 十叉樹
#if !defined __TREE10__
#define __TREE10__
#pragma warning(disable:4786)
namespace sandy
{
namespace Private
{
template<class VALUE>
struct __Node10 //節(jié)點(diǎn)struct
{
typedef __Node10<VALUE>* POINTER;
VALUE * data; //數(shù)據(jù)
POINTER ptr[10]; //子節(jié)點(diǎn)
__Node10():data(0)
{
memset(ptr,0,sizeof(POINTER)*10);
}
};
}
template<typename VALUE>
class CTree10
{
typedef Private::__Node10<VALUE> NODE;
private:
long m_lcount; //插入的數(shù)據(jù)數(shù)量
long m_lnodecount; //節(jié)點(diǎn)數(shù)
NODE* m_proot; //根結(jié)點(diǎn)指針
public:
CTree10():m_lcount(0),m_lnodecount(0),m_proot(CreateNode()) //notice:Keep order with their declare
{
}
~CTree10()
{
DestroyAll();
}
void DestroyAll()
{
for(short i =0;i<10;++i)
{
if(m_proot->ptr[i]!=0)
{
Remove(m_proot->ptr[i]);
m_proot->ptr[i] = 0;
}
}
}
bool Insert(const char*pKey,const VALUE &data) //插入節(jié)點(diǎn)
{
assert(pKey!=0);
NODE * pNode = m_proot;
NODE * pChildNode =0;
char c = 0;
for(unsigned int i=0;i<strlen(pKey);++i)
{
c = pKey[i]; if(c<'0' || c>'9') return false;
pChildNode = pNode->ptr[(c-'0')];
if(pChildNode == 0) //not build
{
pChildNode = pNode->ptr[(c-'0')] = CreateNode();//create a new child
}
pNode = pChildNode ;//change node to child node
}
if(pNode->data == 0) //empty
{
pNode->data = new VALUE(data);
++m_lcount;
return true;
}
else//already inserted
{
return false;
}
}
bool Lookup(const char*pKey,VALUE &data,bool strick = true)
{
assert(pKey!=0);
NODE * pNode = m_proot;
NODE * pChildNode =0;
char c = 0;
for(unsigned int i=0;i<strlen(pKey);++i)
{
c = pKey[i]; if(c<'0' || c>'9') return false;
pChildNode = pNode->ptr[(c-'0')];
if(pChildNode!=0)
{
pNode = pChildNode;
}
else // can't find
{
if(!strick)
{
break;
}
return false;
}
}
if(pNode->data != 0) //already inserted
{
data = *(pNode->data);
return true;
}
else // no inserted
{
return false;
}
}
private:
NODE *CreateNode()
{
NODE *pNewNode = new NODE();
assert(pNewNode!= 0);
++m_lnodecount;
return pNewNode;
}
void Remove(NODE *pNode)
{
assert(pNode!=0);
for( short i = 0 ; i < 10 ; i ++ )
{
if( pNode -> ptr[ i ] )
Remove( pNode -> ptr[ i ] );
}
if(pNode->data!=0)
{
delete pNode->data;
--m_lcount;
}
--m_lnodecount;
delete pNode;
}
};
}
#endif
這個Tree10我在vc6下測試的結(jié)果：
插入速度比std::map快3倍，查詢速度則是std::map的10倍