新年将至，想明年开始一个自己的project，目前还没有想好要做什么。用业余时间。继续打乒乓球。继续Blog.继续看书。其他的没想到了。
2008年12月31日星期三
2008年12月27日星期六
| [+/-] |
2008年终总结 |
2008年即将过去，雪灾，地震，奥运，藏独，经济危机... ... 真是多事之秋，而且很多都和我直接相关，即便不再身上发生，也会强烈的撼动我。所以觉得2008年过得很快，一个悲伤的年份。
今年没有出去玩，和lp一起把旅游经费都捐给灾区了。租的房子也搬了，因为以前的房子卖了。我自己买的房子还没到手，于是又换了一个房子。这个房子房租贵些，但是离上班比较近一些。并且，新房子有网络上，虽然网络质量一开始非常差。于是我又开始玩游戏。到年底房子已经好了，还没开始装修。
今年看了一些书，做了大概几十题的PKU ACM题库的题目。有不少收获，实际做题的帮助还是挺大的，只看不练也不行。但是再做下去也不想做了，因为感觉能做的能做，不能做的还是不太好做。还是多看看书吧。今年买了不少书，不过很多都没时间看，都是马桶上翻翻，上班的间隙翻翻。
工作今年很忙，加入这个组之后。对于linux内核方面有不少收获，不过并不是那么完整。工作其实更多的时间在做很烦人的事情。这两年都没闲下来过。
打乒乓球换了一段时间直板，最后又改回来，现在是oc横版但是不贴满，却发现这样非常好用，解决了我手小捏版问题，哈哈。
2008，没什么可写的了。
让自己快乐起来！
标签：
纪事
2008年12月25日星期四
| [+/-] |
基于染色DFS下的拓扑排序算法 |
拉屎的时候翻算法导论，无意停在图的DFS，然后到拓扑排序，发现这里的拓扑排序算法是基于DFS的。以前在群里还和讨论过依赖关系的算法，当时我知道的就是那个最简单的不断删除入度0顶点的算法。因为认为DFS(注：普通的DFS）算法可能需要辅助一些特殊的手段来做，不是很方便。
其实删除顶点算法并不是很好用，虽然渐近意义上是o(v+e)，实际使用中和存储结构很相关，而且不好用。然而算法导论上的基于染色的DFS算法很容易做拓扑排序：因为染色使得很容易知道回路，（灰色节点的重入代表回路）。接下来就简单了：
For each v in V do DFS
If a child is Gray , Fail.
If v is finished (to be black), insert v onto the font of list L.
return L.
这个算法的复杂度也是o(v+e),但是执行起来效率很高，因为删除顶点的算法需要维护“可删除性”，就是入度的维护。DFS维护一个染色信息，和顶点数相同。但是删除顶点算法可能需要临时的栈/队列来暂存计算出来的入度为0的节点。。以前老觉得DFS多老生常谈，什么书到那都翻过去，其实发现《导论》上的染色并且维护时间戳的DFS是非常有用的。（记得以前有段时间研究GC遇到过，但是没有在意在别的上面的应用）。看来很多书还要再仔细的多翻翻。
ps，惊闻饭岛爱去世的消息，沉痛悼念！
标签：
编程
2008年12月13日星期六
| [+/-] |
又到年末 |
今天是12月13号。。。明天凌晨又是皇马对巴萨，突然又想起四年前的皇马对巴萨，那时只有小罗和齐达内，没有梅西，更没有柏杨。。又是年末，圣诞将至，元旦将至，尾牙将至，春节将至。。。。
到年末就是要写年终总结的，我把07年的总结翻出来，看着觉得好熟悉，觉得近在咫尺，不能想象过了一年了。。今年也是看上去波澜不惊的一年，只是2008年对于身边的环境，的确是一个多事之秋。
准备准备，写一篇总结。。。
2008年12月6日星期六
订阅：
博文 (Atom)
博文
