注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

初识斐波那契堆  

2010-08-18 10:33:16|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Fibonacci堆以前只是“传说中”的产物,基本没听说谁敢在比赛中使用,并且听说它:
1.理论复杂度超好
2.常数超级大
正好我读《Introduction To Algorithms》到了fibonacci堆这一节,便打算尝试一下。
总体感受:代码超长(107行)
http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/Fibheap/Fibheap.cpp
并且如果不是照着《算法导论》抄的话,我觉得我不太可能把它调出来。
fibheap之所以令人着迷,原因在于它优秀的均摊时间复杂度:
插入、减小一个元素、合并两个堆:O(1)
千真万确,是常数!
只有弹出最小元素的复杂度是O(log(n))
fibheap的一个典型应用就是加速Dijkstra算法。
它使得dijkstra算法时间复杂度变为O(VlogV+E),而如果只用
二叉堆,那么复杂度是O((V+E)logV),请注意,对于E=O(V*V)的超级稠密图,二叉堆的表现可能不如
不用堆的朴素实现:O(V*V+E)
我打算着手实验一下,看看fibheap和二叉堆在10000个点、100000000条边的超级稠密图上的表现。
首先是随机图。
因为我不想让读入成为瓶颈,所以我使用了一个函数来计算边的值而不读入它。
int E(int x,int y){ecnt++;
if (x==y)return 0;
int r=x*13687+y*68877+x*y*3611+x*x*6541+y*y*6329;
return (r&0x7fffffff)%10000001+1;
}
至少看起来是挺随机的。同时,我还把最终的运行时间减掉计算这么多边权花费的时间,来计算“真正”的用时。
http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/Fibheap/dijkstra^_fh.cpp
http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/Fibheap/dijkstra^_bh.cpp
为了抵消掉我的代码糟糕的常数,我在编译时加入了-O2的选项。
结果呢?
二叉堆:827ms
fibheap:890ms
注意:算法执行的时候只大约进行了7.7万次减小标号的调整,所以
fibheap和二叉堆的实现实际上没有体现出复杂度的差异。
我们只能得出以下结论:
fibheap的常数并不是特别的大。
接下来嘛,就是“二叉堆版dijkstra”专杀图了:
int E(int x,int y){ecnt++;
if (x==y)return 0;
if (x>y){int t=x;x=y;y=t;}
if (y==x+1)return 1;
return (100000-x-x)*10000+10000-y;
}
可以想象,算法执行的过程中疯狂地减小标号。
二叉堆:12032ms
fibheap:3578ms
这里大约可以看出复杂度导致的差异,但是,就像我们看到的那样,
差距并不是很大,所以fibheap也只能在更大的图上可以明显甩开二叉堆。
但是,过大的图会导致测评极其困难。所以,在OI中,fibheap加速dijkstra的应用很尴尬:
点数多的稀疏图,跑得肯定不如二叉堆,
点数少的稠密图,拉不开差距。

然而,在算法艺术中,fibheap优秀的特性为我们带来了欣喜。
通过它,我们可以把很多算法的时间复杂度压缩到极致。

之后,我想实际测一下fibheap的常数到底如何。
这里的应用是:堆排序。
当然,如果只是排序,那么fibheap在结构上就退化成了BinomialHeap,不过常数的插入操作得以维持。
同时,我也“邀请”左偏树、random堆参与堆排序的“常数大比拼”
http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/Fibheap/sort^_rh.cpp
//random堆
http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/Fibheap/sort^_lh.cpp
//左偏树
同样,编译选项加入-O2
排序1000000个随机数
二叉堆: 2281ms
左偏树: 2593ms
fibheap: 3015ms
random堆: 3031ms
可以看出,fibheap的常数并不是那样的让人担忧。虽然它的操作很复杂,但常数仅仅多了一半而已。

看一眼代码量(仅堆的实现函数):
random堆: 158 byte
左偏树: 312 byte
二叉堆: 452 byte
fibheap: 2010byte

当然,random堆一定要使用自己手写的非常快的rand才行。
fibheap在数量级上”领先“了其他数据结构。

总结一下,fibheap的常数并不是特别大,但它的优异的复杂度优势也非常难以发挥。
fibheap更多的是一个理论上的工具,它动辄上百行的代码量,只能让OIer望洋兴叹了。

盼望哪天stl里能有一个fibonacci堆的模板(呵呵O(∩_∩)O~)
  评论这张
 
阅读(3297)| 评论(4)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017