Jul 17

重拾线段树 不指定

felix021 @ 2016-7-17 22:46 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(7033) | Via 本站原创 | |
  前几天讨论遇到一个涉及区间覆盖的数据统计,发现很适合使用线段树来解决,于是重新回顾了一下这个好几年前学过的东西,凭着残存的理解,好了好久才勉强写了出来,感觉自己确实是没有搞算法的天赋,在边界处理的时候磕磕碰碰的,需要改好几次才能写对,不够干净利落。

  不过能从繁杂的业务中抽出来写写纯粹的数据结构和算法,有点回到学校的状态,感觉也蛮不错。

  以前在学校折腾算法的时候,从yyt同学的分享的ppt学到了这个数据结构,印象比较深的是,ppt上说,对于一个长度是 x 的线段,使用数组(元素 i 的左右节点分别是 2*i 和 2*i+1 )来记录的话,需要大小约为 3*x 的数组,但是在实际做题的时候却发现越界了,后来仔细去挖这个地方,才发现,其实应该是找到一个 y = 2^n 满足 2^(n-1) < x <= 2^n,所需的数组长度为 2y 。

  这次是先写了一个C++的class(偷懒用的struct),配合一些c-style的函数,让python用ctypes载入使用。然后兴起写了个Python的版本对比,跑了个简单的case,发现性能居然相差200+倍,做了一些改进,才领悟到,对于python来说,其实用数组建树比起直接用对象指针关联建树并没有太大优势,而用对象建树的好处是,如果不是极端情况,可以lazy load左右子树(当然,数组也可以lazy initialization子节点,但不能减少内存占用)。改起来也不难,于是就验证了一下,效果相当好,甚至比C++还快(因为测试case太简单,几乎没有展开子树),此外这种方式节点的数量可以减少到2 * x - 1(但是相应地每个节点需要增加指针)。

  另外遇到一个问题是迭代,Python的迭代器如果使用Generator语法(yield),写起来和用起来都特别自然,可是到C++就完全不一样了,形式上想要达到类似的效果比较累,保存和还原现场比较辛苦(不过这个case还好),试着实现了一个版本,但是需要遍历所有的节点感觉不太好,后来还是改成了偷懒的写法(直接生成整个结果集,在结果集上迭代)。

  最后,不成熟的小代码放在了这里:https://github.com/felix021/mycodes/tree/master/segtree

[update] 到数据集上实际跑了一下,C++版还是跑赢了几倍的速度,这还是没有做lazy init的情况,回头抽空再写个版本验证一下吧~

转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: http://www.felix021.com/blog/feed.php
pumpkinsm
2016-7-25 19:39
树状数组更好写吧。question
felix021 回复于 2016-7-26 08:28
需求不同,树状数组不适合做区间覆盖的问题吧。
分页: 1/1 第一页 1 最后页
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]