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);
            
forshort 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

posted on 2006-01-12 00:27 zmj 阅读(515) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理