Felix021

　　前几天讨论遇到一个涉及区间覆盖的数据统计，发现很适合使用线段树来解决，于是重新回顾了一下这个好几年前学过的东西，凭着残存的理解，好了好久才勉强写了出来，感觉自己确实是没有搞算法的天赋，在边界处理的时候磕磕碰碰的，需要改好几次才能写对，不够干净利落。

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

　　以前在学校折腾算法的时候，从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订阅地址: https://www.felix021.com/blog/feed.php 。