关于MRu算法的实现研究
本帖最后由 freeeyes 于 2010-11-4 14:43 编辑这两个月家里事情比较多，公司里负责写战斗和任务模块，身体也不是很好，导致自己在这里的时间所余无几，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。
呵呵，希望对大家有所帮助，另外就是看看大家的意见。或许有更优的方法，欢迎讨论。
#include <list>
#include <assert.h>
template<class K, class V>
class McMruContainter
{
typedef list<K*> LIST_KEY;//经常访问队列，经常访问的在前面
typedef typename LIST_KEY::iterator LIST_KEY_ITERATOR;
struct MsItem//map元素
{
V* data;//数据指针
LIST_KEY_ITERATOR key_pos;//在经常访问队列中的位置，便于通过元素在经常访问队列中找到相应的元素
};
typedef map<K, MsItem> MAP_DATA;
MAP_DATA map_data;//data表
LIST_KEY list_key;//经常访问队列
int m_nMaxCount;//最大元素个数
public:
McMruContainter(int nCount)
{
m_nMaxCount = nCount;
}
~McMruContainter()
{
Clear();
}
bool AddMapData(const K& k, V* v)
{
MAP_DATA::iterator it = map_data.find(k);
if(it != map_data.end())//已经存在
return false;
int nSize = (int)map_data.size();
if(nSize >= m_nMaxCount)//超过当前容器的大小
{
//释放最后一个元素
K* last = *list_key.rbegin();//最后一个元素的key指针
list_key.pop_back();//经常访问队列中删除最后一个元素
it = map_data.find(*last);//data表中查找相应的元素
assert(it != map_data.end());//一定能找到
delete it->second.data;//清除相应的数据
map_data.erase(it);//data表中删除相应的元素
}
//现在肯定有空间了
list_key.push_front(NULL);//新增的总是在经常访问队列的头部
LIST_KEY_ITERATOR new_key_pos = list_key.begin();//获取k在列表中的位置
MsItem item;
item.data = v;
item.key_pos = new_key_pos;
MAP_DATA::iterator itNew = (map_data.insert(make_pair(k, item))).first;//在data表中增加元素
*new_key_pos = const_cast<K*>(&(itNew->first));//将新的元素的k的地址，赋值到新的经常访问队列中去
//一开始用的是NULL，因为那时还不知道key的地址，现在知道了，在data表中，为新元素分配了空间来存放k和v
return true;
}
bool DelMapData(const K& k)
{
MAP_DATA::iterator it = map_data.find(k);
if(it == map_data.end())//不存在
return false;
MsItem& item = it->second;
delete item.data;//删除相应的元素的数据
list_key.erase(item.key_pos);//删除经常访问队列中的元素
map_data.erase(it);//删除data表中的元素
return true;
}
V* SearchMapData(const K& k)
{
MAP_DATA::iterator it = map_data.find(k);
if(it == map_data.end())//不存在
return NULL;
MsItem& item = it->second;
LIST_KEY_ITERATOR it_key = item.key_pos;
list_key.push_front(*it_key);//将当前的值插入到队头
list_key.erase(it_key);//删除当前的元素。这两句相当于将当前元素移到了队头
item.key_pos = list_key.begin();//修改item中的key_pos，它等于队头
return item.data;//返回数据指针
}
void Clear()
{
MAP_DATA::iterator itEnd = map_data.end();
for(MAP_DATA::iterator it = map_data.begin(); it != itEnd; it++)
delete it->second.data;
map_data.clear();
list_key.clear();
}
int GetSize()
{
return (int)map_data.size();
}
};
上述代码复制到"MapTemplate.h”中，其实是CMapTemplate的一种实现方式。
CMapTemplate大概6.8秒
McMruContainter大概4.0秒
以上是在我的笔记本上的测试结果 很棒！
MsItem& item = it->second;
LIST_KEY_ITERATOR it_key = item.key_pos;
list_key.push_front(*it_key);//将当前的值插入到队头
list_key.erase(it_key);//删除当前的元素。这两句相当于将当前元素移到了队头
item.key_pos = list_key.begin();//修改item中的key_pos，它等于队头
这里很巧妙 楼主用的debug模式运行的吧
页:
[1]