关于MRu算法的实现研究

freeeyes

这两个月家里事情比较多，公司里负责写战斗和任务模块，身体也不是很好，导致自己在这里的时间所余无几，ICE的文章和我的开源服务器现在都处于暂停的状态。不过我并不想荒废这里，我会继续写下去。最近在群里看有朋友讨论了mru算法，再看ICE里面，有一种类似mru的组件，很有兴趣的看了一下，发现ICE里面的代码貌似只提供了一个框架算法框架，扔东西和加载东西完全凭借自己的算法去实现。想到自己也要用到这样的类，其实确实挺常见的。就利用这两天自己写了一个。测试了一下，速度不敢说非常快，但是我自己觉得还可以，放在这里，希望给需要它的大家一些帮助，由于考虑了跨平台以及简单易用的想法，我并没有在这里类里面使用boost，当然如果你喜欢完全可以把我的map替换之。
这里要感谢stone，7cat和modern对我的帮助。当然，我也在尝试优化其中的部分。不得不说，boost库比我想象的优秀的多，我使用boost库后，速度提升了一倍多，不过为了保持简单性，我在这里没有使用。不过推荐大家如果有条件，还是使用boost替换我的map比较好。
我的设计思路是，用户可以使用我这类，实现一个简单的key-value的对应模式，用户一开始指定一个可以允许的大小，当数据达到上限后，将会自动把最不常用的数据剔除。始终保持数据量在一个可以限制的范围内。

首先，我需要一个链表，来管理我的这些数据之间的被调用关系，这个链表的主要作用就是记录谁是最后没有被访问过的哪个，并将这个数据剔除并替换成我的新数据。写链表都是基本功，这点没啥好说的。

1. class CListNode
2. {
3. public:
4.         CListNode()
5.         {
6.                 m_pData           = NULL;
7.                 m_pNextListNode   = NULL;
8.                 m_pBeforeListNode = NULL;
9.         };
11.         ~CListNode()
12.         {
13.                 Close();
14.         };
16.         void Close()
17.         {
18.                 if(NULL != m_pData)
19.                 {
20.                         delete m_pData;
21.                         m_pData = NULL;
22.                 }
23.         };
25.         void SetNodeData(void* pData)
26.         {
27.                 m_pData = pData;
28.         };
30.         void SetNodeNext(CListNode* pListNode)
31.         {
32.                 m_pNextListNode = pListNode;
33.         }
35.         void SetNodeBefore(CListNode* pListNode)
36.         {
37.                 m_pBeforeListNode = pListNode;
38.         }
40.         void* GetNodeData()
41.         {
42.                 return m_pData;
43.         }
45.         CListNode* GetNodeNext()
46.         {
47.                 return m_pNextListNode;
48.         }
50.         CListNode* GetNodeBefore()
51.         {
52.                 return m_pBeforeListNode;
53.         }
55. private:
56.         void* m_pData;
57.         CListNode* m_pNextListNode;
58.         CListNode* m_pBeforeListNode;
59. };

复制代码

这是一个简单的双向列表节点，没啥好说的。

