Posted on 2005-12-22 20:42
小明 阅读(3821)
评论(8) 编辑 收藏 引用 所属分类:
C/C++
对于性能优化，相信喜欢C++的人都是比较重视效率。我准备写一个系列，主要是基于我的一些实践，至于理论上的东西，不是我的重点。我也讲不出来一堆道理:-)。我所说的例子，都将是我以前所遇到的一些案例，记录一下思路，拿出来跟大家share。
在C++程序中，自从有了STL,很少有人去自己去设计数据结构，当然大部分情况STL的效率都是可以的。万事都有例外。
我接触到一个需求，是根据手机号码的号段表(位数不定，一般是七八位）来查出手机号码所在的地区。
比如
1315156 南京
13812345 北京
1366789 上海
025 南京
一种可能的方案是设计多个hashmap
map<int,string> seg8; map<int,string> seg7; map<int,string> seg3; ...
每个map分别对应不同的位数。对于一个phone,分别在这些map中查找
但是效率不行。
这里面有个关键，因为手机号码都是数字，我们可以设计出一棵树，每个节点都是0-9，他可以有10个节点，叶子节点我们就可以储存数据。迅速在大脑里想象一个这样的模型。
还是看代码比较明了。 十叉树
#if !defined __TREE10__
#define __TREE10__
#pragma warning(disable:4786)
namespace sandy
{
namespace Private
{
template<class VALUE>
struct __Node10 //节点struct
{
typedef __Node10<VALUE>* POINTER;
VALUE * data; //数据
POINTER ptr[10]; //子节点
__Node10():data(0)
{
memset(ptr,0,sizeof(POINTER)*10);
}
};
}
template<typename VALUE>
class CTree10
{
typedef Private::__Node10<VALUE> NODE;
private:
long m_lcount; //插入的数据数量
long m_lnodecount; //节点数
NODE* m_proot; //根结点指针
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) //插入节点
{
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下测试的结果：
插入速度比std::map快3倍，查询速度则是std::map的10倍