Monthly Archives: June 2013

缓存友好的数据结构

就是 cache friendly data structure。不知道如此中译是否合适了。 之前在 cJSON 链表的缺陷 文中提到过双向链表很可能是 cJSON 的 array 添加 item 所存在的效率问题的原因。 这次在解 POJ 的时候也遇到了同样的问题。于是就顺便做下代码示例。 题目是 POJ3253,Fence Repair。简单而言解法利用 Huffman 编码的思想。 看如下两个实现: 我首先写出的是 std::vector 的实现,提交后顺利通过。注意41行至52行的在已排序数列中插入元素的算法用二分查找会更快,但目前也不影响AC。 然后,注意到程序中完全没有使用数列的随机存取功能(上面只使用了线性搜索而非二分搜索),于是打算改用列表实现来节省 std::vector 的 erase 和 insert 造成的内存复制的额外开销。将 std::vector 换成 std::list,代码对应有少量修改。接下来出乎意料的是,提交后直接超时。 于是在本地简单用随机数据测试,20000大小的数据,列表实现要比数组实现慢近10倍,几乎全部的CPU时间都花在46行的 merge 函数上。内存访问对性能的影响极其显著。 关于缓存友好这个问题本身,个人并没有看到特别专门的论述。 … Continue reading

Posted in Computer and Internet, Programming and Algorithm | Tagged , , | Leave a comment

图论与线性规划

算是个回顾吧。到底我很久没看图论甚至数学相关的东西了(看的都是 Haskell 或 thread local 这种),这次只是翻看了些原来就知道的知识。 首先从图论开始。大学课程一般会熟悉 Hall结婚定理,和著名的 最大流最小割 定理。这两个定理和数个其它定理实质上是等价的,参看 Equivalence of seven major theorems in combinatorics。结婚定理 和 最大流最小割 定理的相似性从他们的证明和实现算法上看其实相当明显,都是利用增广路这一工具。 很多图论问题或看起来非图论但可以用图来建模的问题最终都可以比较方便的归纳成最大流最小割问题。而同时最大流又可以用超著名的 线性规划 来解决(虽然在实现上一般不会这么做),然后它的对偶问题就是最小割问题。 线性规划的重要性不吝多言。需要注意的是 对偶 这一概念在很多更具通用性的场合都有应用,比如 凸优化 及 KKT条件。 好吧回顾到此为止,上面提到的基本都是在大学教程上就能找到的概念罢了。

Posted in Science | Tagged , , | Leave a comment