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

还东国的博客

行之苟有恒,久久自芬芳

 
 
 

日志

 
 

(转)从union到merge,个人对算法进化的思考  

2011-11-03 14:41:14|  分类: 算法及数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
从union到merge,个人对算法进化的思考(1)
 (2011-04-18 20:25:13)
(转)从union到merge,个人对算法进化的思考 - 还东国 - 还东国的博客转载
标签: 
算法
 
merge
 
杂谈

这几天闲的没事翻了翻那本严蔚敏的数据结构,里面地头几章介绍了算法:union,merge。自以为对merge已经比较熟悉了,没想到现在回头看这本书,心里真是别有一番滋味啊,现在就把这些想法记录下来,给大家分享。
 union:伪代码:
  void union(list &la,list lb)
  {
    la_len=listlength(la);lb_len=listlength(lb);
     for(i=1;i<=lb_len;i++)
     {
       getelem(lb,i,e);
       if(!locateElem(la,e,equal)) listinsert(la,++la_len,e);
     }
  }
通俗地:想要把球的两个线性表的并,我们对扫描其中一个进行扫描,针对当前正在扫描的元素a,如果他不存在于另外一个表中,我们就把a插入到那个表中,显然这个算法的复杂度是:O(la*lb).
现在的问题是,我们如何来对这个求并的操作进行优化呢,能不能降低一个数量级呢?
目前的方法里面,我们对每一个当前扫描的元素,都要在另外的表中进行一遍全表的扫描,来找出是否存在当前元素,显然我们如果要降低复杂度,就要从如何避免进行全表扫描入手。
按照常规的思路,要对算法进行优化,我们就是要对源数据进行首先的处理,
  使得被处理过的数据具有某种性质.(例如排序之后,需要处理的数据就有了有序的性质)
  提前计算并保存下一定的在真正处理的时候的有用信息以供以后使用.(例如对元素建立索引:我们可以在表上建立一个查找树,这样查找操作就会变得轻易的很(当然要建立索引很多情况也要进行排序的!)或者我们可以对当前表建立一个hash索引,这个索引应该不会需要排序,我们使用一定的hash函数,例如直接使用anscii码值当然这是一个错误的也很不好的选择,可能会有很多的冲突!)
这样在最后真正的处理的时候,例如在这个例子里面我们进行的求并的时候要进行寻找当前元素时候在另外一个表中。
    对于第一种情况,我们知道查找当前元素是否在一个表中我们使用了元素之间的比较的操作,如果比较元素和表中当前元素相同,或者不相同,我们采取相应的操作。然而,我们是否可以利用不相同的(大于,小于)情况加快查找速度呢。当然,假设当前表是有序的,那么如果我们在查找过程中发现从开始当前表就不可能包含比较元素:例如当前表第一个元素就比比较元素大,而当前表是递增的,反之亦然。我们就可以结束搜索了。然而这只是简单的优化,并没有什么实质的性能增长。我们在比较过程中,开始当前表如果比比较元素小,当我们第一次碰到当前表元素比比较元素大的时候,就可以确定,这个表肯定不包含比较元素。
    对于同一种情况,我们依据上面的讨论,对要进行全表扫描的方法进行了优化,那么这样的优化是不是已经到顶了?是不是还有优化的空间呢?
    我们依然是通过对某一个表进行排序得到的性能的提升,现在我们试一试对参与操作的两个(所有)表都进行排序。我们对一个表进行扫描:取出比较元素。如果当前的比较元素和另外的表的当前元素比较,更小。那么在整个并集合里面可定包含当前元素。如果,更大,那么结果并集合可能包含比较元素;如果相等,那么我们从比较元素和当前元素之间选一个加入并集合就可以了。由于两个表是对等的,所以我们可以根据这个原理,交替的从两个表中选择比较元素。于是所谓的merge算法形成了:
merge :伪代码:
void merge_sq(list a, list b, list&c)
{
   pa=a.elem;pb=b.elem;
   c.listsize=c.length=a.length+b.length;
   pc=c.elem=(elemtype*)malloc(c,listsize*sizeof(elemtype));
   if(!pc)exit(overflow);
   pa_last=a.elem+a.length-1;
   pb_last=b.elem+b.length-1;
   while(pa<=pa_last&&pb<=pb_last)
   {
     if(*pa<=*pb) *pc++=*pa++;
     else *pc++=*pb++;
   }
   while(pa<=pa_last) *pc++=*pa++;
   while(pb<=pb_last) *pc++=*pb++;
}
  评论这张
 
阅读(537)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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