1. class CLinkList
2. {
3. public:
4.         CLinkList()
5.         {
6.                 m_pListNode      = NULL;
7.                 m_pFirstListNode = NULL;
8.                 m_pLastListNode  = NULL;
9.         };
11.         ~CLinkList()
12.         {
13.                 Close();
14.         };
16.         bool Add(CListNode* pListNode, void* pData)
17.         {
18.                 if(NULL == pListNode)
19.                 {
20.                         return false;
21.                 }
23.                 pListNode->SetNodeData(pData);
24.                 if(NULL == m_pFirstListNode)
25.                 {
26.                         //如果是链表的第一个
27.                         m_pListNode      = pListNode;
28.                         m_pFirstListNode = pListNode;
29.                         m_pLastListNode  = pListNode;
30.                 }
31.                 else
32.                 {
33.                         pListNode->SetNodeBefore(m_pLastListNode);
34.                         m_pLastListNode->SetNodeNext(pListNode);
35.                         m_pLastListNode = pListNode;
36.                 }
38.                 return true;
39.         };
41.         bool MoveTop(CListNode* pListNode)
42.         {
43.                 if(NULL == pListNode)
44.                 {
45.                         return false;
46.                 }
48.                 if(NULL == m_pFirstListNode)
49.                 {
50.                         return false;
51.                 }
53.                 if(pListNode == m_pFirstListNode)
54.                 {
55.                         return true;
56.                 }
58.                 CListNode* pBefore = pListNode->GetNodeBefore();
59.                 CListNode* pNext   = pListNode->GetNodeNext();
61.                 if(NULL == pBefore)
62.                 {
63.                         //如果就是第一个
64.                         return true;
65.                 }
67.                 pBefore->SetNodeNext(pNext);
68.                 if(NULL != pNext)
69.                 {
70.                         pNext->SetNodeBefore(pBefore);
71.                 }
73.                 if(pListNode == m_pLastListNode)
74.                 {
75.                         if(NULL != pBefore)
76.                         {
77.                                 m_pLastListNode = pBefore;
78.                         }
79.                 }
81.                 pListNode->SetNodeNext(m_pFirstListNode);
82.                 pListNode->SetNodeBefore(NULL);
83.                 m_pFirstListNode->SetNodeBefore(pListNode);
84.                 m_pFirstListNode = pListNode;
85.                 return true;
86.         }
88.         bool DelNode(CListNode* pListNode, bool blDel = true)
89.         {
90.                 if(NULL == pListNode)
91.                 {
92.                         return false;
93.                 }
95.                 CListNode* pBefore = pListNode->GetNodeBefore();
96.                 CListNode* pNext   = pListNode->GetNodeNext();
98.                 if(pBefore != NULL)
99.                 {
100.                         pBefore->SetNodeNext(pNext);
101.                 }
102.                 else
103.                 {
104.                         m_pFirstListNode = pListNode->GetNodeNext();
105.                         m_pFirstListNode->SetNodeBefore(NULL);
106.                 }
108.                 if(pNext != NULL)
109.                 {
110.                         pNext->SetNodeBefore(pBefore);
111.                 }
112.                 else
113.                 {
114.                         m_pLastListNode = pListNode->GetNodeBefore();
115.                         m_pLastListNode->SetNodeNext(NULL);
116.                 }
118.                 if(blDel == true)
119.                 {
120.                         delete pListNode;
121.                 }
123.                 pListNode->SetNodeBefore(NULL);
124.                 pListNode->SetNodeNext(NULL);
125.                 return true;
126.         }
128.         CListNode* GetFirst()
129.         {
130.                 return m_pFirstListNode;
131.         }
133.         CListNode* GetLast()
134.         {
135.                 return m_pLastListNode;
136.         }
138.         void Display()
139.         {
140.                 CListNode* pListNode = NULL;
141.                 if(m_pFirstListNode != NULL)
142.                 {
143.                         pListNode = m_pFirstListNode;
144.                         while(pListNode)
145.                         {
146.                                 CListNode* pNextListNode = pListNode->GetNodeNext();
147.                                 printf("..%s..", pListNode->GetNodeData());
148.                                 pListNode = pNextListNode;
149.                         }
150.                 }
151.         }
153.         CListNode* GetLastNode()
154.         {
155.                 if(m_pFirstListNode == NULL)
156.                 {
157.                         return NULL;
158.                 }
160.                 CListNode* pListNode = m_pLastListNode;
161.                 CListNode* pBefor = m_pLastListNode->GetNodeBefore();
162.                 if(NULL == pBefor)
163.                 {
164.                         m_pFirstListNode = NULL;
165.                         m_pLastListNode  = NULL;
166.                 }
167.                 else
168.                 {
169.                         pBefor->SetNodeNext(NULL);
170.                         m_pLastListNode = pBefor;
171.                 }
173.                 pListNode->SetNodeBefore(NULL);
174.                 pListNode->SetNodeNext(NULL);
175.                 return pListNode;
176.         }
178.         void Close()
179.         {
180.                 CListNode* pListNode = NULL;
181.                 if(m_pFirstListNode != NULL)
182.                 {
183.                         pListNode = m_pFirstListNode;
184.                         while(pListNode)
185.                         {
186.                                 CListNode* pNextListNode = pListNode->GetNodeNext();
187.                                 delete pListNode;
188.                                 pListNode = pNextListNode;
189.                         }
190.                 }
191.         }
193. private:
194.         CListNode* m_pListNode;
195.         CListNode* m_pFirstListNode;
196.         CListNode* m_pLastListNode;
197. };

复制代码

这是一个简单的链表，不同的是我提供了一个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。
呵呵，希望对大家有所帮助，另外就是看看大家的意见。或许有更优的方法，欢迎讨论。

xjh_001

#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秒
以上是在我的笔记本上的测试结果

freeeyes

很棒！
               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，它等于队头
这里很巧妙

cary

楼主用的debug模式运行的吧