前段时间给N年前的一些代码code review，其中涉及到了一个人机博弈的程序。人机博弈中有一个很重要的结构，就是优先队列，其作用的是能够随机的insert一些数据，并保证随时能获得最小(大)的点，其实该结构在大部分的图算法中（包括寻路问题）也很常用。我原来的代码使用heap实现的，不过最近看了一篇paper，是描述《帝国时代》游戏中寻路算法的数据结构的，很是新颖，其用线性表+缓存的结构就可以达到相当快的速度，于是想拿它来试试，看看它和堆哪个快。结果很失望，还是堆快，而且快的不是一星半点，当然也许在特定领域会有不同的表现。
    为了完善该paper的思想，我决定对这个结构进行改进，看看能不能接近或者超过堆。先看看堆的优先队列是如何实现的，我这里使用STL里面的结构：
class PriorityQueueHeap
{
private:
  vector<int> vec;
public:
  int ExtractMin();
  void Insert(const int value);
  void Display(){}
  bool IsEmpty(){return vec.empty();}
};
void PriorityQueueHeap::Insert(const int value)
{
vec.push_back(value);
push_heap(vec.begin(),vec.end(),greater<int>());
}
int PriorityQueueHeap::ExtractMin()
{
pop_heap(vec.begin(),vec.end(),greater<int>());
int min=vec.back();
vec.pop_back();
return min;
}
    接下来，我开始对线性表的结构进行改进，首先将固定缓存进行扩展，变成了动态缓存，在做了这个改进后，发现性能有显著提高，大约相当于STL Heap版的60%，这当然是不令人满意的；而后，利用桶排序的思想分割线性表并结合动态缓存修改算法，经过一系列精心的优化（比如减少函数调用次数，利用内联等等）后，惊人的效果出现了，测试表示改进后的时间比STL要快了将近30%，测试程序如下：
srand((unsigned)time(NULL));
for(int k=0;k<1;k++){
 KobePriorityQueue pq1; (PriorityQueueHeap pq1;)
     for(int i=0;i<=100000000;i++){
     int value=rand()%16777216;
     pq1.Insert(value);
     if(!pq1.IsEmpty()&&rand()%8==1)
        pq1.ExtractMin();
     }//end for i
}//end for k
    KobePriorityQueue是经过我改进后的结构，PriorityQueueHeap是STL最小堆实现，测试程序会不停的插入节点，并随机取最小点，随机数1/8的来源是因为大多数寻路问题（棋盘问题）新增节点和删除节点的比是8。测试结果如下(linux 4核,4G内存)：

Scale	Loop	STL HeapPQ(average sec)	KobePQ(average sec)	KobePQ(best sec)	percentage comparison
1000	10000	1.222	2.79	1.221	-0.08%
10000	1000	1.298	1.406	1.261	2.93%
100000	100	1.433	1.192	1.159	23.64%
1000000	10	1.535	1.214	1.214	26.44%
10000000	1	1.652	1.293	1.265	30.6%

    可见，在缺省参数下，十万级以上KobePriorityQueue比STL版本要快了25%，在10万级以下应用，通过调整参数也可以获得和STL相当的效率。当然这里的弱点就是在某些应用时，需要调节算法参数，使得其不像STL那样稳定通用（毕竟堆的操作效率基本都是logN，使得其时间消耗很稳定快速）。另，根据CLRS，有一种叫FIB heap的结构在插入时可以比最小堆更快，平摊获得O(1)的效率，根据其wiki链接，也下了一份其实现做比较，但结果很令人遗憾，其方法的速度比heap和KobePQ要慢了好几个数量级，当然不排重是代码编写的问题。
    总之，和C++和Java都采用的以堆实现的优先队列算法比较，KobePriorityQueue基本表现得略胜一筹，在某些特定要求速度的领域，可以代替STL Heap。当然在要求稳定性的领域，还是用STL更安全些。

根据我上篇提到的boost::object_pool的一些问题，我试着把object_pool做了一些改进，改进完的性能测试如下（测试环境linux服务器,4G内存，4核CPU(3052MHz)）
#include "kobe_object_pool.hpp"
using namespace std;
using namespace boost;
//--------------------------------------------------------------
class SS
{
public:
int value;
float value2;
SS(){}
};
//--------------------------------------------------------------
int main(int agrc,char** argv)
{
boost::kobe_object_pool<SS,boost::default_user_allocator_new_delete> my_pool;
int test_range=10000000;
for(int i=0;i<test_range;i++)
    {
     SS* p=my_pool.construct();
     my_pool.destroy(p);
    }
real    0m0.049s
user    0m0.040s
sys     0m0.000s
//--------------------------------------------------------------
boost::object_pool<SS> my_pool;
for(int i=0;i<test_range;i++)
    {
     SS* p=my_pool.construct();
     my_pool.destroy(p);
    }
real    0m0.125s
user    0m0.120s
sys     0m0.000s
//--------------------------------------------------------------
for(int i=0;i<test_range;i++)
    {
     SS* p=new SS();
     delete p;
    }
real    0m0.695s
user    0m0.690s
sys     0m0.000s
//--------------------------------------------------------------
return 0;
}

可以看见，使用我的kobe_object_pool要比boost_object_pool快了1倍多，比常规的内存分配快了一个数量级。这里有一个说明：
kobe_object_pool要求使用者调用完construct后一定要调用destroy，以保证对象的析构可以被正常唤起，否则将会有隐患的资源泄漏；而boost::object_pool则不然，它可以在pool析构时释放用户所遗留析构的object。这也是boost::object_pool的一个优点吧，但如果用户可以保证唤起析构，那么使用kobe_object_pool还是有性能优势的。