w.rdc.sae.sina.com.cn:3307|nj41yyozkz|nj41yyozkz 优先队列 « SAE云计算
Twitter FaceBook
Home
Sina App Engine

Displaying Tag '优先队列'

Posted by kobe, and filed under 计算机理论

    前段时间给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更安全些。

前段时间给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更安全些。

13th 四 2010
illuminati
illuminati
 
Designed by