关于MRu算法的实现研究
这两个月家里事情比较多，公司里负责写战斗和任务模块，身体也不是很好，导致自己在这里的时间所余无几，ICE的文章和我的开源服务器现在都处于暂停的状态。不过我并不想荒废这里，我会继续写下去。最近在群里看有朋友讨论了mru算法，再看ICE里面，有一种类似mru的组件，很有兴趣的看了一下，发现ICE里面的代码貌似只提供了一个框架算法框架，扔东西和加载东西完全凭借自己的算法去实现。想到自己也要用到这样的类，其实确实挺常见的。就利用这两天自己写了一个。测试了一下，速度不敢说非常快，但是我自己觉得还可以，放在这里，希望给需要它的大家一些帮助，由于考虑了跨平台以及简单易用的想法，我并没有在这里类里面使用boost，当然如果你喜欢完全可以把我的map替换之。
这里要感谢stone，7cat和modern对我的帮助。当然，我也在尝试优化其中的部分。不得不说，boost库比我想象的优秀的多，我使用boost库后，速度提升了一倍多，不过为了保持简单性，我在这里没有使用。不过推荐大家如果有条件，还是使用boost替换我的map比较好。
我的设计思路是，用户可以使用我这类，实现一个简单的key-value的对应模式，用户一开始指定一个可以允许的大小，当数据达到上限后，将会自动把最不常用的数据剔除。始终保持数据量在一个可以限制的范围内。
首先，我需要一个链表，来管理我的这些数据之间的被调用关系，这个链表的主要作用就是记录谁是最后没有被访问过的哪个，并将这个数据剔除并替换成我的新数据。写链表都是基本功，这点没啥好说的。
class CListNode
{
public:
CListNode()
{
m_pData = NULL;
m_pNextListNode = NULL;
m_pBeforeListNode = NULL;
};
~CListNode()
{
Close();
};
void Close()
{
if(NULL != m_pData)
{
delete m_pData;
m_pData = NULL;
}
};
void SetNodeData(void* pData)
{
m_pData = pData;
};
void SetNodeNext(CListNode* pListNode)
{
m_pNextListNode = pListNode;
}
void SetNodeBefore(CListNode* pListNode)
{
m_pBeforeListNode = pListNode;
}
void* GetNodeData()
{
return m_pData;
}
CListNode* GetNodeNext()
{
return m_pNextListNode;
}
CListNode* GetNodeBefore()
{
return m_pBeforeListNode;
}
private:
void* m_pData;
CListNode* m_pNextListNode;
CListNode* m_pBeforeListNode;
};
这是一个简单的双向列表节点，没啥好说的。
class CLinkList
{
public:
CLinkList()
{
m_pListNode = NULL;
m_pFirstListNode = NULL;
m_pLastListNode = NULL;
};
~CLinkList()
{
Close();
};
bool Add(CListNode* pListNode, void* pData)
{
if(NULL == pListNode)
{
return false;
}
pListNode->SetNodeData(pData);
if(NULL == m_pFirstListNode)
{
//如果是链表的第一个
m_pListNode = pListNode;
m_pFirstListNode = pListNode;
m_pLastListNode = pListNode;
}
else
{
pListNode->SetNodeBefore(m_pLastListNode);
m_pLastListNode->SetNodeNext(pListNode);
m_pLastListNode = pListNode;
}
return true;
};
bool MoveTop(CListNode* pListNode)
{
if(NULL == pListNode)
{
return false;
}
if(NULL == m_pFirstListNode)
{
return false;
}
if(pListNode == m_pFirstListNode)
{
return true;
}
CListNode* pBefore = pListNode->GetNodeBefore();
CListNode* pNext = pListNode->GetNodeNext();
if(NULL == pBefore)
{
//如果就是第一个
return true;
}
pBefore->SetNodeNext(pNext);
if(NULL != pNext)
{
pNext->SetNodeBefore(pBefore);
}
if(pListNode == m_pLastListNode)
{
if(NULL != pBefore)
{
m_pLastListNode = pBefore;
}
}
pListNode->SetNodeNext(m_pFirstListNode);
pListNode->SetNodeBefore(NULL);
m_pFirstListNode->SetNodeBefore(pListNode);
m_pFirstListNode = pListNode;
return true;
}
bool DelNode(CListNode* pListNode, bool blDel = true)
{
if(NULL == pListNode)
{
return false;
}
CListNode* pBefore = pListNode->GetNodeBefore();
CListNode* pNext = pListNode->GetNodeNext();
if(pBefore != NULL)
{
pBefore->SetNodeNext(pNext);
}
else
{
m_pFirstListNode = pListNode->GetNodeNext();
m_pFirstListNode->SetNodeBefore(NULL);
}
if(pNext != NULL)
{
pNext->SetNodeBefore(pBefore);
}
else
{
m_pLastListNode = pListNode->GetNodeBefore();
m_pLastListNode->SetNodeNext(NULL);
}
if(blDel == true)
{
delete pListNode;
}
pListNode->SetNodeBefore(NULL);
pListNode->SetNodeNext(NULL);
return true;
}
CListNode* GetFirst()
{
return m_pFirstListNode;
}
CListNode* GetLast()
{
return m_pLastListNode;
}
void Display()
{
CListNode* pListNode = NULL;
if(m_pFirstListNode != NULL)
{
pListNode = m_pFirstListNode;
while(pListNode)
{
CListNode* pNextListNode = pListNode->GetNodeNext();
printf("..%s..", pListNode->GetNodeData());
pListNode = pNextListNode;
}
}
}
CListNode* GetLastNode()
{
if(m_pFirstListNode == NULL)
{
return NULL;
}
CListNode* pListNode = m_pLastListNode;
CListNode* pBefor = m_pLastListNode->GetNodeBefore();
if(NULL == pBefor)
{
m_pFirstListNode = NULL;
m_pLastListNode = NULL;
}
else
{
pBefor->SetNodeNext(NULL);
m_pLastListNode = pBefor;
}
pListNode->SetNodeBefore(NULL);
pListNode->SetNodeNext(NULL);
return pListNode;
}
void Close()
{
CListNode* pListNode = NULL;
if(m_pFirstListNode != NULL)
{
pListNode = m_pFirstListNode;
while(pListNode)
{
CListNode* pNextListNode = pListNode->GetNodeNext();
delete pListNode;
pListNode = pNextListNode;
}
}
}
private:
CListNode* m_pListNode;
CListNode* m_pFirstListNode;
CListNode* m_pLastListNode;
};
这是一个简单的链表，不同的是我提供了一个moveTop的方法，当我的key被访问的时候，我会调用这个方法把这个数据放在链表的最前面，当然，当指定的容器达到上限的时候，我会从链表尾部删除节点，并插入新节点。
为了保持通用性，我用模板重载了一个stl map类，来满足我的功能这个map完全可以用boost去替换，当然，链表也一样的。
template <class Key, class T>
class CMapTemplate
{
。。。。。
}
在这里我遇到了一个挺烦的难题，那就是我要把我的node和key做一一对应，通过key能找到指定的node，还有就是给定一个node删除指定的key，为了减少循环，我没有采用遍历链表的方法，因为当数据量较大的时候，遍历时间成本是较大的。map的查找比较高效，于是就用它了。用空间换时间。
typedef map<CListNode*, Key> mapNode2Key; //定义链表和Key的对应关系
typedef map<Key, CListNode*> mapKey2Node; //定义链表和Key的对应关系
我的这个类实际有3个map，用户初始化的时候，必须指定容器的大小。我会根据这个大小，初始化出一批node节点，当使用时候分配给对应的key，这样的话，当有大量数据需要淘汰的时候，程序不用反复的new和delete。
测试了一下，在我的笔记本下，10万条大概是4秒左右(DEBUG)，在服务器上或许能更快，7cat弄出来了一个0.XX秒，不知道是怎么做到的，或许和机器相关吧。一样的代码。
把测试代码和类贴上来，实际就两个.h。
呵呵，希望对大家有所帮助，另外就是看看大家的意见。或许有更优的方法，欢迎讨论。
MRu算法代码MruList.zip在Linux公社的1号FTP服务器里，下载地址：
FTP地址：ftp://www.linuxidc.com
在 2011年LinuxIDC.com\7月\多级缓冲的服务器数据服务机制实现