2009展望

新年将至，想明年开始一个自己的project，目前还没有想好要做什么。用业余时间。继续打乒乓球。继续Blog.继续看书。其他的没想到了。

2008年终总结

2008年即将过去，雪灾，地震，奥运，藏独，经济危机... ... 真是多事之秋，而且很多都和我直接相关，即便不再身上发生，也会强烈的撼动我。所以觉得2008年过得很快，一个悲伤的年份。

今年没有出去玩，和lp一起把旅游经费都捐给灾区了。租的房子也搬了，因为以前的房子卖了。我自己买的房子还没到手，于是又换了一个房子。这个房子房租贵些，但是离上班比较近一些。并且，新房子有网络上，虽然网络质量一开始非常差。于是我又开始玩游戏。到年底房子已经好了，还没开始装修。

今年看了一些书，做了大概几十题的PKU ACM题库的题目。有不少收获，实际做题的帮助还是挺大的，只看不练也不行。但是再做下去也不想做了，因为感觉能做的能做，不能做的还是不太好做。还是多看看书吧。今年买了不少书，不过很多都没时间看，都是马桶上翻翻，上班的间隙翻翻。

工作今年很忙，加入这个组之后。对于linux内核方面有不少收获，不过并不是那么完整。工作其实更多的时间在做很烦人的事情。这两年都没闲下来过。

打乒乓球换了一段时间直板，最后又改回来，现在是oc横版但是不贴满，却发现这样非常好用，解决了我手小捏版问题，哈哈。

2008，没什么可写的了。

让自己快乐起来！

基于染色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，惊闻饭岛爱去世的消息，沉痛悼念！

又到年末

今天是12月13号。。。明天凌晨又是皇马对巴萨，突然又想起四年前的皇马对巴萨，那时只有小罗和齐达内，没有梅西，更没有柏杨。。又是年末，圣诞将至，元旦将至，尾牙将至，春节将至。。。。

到年末就是要写年终总结的，我把07年的总结翻出来，看着觉得好熟悉，觉得近在咫尺，不能想象过了一年了。。今年也是看上去波澜不惊的一年，只是2008年对于身边的环境，的确是一个多事之秋。

准备准备，写一篇总结。。。

买书

又买了一些书，貌似买的太多了。以前还有很多书没看。。。。最近，好像一年半都挺忙的。

《代码之美》

《TAOCP》 第四卷 2 3 4 双语。 （翻译小心的过分了，生涩的很，感觉图词的准确，但是句子有些不通，幸亏是双语的）

《费曼讲物理》 （汗，科普书）。

今年一共买了不少书。前面值得一提的还有

《算法导论》

《什么是数学》 （汗，又是科普。没办法，太菜了，除了看科普，总不能再去学教材）.

《梦断代码》

《编译方面的一些书》 （现代编译原理 现代编译程序设计，重新学习编译原理的东西）

《电影的故事》

换直板了

打了几年横板，换了块直板玩，OC. 觉得横板我一直没找到适合我的打法，握拍的用力和爆发拉球的力经常矛盾。才换的直板，这两天玩了玩，还不错。我发现直板很拉我很容易啊，哈哈。。。另外纠正一个以前的错误，就是拉球的引拍离身体太远，其实应该是先自然下垂，重心先侧倾，这样才能爆发用力。。。以前容易把肩膀架起来..

Linux ARM SWI

这两天终于把那个在Linux下面的SWI搞定了。解决了不少问题。其中一个值得记下的就是一个关于code需要重定位。因为Hook Linux SWI,就需要有段code取代原始Linux的SWI Handler，跳转到自己的Handler然后重新派发,以区分linux系统调用的SWI号和自己的SWI号，自己的就要跳转到自己的Handler，Linux的则要跳转原始的Linux的Handler (vecotor_swi)。这个Handler的代码必须复制到0xC0000000以后的Kernel空间内，不然会有问题（系统死掉，因为handler通过insmod进去，但是模块的函数地址在0xbf000000开始），所以要把code复制到kmalloc的内存里面，同时要小心不能使用一些像LDR的伪指令，需要保证局部跳转不会混淆。其他的问题都是零碎的，也没什么可记录的。 另外遇到一些问题，但是可能和片子有关。

酒量减了

昨天项目组吃饭，其实也没喝多少，我竟然宿醉。在上次和表弟喝酒，也喝了差不多，就没啥。昨天看来喝的太快了！！每次喝都过瘾，喝完就难受，烟戒了，这酒是不是该控制一下了。以前在学校喝酒，下铺给我一个描述：逢酒必喝，逢喝必醉，逢醉必吐。倒。。。
现在酒太多了，回家的时候，老爸也给我酒喝，做无数的菜，我妈也要我喝点，这种温情环境还没喝就有点微醺，所以在家一般喝一点就醉。晕！去亲戚家更是不用说，酒。。。。。


/*********** 华丽分界线 ************/

这个星期比较忙，做了一个比较麻烦的事情，让我不得不回头重新啃ARM汇编。一般的汇编倒也就算了，而这个是非常麻烦的事情：在 Linux 下面自己维护user mode和kernel mode切换，通过ARM的SWI软中断实现（这个名字好多种叫法，一般操作系统书都喜欢说是自陷，这名字好，人和代码一起陷进去。。。）。切换也就罢了，还要下面切回来在切进去，因为要把以前的一些同线程callback已有的代码实现。这汇编写的真是容易晕，栈有上下两个，寄存器也要分模式。终于sample调通了，往项目里插还得花时间。

/***********华丽的分界线**********/

听说最近经济危机找工作的人真的很难找，好多公司也不再招人，招人的都是好几百里面挑几十。

除除草

好久没有更新了，最近也没什么可写的。胡乱写点 前几天工作刚刚告一段落，不过新的事情又要过来。 我终于订了宋祖德的Blog,并且，把他不归在Blog的Tag里面而是 news 哈哈！ 最近在复习编译原理，一直想写一个类似LUA的嵌入语言parser和vm. 技术不实践，高来高去的扯淡是没用的。不过到底自己要做什么，也想不好。 奶粉事件后，现在很多东西也不敢吃了，nnd。到处都是腐败，房价也开始跌了。 开始过冬了！！

国庆看了 《站台》

国庆看了贾樟柯的站台，不知道为啥，让我感觉到中国人的精神黑洞，经历了改革开放，经历了国内外文化的冲击，火车，在矿工的生命代价下终于咆哮的着开动起来，中国也迎来了工业文明，有了知识的大学生，物质开始丰腴。可是精神上，却还是一片黑暗。艺术工作者在他们的努力下，却无法找到能源，如煤矿之于火车，他们在原地绕圈子，他们努力，一次次的燃起希望，结果一事无成。知道最后，他们结果就是沉沉睡去，麻木不再醒来，并且下一代被教育，不要再去触碰那笛声，那曾经承载年轻梦想的声音（哈哈，这都是我的理解，可不要认为是原片的意思）。

电影的音乐很喜欢，除了贾擅长的背景音运用，表现历史时刻和关键标记，在中间几次出现的哀伤的弦乐。里面每个小段落几乎都是长镜头一口气，演员演的也很到位。中间崔明亮两次点燃火的小段也很有结构的作用，尤其在他们看到火车之后的桥洞下，达到人物成长和整个电影的高潮。电影一点都不做作，也是我至今看过最细致的电影。细节很多很多。

不知道是先有英文名Platform还是先有中文名站台的，Platform还有舞台，戏台的意思，貌似这两个更贴合剧情一点哦。

至少我觉得，电影是哀伤的，不知为什么，我看到的是一部非常悲观的电影！

三鹿，无语

质监部门不作为，为什么给国外狗粮能测，却不能保护祖国的花骨朵？

关于所谓石家庄调查组之类的，说句实话，都能想像他们之间一起商讨搞出个奶农掺毒说法的样子，恶心！这样的调查组，谁会信啊！不能怪群众不信任你们，只是你们的劣迹斑斑！无非和周老虎的问题如出一辙。

寒心不止一次！

电信真是太垃圾了！

家里断网快一个星期了，前段时间也是断过好几次。竟然大言不惭承诺24小时修复，这次都搞了这么长时间了。服务人员就是一群傻逼。这就是欺骗消费者啊，质量根本不够包月，出现故障也没有补偿，我的300小时包月啊，妈的！！！

唉，在中国，垄断真他妈的比恶心，《反垄断法》完全是个笑话！

试用Google Chrome

呵呵，昨天猜测错了，就是OS的进程。

速度的确很快，其实我需要的功能都完备了，就差插件和更方便的书签。

很久没有Google的软件更新了，这次真不错。

Google Chrome 的“进程”

Firefox3我觉得已经很好用了，不过的确有被js堵死的经历。 今天看到Google要推出自己的浏览器了，的确有点意外，不过也有是意料之中。其中有个说法，就是Chrome使用多进程结构，每个Tab是一个进程，这样JS的死掉不会破坏整个浏览器。感觉就和曾经的曾经的iE浏览器一样。但是我个人猜测Google如果要想让浏览器很快的话，使用OS层面的进程是不是有点开销过大，至少平台差异严重。所以我猜测Google会不会自己实现轻量级的进程，只面向JS来做局部数据和执行的管理。。。仅仅是猜测，明天应该会发布了，有时间看看她的源代码。

我的体育

从小我就比较体弱，读书也比一般小孩早点，常被欺负，体育自然是不行的。很小的时候，需要身体力行玩的东西多，即便和女孩儿一起跳皮筋，也挺有趣的。那时候，有没有那个傻逼要说考试要考体育，于是慢慢的也茁壮的长大了。

上了初中，也不明白中国人自当强身健体，那啥奥运亚运奖牌，和我也没什么关系。于是开始想玩一些体育项目。接触了篮球，足球和乒乓球，至于田径，虽然我跑的还算快，跳的也够远，耐力很差，终究不是好玩的东西，一般没有任何兴趣，电视上看到比赛，也觉得乏味的很，毕竟年纪太小，力量的感觉，还不如圣斗士和变形金刚来的实在。群体的球类，好玩的很，因为是一群人的游戏。篮球和足球也是乱玩，没有什么章法，至于乒乓球，小孩都会打，打得都不好，这门运动的魅力就是谁都可以发明打法，但是没有系统训练，大部分打法都是不科学的。

高中开始没什么体育的了，因为俺正式开始发育了，也许吧，14岁应该是开始了，于是开始练胸肌，练腹肌（练得时候觉得涨了不少，第二天就觉得没了）。对力量有感觉了，看比赛也有兴奋了。中国拿了奖牌，也是高兴的不得了。可恶的是，这时候，偏偏本来对体育有点兴趣的，不知道为啥体育要考试了，本来上学就非常的辛苦。。。谁出的馊主意啊！再说，考试也可以考点有意思的，就是跑，跑，跑。。。

进入大学，彻底对自我体育修养失去信心。只看不练，看完乔丹看意甲，自己就是不上场。后来，对游戏竞技的兴趣更甚，逐渐爱上只动手指头的运动了。。。而俺们国家的奖牌越来越多了，真是为之骄傲啊，恩，运动员和世界差距越来越小，我和他们的差距越来越大！

今天，中国已经拿到49枚金牌，稳坐第一，大大超过美国。我感到非常的兴奋和自豪，因为我的国家是体育强国，虽然我不是体育强人。让我去跑步?算了吧，我还要上班和游戏哦。

做题1022

1022的题目看了我一个小时才大概搞明白怎么回事，还是所谓的4维空间的题目。-_-~~. 其实就是把3D立方体组合出一个所谓4维的立方体，面变成了3d立方体。其实这些都是虚的，题目扯了很多，其实他的拓扑结构很简单，就是个最大8度的图。在四个坐标轴上各自有两个边。有边表示有粘合，如果在方向xn有边a-b，则必有b-a在xn的反方向，没有就输出矛盾。然后只要通过递归标记所有的可到达的立方体，计算最大的四个坐标轴的范围l1,l2,l3,l4. 递归到不能标记为止，如果所有的立方体（搞个计数器）都标记了，说明是一个所谓的物体（题目中如果物体分离则输出矛盾）。体积就是l1*l2*l3*l4.(这个是我猜测题意的，所谓的四维体积，结果是对的）。另外，题目有个陷阱：单位立方体的ID不是1-n，而是任意的，BS. wa了一次。最后16ms AC。

奥运进行中

错怪老谋子了，晕倒的CCAV。 男篮惜败，可惜啊！ 向中国体操队致敬！ 向女足表达祝福！ 。。。 向那位比利时的兄弟说声：对不起！

奥运来了！

看了。 中国画卷的主体，为啥那么小？ 创可贴？

又开始堕落

能上网了，恩，是说能在家里上网了，我可以玩游戏。又开始堕落了，我又开始CS,疯狂下载各种网游，不看书了，不做题了。竟然还跑去玩老传奇，罪过啊，真是毒品，受不了了。 没办法，真的好想玩！

转大牛Donald E Knuth的采访！

这是一篇关于大牛Donald E Knuth最近的采访。Knuth对于很多“时髦”的东西做了自己的阐述。关于开源， 多核和极限编程等。既然是大师，肯定不会人云亦云，也不怕表达自己的观点，即便是以谦虚的态度。平时看多了商业或非商业鼓吹，让人觉得有些不止所归的时刻，大师的话至少是一盏灯。

翻译的让我愤怒

昨天说到Understanding Linux Kernel中文版翻译很差，说来巧，公司买了最新的基于第三版的翻译，我先翻了一下，发现一些小错误改掉了。但是，还没怎么看，又看到多处错误，而且非常明显的错误，比如（内核线程从不访问内核空间），还有甚至吧ThinkPad写成ThinkPnd.....这才没几页啊，就这么多错误。而且我也不是很细节的再看，因为完全不敢，幸亏有英文原版，不然就晕过去了。 既然是翻译，就应该专业。另外，读英文还是比较不如中文省力的，因为中文感觉可以一目十行，但是英文就不行。所以翻译的书对于很多读者还是很有用的，但是包括这样没有水平的错误，让人觉得寒心，态度在哪里？？？其实态度好，哪怕不好翻译，写在注脚也是让人很能接受的，唉～！ 有点愤怒!

记忆中的电影（情书）

喜欢一些电影里面，随着钢琴声，镜头在空中，穿过岁月，回到过去的镜头。一路上的雨和雪，柔和的扑面而来。 突然又想起了《情书》。最喜欢里面两首曲子，一个是,另外一个是. 想起大学时候，突然在校园网看到这么一部电影，一下子就让我静静的坐在那里看完。而且让我永远记着了那个导演的名字：岩井俊二。流畅的镜头，动人的音乐，绝美的光影。 打开豆瓣，几乎和所有人的共同收藏就是《情书》。一部大师级让所有人都喜欢的电影，这实在是太难得了。 因为想写一些Blog，记录下我看过觉得很有意思的电影，凭记忆写一些留在脑海里的感觉，第一篇就选《情书》了，因为根本不需要笔墨，嘿嘿。

又要找房子了

新房还没到手，房东就要催我滚蛋了，又要看房了。哎，真他妈的麻烦！ 下午去看了一个，现在租房子也不是一般的贵啊，屁大个地方也是1000块钱。

做题 PKU1128

这几天很忙，换了平台，问题无数，烦死了。
突然觉得，做题目是多么纯粹的事情，看题目，分析，写代码，调试，搞定。不用交流，不用扯淡，不用管什么环境。。。。。。这是多么幸福的事情。

这次的题目是PKU1128，最后0MS AC。

题目也不难。首先扫描输入数据，得到矩形的区域信息，（这里已开始没有看清楚题目，题目有个约束是see at least one part of each of the four sides, 这极大的简化了题目). 然后在每条边上查询被那些覆盖的字符，那么那些覆盖字符代表的矩形就是表示z-order更高的。得到一系列的序对：(A, B) (A < B). 当然，根据这个序对得到一个有向图，本质上是求出这个图的所有的拓扑排序。每次找到一个入度0的节点，然后删除，递归这个过程直到得到路径。题目要求所有的路径，于是需要递归前后回复状态，把删除的节点恢复。（我使用一个标志数组，效率还不错）。

不过一开始还是在scanf上面又纠缠了一下。。。WA了一次-_-~。

继续做题 PKU1034

这个题目不难，只是一开始容易被题目信息迷惑，还有那个可恶的" speed that is up to two times greater than his master's speed" (这句英语我到现在还没明白，是3倍还是2倍，幸亏题目的例子俩面经过测试应该2倍。。。题目的内容给人感觉是网格运动模拟+搜索类的题目。其实稍微分析一下，题目中的一个不完美的限制“小狗”每次在主人的一个运动区段中只能走过一个感兴趣的位置。所以这个题目最后抽象为：主人线段 与 （同时2被速度内）可到达顶点集合的2部图最大匹配问题。结果就是，未匹配点就是小狗乖乖的跟着主人走，匹配点是去玩一下到下一个定点。
刚好复习匈牙利算法，32MS AC! （增广路径每次+一条匹配所以条目计数也是很方便的。）其实匈牙利算法的代码是很精炼的，但是精炼的背后还是有很多细节值得重新学习和分析一下。

Diablo III !!

哈哈，终于出现了，就是Diablo III.

貌似这两天blogspot解封了？

Diablo 3要出来了？

这两暴雪的主页上有神秘的冰裂开的图，似乎有新的游戏要破冰而出，而且上面有暗黑的符文标记，难道是传说中等到花开花谢的Diablo 3??

看球的这些年

我第一个认识的球星是马尔蒂尼，因为那时候买了一张贺年卡，上面就是他。不知不觉看他踢球踢到老，真是岁月如刀。第一个非常喜欢的球星是欧文，98世界杯那一个惊世骇俗的天才，比我大两岁的天才少年，像一把极快的尖刀穿到阿根廷的左肋。也是不知不觉，在06世界杯上，看到他因为那陈年的膝伤，软弱的倒在绿茵场上，不能忘记临倒下的那个眼神，早已失去神童的光泽，只有遗憾，悲伤，和对足球的告别。

今天的足球，逐渐的失去早日的华丽，越来越野蛮，功利的的踢法使得足球在观赏上开始走下坡路，无论是哪个天才，除了伤病就是侵犯。在一点上，马拉多纳是幸运的。今日有很多极高天赋的球星，要不就想罗纳尔多，欧文那样成为一个悲剧，要不就是像梅西一样成为玻璃人。看到梅西过人的时候，除了惊叹，更多的是揪心。

高中的时候开始稍微的看球，在大学看得也不多，真正看得多的是刚刚毕业的时候，因为欧文而喜欢利物浦，喜欢英超。那时候同学大部分更喜欢意甲，英超的强队相对不是很多。周末有个重大的活动就是看球，无论多么晚。去年英超被买断了，没得看了。意甲爆了丑闻。德甲没得看，西甲只有好戏除了皇马对巴萨也是寥寥。能看的球越来越少了。。。

至于中国足球，我从三年前就说再也不看了，可是和很多中国球迷一样，一个字：犯贱。一场又一场，一场更比一场丑。上次回家，还笑话我舅舅被舅妈说看完中国队比较手脚竟然冰凉的，结果前天中国主场对伊拉克，看完了，我才发现我的脚是冰的。中国足球是一个奇迹，一个彻头彻尾的奇迹，非物质文化遗产，前无古人，后无来者，惊天地，泣鬼神。

关于C语言中实现的GC

去年年底做了个ANSI-C的GC简单原型, 写完代码就扔在哪里, 也没有关注过，虽然写GC的过程中很有收获（比如学习了一个GC mark的非栈算法（3p算法)）,但是最终结果是还是应用起来相对比想象中的复杂性还是要高了一些。也就没管了，但是最后也没总结个文档出来。前两天看到云风的blog上面有他在这几天也写了一个GC for C的原型，基本上是另一个方向，基于 C 语言的指针而不是Handle, 因此看到他的Blog，颇有共同语言，遂回复并请教之，他也在回复中做了一些比较详尽的讨论。他是很有勇气的，把他的东西开源了，我那个玩意现在最后的设想，关于finalizer线程并没完全实现，（当时考虑到Geohm GC依赖于图的拓扑排序来finalize,所以做了一些思考，包括这个顺序本身的问题和finalize的线程，还有执行批量一次多少对象的finalize）.

既然有人也做了，我也可以把我的那个做法和基本的思考写出来，做个基本的回顾，不管成功失败，结果总是有一丁点的价值吧。

1.首先重点是接口，其实到底该给用户一个什么样界面，什么样的接口，甚至要提出需要的概念，是否够用，是决定了这个GC是否好用和有价值。当时思考这个问题真的非常的扰人。首先，在C语言，处于C的哲学，你必须够简洁，而且够用。一般的，在Java, C#这些已经有了GC的语言中，引用这个概念是显然的，在C里面，就要选一个，是Handle还是指针。这个后面会提到。另外，全局引用，对象之间的引用，栈上引用，还有甚至所谓寄存器引用(在Geohm GC的实现里面，扫描会饱含寄存器，所有架构相关可能存有引用的都会被扫到）。我的想法是把这个问题简单化，透明化：用户来搞，用户只维护两种引用：全局，对象间。全局引用使用引用计数来作为收集标志，并且他们是所谓的GC 根， 扫描总是从这些开始。（如果非要把根单数化，那么可以考虑有个根对象，跟对象和这些全局有着这些引用，但是这样的归纳看上去简洁了，实现确不如后来的有效率）。对象引用就是普通的赋值，不做赋值跟踪（使用C操作符=而不是定义宏，这个有缺陷，后面会说）。这些是否就够用了呢，基本上，差不多。有些细节，比如为了用户方便，实现一个所谓“基本数组”对象，就不提了。但是有个不能不提，那就是栈上引用的模拟，我是用一个对象，叫做Local frame, 每个线程使用线程局部存储来维护一个Local frame stack.可以push和pop. pop就是吧一个frame去掉，这个对象没了，那么栈上的对象引用也就解除。这个有好处就是GC有个很大的用途：一些紧凑的编程，需要产生不少所谓栈上的对象，而这些对象，用户并不想去自己来释放。少了这个，GC就少了很多威力。


2.Handle ,还是 void *?
这个问题是C里面实现GC的根本指导:要高的还是要低的。普通的C指针是比较简洁的，对用户很透明，但是关于在C里面应用Handle, 好处是很多的，虽然会增加用户代码，因为Handle本身有合法检查性方便，这样就不至于再给用户一把自宫刀子了。可以做内存重新整理，这一点很重要，GC在标记之后的垃圾清扫，使用何种策略是GC能不能带来好处的重大因素。一个整理内存的GC有着非常多的好处比如 没有碎片。

我的GC的指导是用户知道自己该让哪些对象，处于GC的内存管理之下，并且用户在提取Handle的指针的时候，可以处于GC关闭的保护，（我叫他做GC barrier，这个名字不太好去，和并行编程的那个barrier不是一个概念，就是防止用户提取指针的时候GC运行导致指针移动 ）。

到底该使用哪个方式，我觉得都是可行的，只是我个人认为Handle的方式在将来的扩展性可能要好些，当然，这是建立在用户多写handle相关的代码上，不过我觉得现在handle相关的代码很多，C程序员早就习惯了Handle了。


Handle方式的实现比较简单，一般就是一个Handle向量表，和一个堆来存储对象。细节就不说了，将来我的那个也开源吧，最近没有时间，还是要整理一下。

3.GC Thread
这是个困扰我的问题，虽然我早就定下使用一个Thread来做GC的方式。我还没有仔细的看过云风的代码，如果没有猜错，是在用户线程环境下做收集的。我的GC 有 Thread，然而Thread，众所周知，是移植性最大的挑战。首先，当GC在收集的时候，用户到底是把自己的所有线程暂停，还是仅仅是：当GC收集的时候，用户进入Barrier会被挡住，或者如果当前有用户在Barrier保护内，GC就不能收集。（这里有潜在分配/barrier死锁，不在这里细微讨论了，是可解的）。我采用的是后者，但是这并不能说这就是安全的，用户要知道这一点。在一些嵌入式系统上，我们可以简单的关闭中断（吓死人）来防止线程调度，来保护GC收集的时候不会到其他线程导致冲突，这在别的系统上是不可行的，在别的系统上，比如linux，可以参考Geohm GC里面挂起所有线程的办法。

另外，就是Finalizer Thread。这个应该不能放到GC Thread里面，因为把客户代码放到GC Thread简直就是自取灭亡。必须通过另外一个Thread, 或者多个-_-~。 这个我的代码没有实现，因为最后没有想好一个比较好的finalizer顺序。。。。在下面finalizer会提。

使用Thread可能是很自然的，然而在GC for C这样的里面使用Thread是有很大风险的，我的GC有一个OS Porting层，然而这层的接口比较潦草，仅仅是Thread mutex semaphore这些基本实现，并不考虑各种系统的区别。也许直接用posix的比较好，谁知道呢，win的支持不好，@#@$MS@#Q@.

4.隔代收集。
内存整理是个很耗费时间的事情，基于标记-清除或者整理都有这个比较郁闷的僵死时间。这也是早年GC老被人嘲笑的原因。现在有很多成熟的基于隔代收集的算法，这些算法的效率已经非常不错了。然而他们需要一个特点：追踪对象引用的赋值操作，或者说就是要知道某个对象在某时候引用了一个别的object,则需要立刻记录并作一些处理。这个在整体上会有一些效率的耗费，但是获得的是比较短的收集时间。

5.finalizer：
现在很多GC都支持一个所谓的finalize, 来实现GC辅助的资源管理。在 Geohm GC 中，使用拓扑序来call这些finalizer function. 这是个很不错的想法，可惜我没有实现。不过在现实中，对象引用有环的图应该是很容易发生的，但是话说回来，如果依赖finalizer来做资源释放，而本身存在环，这就有点不大对劲了，（不过也是有可能的）。这就不太好做了。我当时想就简单点，随便找个顺序，释放得了。另外，finalizer也需要一个线程，并且优先级要比较低，从一个队列去取对象来调用。这时候，我们再需要一个标记，就是一个对象在mark为不可要的时候，还有finalizer没有call之前也是不能被收集的（如果有finalizer function的话）。当call了之后，标记就置位。

6.Marking算法：
研究GC的应该都会看到那个比较彪悍的不要栈的通过节点缓存（不存父亲指针）的方式图遍历算法，（我叫他3P算法,三个人名字，怪长的），其实实际上，栈的简单深度有限遍历算法也是很有用的，因为我的GC并不是整个系统都在用，所以出现GC回首时，内存无法供给一个动态栈并不是很容发生。反而那个3p算法会需要一个每个节点计数器的存储开销，这个计数器可能并不需要，一般的一些书得介绍因为把对象描述几位几位的省出来一个计数器，有时候并不一定，呵呵。

这个东西做的时间有点长了，记得不太清楚，也不知道有些忘了写出来。先写这么多吧，不然以后忘了就比较失败了。

另，比较佩服云风的精神，开源是需要勇气的，面对回复也是需要勇气的。

mp3的错

自从在电脑上存着mp3, 就会发现听歌简直和拉屎吃饭一样容易，没有放入磁带和碟片的操作，连按按钮的一点点的机械运动都没有。于是一些好听的歌，也被听成黄脸婆了。不断的有歌被删除，又有新的歌加入。那些能坚挺很长时间的歌，还真的不是很多啊。

上上周的pku1088

哀悼日结束了，但是没有理由忘记逝去的生命，更没理由不继续好好的生活。

上上周做了一个比较有意思的题目，很有记录的必要，因为自己的思路很清晰，解题的速度很快，没有纠缠，从分析到得到一个算法，再到一个更加完善的最终的动态规划的算法。PKU1088滑雪问题。

很明显的一些分析，如果是搜索的话，那么可以求解所有的位置的可滑的最长路径，然后比较得到最长的。另外题目有个很优质的特点，肯定不会有回路，这个很容易反证。直接搜索时间上肯定不可行，而且题目的递归式明显的最优子问题结构：

path(x, y) = (1 + max(path(xnext, ynext)). xnext, ynext是所有地势更低的节点。然而，当从第一个节点开始求解的时候，她会求出那些地势低的节点的解。而且这些解会大量的应用到求解其他节点。不过，把这些最优字结构变成动态规划算法，并不是十分容易，或者说，变成递推的动态规划算法并不十分容易，需要一些分析（引入其他参数，如同图的最短路径算法）。不过明显的算法可以是备忘录的动态规划，递归+表存储。

于是写了一个备忘录的代码，上传，16MS AC.恩题目就解了。

如果直到这一步，这个题目就没什么意思。首先，这个解把所有子文题都解了，那么递推的算法肯定优于备忘录（《算法导论》上对于动态规划讲的很好）。怎么得到递推算法才是有价值的。回过头来分析递归树，一般的，搜索的过程會止步在一些地势最低（相对周围）的点，那么，这就是一个提示：递推是不是可以从那些坑里面开始。猜测可以使用按照地势排序的节点索引作为传说中的第三参数。那么：

最低的点，很显然，就是他自己。

如果当前已经求得一部分解（索引参数

1 + max(f(p)) (p为那些next ynext为周围有过求解的节点，如果都没有，那么就是f(p) = 0）。

因为f(k)不可能经过比她地势高的节点，所以xnext,ynext 属于 f(x小于 k)

一直递推到k = m*n ，就是最高节点。其中需要比较得到最长解。

递推的出来了，但是它需要预先的一个排序，哈哈，好像这个递推并不一定比备忘录更快啊。备忘录其实比一般地推是坏在递归的开销上，而这个是一个常熟因子。却没拼过排序的开销（排序一般都有O(N*logN)）.看来这个参数代价太大了。

当然这个题目可能有更好的解。

另：

公司封闭了所有除了80 之外的包括https端口，没有机会上网了，连blog都发不了，这篇也是tor上来的，慢死了。唉～

哀悼日

《国务院公告》

为表达全国各族人民对四川汶川大地震遇难同胞的深切哀悼，国务院决定，2008年5月19日至21日为全国哀悼日。在此期间，全国和各驻外机构下半旗志哀，停止公共娱乐活动，外交部和我国驻外使领馆设立吊唁簿。5月19日14时28分起，全国人民默哀3分钟，届时汽车、火车、舰船鸣笛，防空警报鸣响。

 

早晨沿路经过的，默默的半旗。

中国第一次为百姓降半旗，立此存照！

安息吧，几万的灵魂！

 

（另，和很多Blogger一样，把所有的blog都置为黑白）

哀悼，致敬！

 

已经接近2万的死亡人数了。。。什么都不想说了。

 

向奋战在一线的所有军人，医生和救灾人士致敬！

 

希望所有人都动作起来，无论捐款还是做些什么。可能这些做的有限，但是，只要是努力，就有更多的希望。

为地震死难者默哀

昨天中午在公司突然感到头晕目眩，前后不定，突然有人喊了一句什么东西在晃，当时我以为公司楼下装修出问题了，才发现是有轻微的地震。（合肥，中午2：50分左右）。

新闻马上播报，四川汶川7.8级大地震。死亡人数还在攀升接近1万人，目前数字和救援还没到达震中。

希望ZF能够比较好的完成这次救援。

谨此为死难者默哀！

 

另：为什么奥运火炬还是依旧喜庆的传播，就算不要影响，我也希望能有些仪式上的比如默哀和黑纱，为什么没有，难道那些领导都是机器人？？？

试用谷歌金山词霸

整体界面有点闪烁，然后有一点失望的是链接竟然是直接用IE打开......完全不顾我的默认浏览器设置。

上次更新了Blogspot的版式，右边栏丢失了很多东西，看来要补一下，不过我已经忘了以前都是些什么了。

尝试一下Windows live writer

最近网络有问题，应该是监控导致的。打开网站经常出现第一下没反应，刷新才能出来。然后经常导致一些网页的CSS或者script丢失，所以在线编辑Blog比较烦.所以尝试一下离线的Blog工具，虽然这个是WLW是M$的，但是用起来倒也挺顺手。支持blogger和ms live space.

写Blog4年了？

发现自己的BLog越来越像流水帐了，其实生活里面遇到一些更有意思的东西没有记下来，一方面想不起来，觉得小到不能写出，或者不能用语言表达的好，比如电影。

不知道什么时候注册的豆瓣，然后摆了几个所谓爱看，看过的玩意。但是发现这根本没什么意思，就和有钱人家的书架一样，拿来装个相反的d，当然，穷人就只能上豆瓣了。所谓看过的书，其实大部分都没看完，甚至大量没看懂的，于是只能在看，那玩意就壮观了，经常是个人并行再看无数的书。

于是发现记录这些平时的涉猎，兴趣还是很难的。但是记录还是有好处的，记录的时候会再认真思考一下，有些东西，比如对电影的感觉，不是专业人士，去写影评是个比较招骂的事情，而且自己也会觉得不着边际，但是看电影总是会有感觉的，如果能记下来，再在网上看看，也会有更多的收获。有人认为，没看过相关领域的书，或者研究过，就不应该乱写。恩，在网上掐架的人自然要多看书，不能乱写，乱写就容易被对方抓到把柄。不过对于我来说，写BLOG本来就是记录，错的，对的，都可以写。若干年后，回头看自己当时写的东西，如果觉得很倒，也是一个进步的事情。难道自己还要鄙视曾经的自己？

写BLOG也有好几年了，从一开始的CSDN, MBLOGGER, wordpress到现在BLOGSPOT, 也写了乱七八糟不少东西了，现在看来，有价值的真不多。但是对于自己，看到自己的成长也是很有趣味的。还记得在csdn写过一个message queue java实现，真的傻得可以，（倒不是说程序写的傻），感觉就是想搞个小文章出来，其实那篇文章写的对有些人还是有点帮助的，毕竟那时候刚学习java，想通过一个message queue来写一下java基本的线程，同步，管城的一些东西。因为无论是什么基础的人，学习一个没有用过的语言，肯定是有，至少心里有笔记的，而这些笔记对自己没用 了，但是对一些刚用这个语言的人是有帮助的。

写BLOG是一个心态，是一种生活。也许会有人觉得你写的东西很无聊，也许觉得你写的就是错的，但是，在web2.0的时代，大家都可以提供内容到互联网上，其实有用无用，对错只要稍微经过一点时间就能淘出来。不过，我一直也没明白，我的blog是写给谁看得，现在有答案了，写给路过的人，不仅仅给自己看，也不太想给太熟悉的人看。当然，路过的人，总是很少的。Blogspot经常被GFW，路过还要一些难度的。

上上周做过的题目，1067 和 1024

最近实在太忙，项目里面的一个BUG经常要解很长时间，而且环境也比较恶劣。又有很多自己不能掌控的事情。所以最近也没有做题目。
上次的题目是PKU 1067，一个博弈方面的题目，题目很有意思。记录一下我的思路：
首先题目有一个很大的提示就是棋局都是可解的（就是对于一个棋局，谁会赢是确定的）。首先很容易找到一些必赢的棋局，比如：(1,2), (3,5)(4,7).看看是否有什么规律。对于当前棋局，总能找到一个下法，是的对手无论如何下棋，我都是能赢（递归），或者是，当前棋局，无论如何下棋，对手都能找到下法能赢。

不过规律似乎不是那么容易找到，但是从题目的规则上，容易找到一个筛选算法（带一点贪心性质）。从首先，定义函数 F(a, b）为棋局的胜负(1胜0负，这个胜负代表一种必胜和必负）， C(a, b)为一个规则下法所导致的棋局的集合，比如C(1, 2)就有: (1 , 1), (0, 1), (0, 2), (0, 0)...等（规则就是题目里面的一次只能取一边的任何数目，或者两边都取相同的数目）。那么对于个棋局 (a, b), 通过规则反推， 有：

F(a,b) = 0, 则F(a + x, b + x) = 1
F(a,b) = 0, 则F(a + x, b) = 1
F(a,b) = 0, 则F(a , b + x) = 1

于是：从F(0, 0)为输，那么F(0, 1), F(0, 2),...F( 1, 1), F(2, 2)....F(1, 0), F(2, 0)为赢（显然）。
那么是否可以找到下一个输F(a, b), 是不是把这些筛了下一个就是呢，的确，容易证明：
因为下一个（定义下一个为，b + 1，因为一次筛选肯定能筛掉所有当前行, a 从左到右选择第一个空白）因为下一个F(a,b),通过规则下法，（无论如何，不能不下）， 所以任何 F(c <= a, d <= b) 的棋局是在晒选过得集合里面。F(a,b),通过规则下法，（无论如何，不能不下）， 所以任何 F(c <= a, d <= b) 的棋局是在晒选过得集合里面。这里化个图是很简单的： 这图就是每次筛选用的不同颜色。
因此，如果范围不大，用这个筛选法就能得到结果，可是，这些必胜棋局确实有规律的，我只找到他们的口每次+1，我可怜的思路到此为止，题目中的范围很大，必须找到规律。
后来GOOGLE了，实在想不到了，这个题目的原本就是一个博弈问题，叫做Wythoff 博弈。必胜棋局是有一个通项公式的，BT...

A_n = floor(nP) and B_n = floor(nP) + n, where P = (1+sqrt(5))/2(黄金分割)

好了，到这一步，代码也没什么了。。。


第二题是PKU 1024. 是一个怪绕人的题目，通过迷宫路线求迷宫和多余墙壁。我没想到那个广搜+逐个移去墙壁也能AC。。。
其实我也有一个深搜的版本，深搜的版本预料之中是TLE, 广搜要好很多。，不过可能题目的数据量不大，本来在求墙壁多余的时候，是因该维护一个可“回朔”的队列要好些，因为一个墙壁在广搜的过程中，蔓延到他之前的搜索都是不变的，如果把它移去的话，那么这些层次的数据是应该保留，只用从考虑它开始的那一层广搜开始就行了。另外，有些墙壁天然就是有用的，比如双面路线的，就是不用搜索就可以剔除。不过这些我都没写，就写了个简单的直接搜，竟然AC了，而且16MS还挺快的。。。可能前面有个简单的优化其了一点左右，就是路径的合并，因为题目要求唯一路线，普通广搜只能搜出一条最佳路线，如果要求解所有路线，可能要对兄弟节点都展开，但是实际上可以吧兄弟合并，加入一个ENTER计数,这样就不用重复考虑兄弟又不失路径是否唯一的标志，丢失的只是路径本身（这个信息是不需要的。嘿嘿）。这个题目比较顺利，不若第一个题目那么BT。。

合肥 家乐福

周五下班回家的时候，大概七八点的样子，801路车到青阳路突然改道转金寨路。长江路三里庵段有很多警车。原来是预料之中的抵制家乐福示威活动正式开始了。
星期天接待一个很久没来的朋友，路过长江路，突然一大群人打着标语，喊着口号沿路冲了过去。

以上是我知道的所有的关于合肥家乐福抵制活动的记录。

后来上网，发现合肥的抵制游行活动，无论规模还是影响力，遥遥领先于其他城市。

在此表达一下我的心愿。

尊重自己的同胞，尊重别人的爱国方式，无论形式上还是内容上。请千万不要把拳头挥向自己的同胞，谣言自然不攻自破，但是也要注意若干脑子进水，或者天生暴力倾向，或者别有用心的人。言论自由，不仅仅是对zf的要求，也是对我们自己的要求，当一群人拥有了人数优势，和zf一样，就拥有了一定的暴力，所谓道德制高点的优势，这个时候如果言论的自由被凶恶的打压，和所谓zf的打压没有任何的区别，还显得更加卑劣。

不要沉溺这种大规模活动的表面强势，这毕竟是弱者展示强势的最后手段。做好自己，多多思考，文化，价值观的强势，才是真正的强大。为什么外国的媒体可以侮辱我们，而我们却不能发出自己的声音，为什么外国人看到照片上有坦克和人就会激动。为什么Made in china被外国人肆意歪曲，为什么那么多的科研作假。。。中国的未来，不仅仅是奥运!

好用不经用 ，EG.

上上个星期买了一块EG, 正反狂3. 一个星期就适应了，比OC更适合我。 但是，今天重新刷一遍胶水，面材就脱落了一小块。。。。 真不经用。郁闷。

Blogger里面插代码

Blogger的HTML编辑器插入C代码比较麻烦,得加一个pre，但是pre也不太方便。真是的。不知道有什么好的办法。直接从本地编辑器复制出来的代码粘贴到Blogger就乱七八糟的，自作主张的做了各种排版。不知道在哪里去调整。 晚上去和表弟喝酒，这次的做题先就不写了，和下次的题目一起写。 唉，周末真无聊，自从英超被买断，再也没看过英超，意甲周末也是不一定有，西甲太晚，看球是没什么指望了。要不再去打大波罗？以前在学校是联机玩，单机我玩了一个死灵，到地狱打不动了，全招的，累死了。去玩个法师好了。

北京奥运

本来我对北京奥运没什么特别的感觉。但是最近的关于奥运的事件，打上ZD事件的烙印，觉得奥运对于中国，开始有了某种特殊的意义。这次ZD事件和奥运的风波，在中国，无论各方都在重新思考，世界和中国。

真的没玩够

我最不后悔的事情，和某些人比较，就是在大学的时候选择的是玩的路线，嘿嘿。真的很开心，现在工作了才觉得好明智，如果大学没玩，工作后就没有什么玩的意思了。 很庆幸的是，我到大学之后，电脑已经开始普及，高中的时候电脑游戏就开始兴起，不过大学之后，游戏更呈“专业化”发展。所以，玩的主题基本就是游戏了。其他的，于前辈人共有的比如喝酒唱歌之类，自然不在话下。无论何时，总能找到一帮子人，和你玩。大学三个班，第一年和三班玩，第二年和一班玩，第三年和一班玩，第四年和二班玩。 工作后，身边的朋友逐渐远走了，也没人可以玩了。生活真的黯淡了很多，也许有些人会说，玩够了，该干正经的了，或者说，年纪不小了，该收了。可是我怎么总是觉得没有玩够啊，现在每天没有人一起玩游戏，的确没什么时间，可是觉得现在这样是在浪费生命。 每天回去我都只能在cs,sc两个老游戏里面殴电脑，把他们想像成曾经的同学。。。 。。。 生命在于玩乐。

第三题很失败，1015。

妈的， space速度还真不是一般的慢，还是用我的blogspot好了，虽然国内无法访问。 这周做个题目不顺，就是那个1015,陪审团问题。虽然有个思路，但是因为实在没有时间去做，没有提交，因为老是没作对。 思路是类似动态规划。貌似不能叫做动态规划来解的题，因为题目的最优解并不是通过求解相同最优子结构来做的，而是通过相同子结构迭代求一系列解来做。求和问题和01背包很类似，有大量同子问题。通过增长决策的源数据下标，增长求和个数（<=20），不断求得一个范围内的和数问题。然后选择最优的。因为没有用去尝试这个解法（空间复杂度比较高，而且用C写，存路径很麻烦的，debug也要费不少时间），所以不敢保证是对的，也不想再纠缠下去。 Bs自己。 后来在《算法导论》的NP完全问题的近似解法中也看到一个类似的算法求子集和数的问题（不过这个和数是固定的，子结构中超过这个和数就可以cut掉，解法没什么，但是那个通过归并排序来求下个决策下标的和数比较不错），书上没说这个是属于动态规划，俺也不敢说。虽然真的和动态规划很像。

第二题1175和一些思考

第二题本来是乱选一个题目是个求解同棋局问题，但是我觉得题意有点不清晰。（到底是形状匹配还是下法匹配），打开discuss，有人说数据有问题，很容易pass,另外一个人说和1175题目完全一样，我就去做了1175。

http://acm.pku.edu.cn/JudgeOnline/problem?id=1175

1175是个很浪漫的题目，求解星空中所有相同的星簇（cluster）。 (98 IOI). 这个题目乍一看相当简单，但是做起来发现也是很容易出错的。
我的结果是16MS。未作更多优化。
思路很简单，先逐个查找出所有的星簇，当找到一个星星就从她开始递归的连接出所有的其他星星，存储宽，高等足够的信息。
然后从已经找到的星簇中寻找相同的，旋转和倒映的，如果没有找到就继续。找到了，要把星星标记重新标记为已经存在的那个字符。这里我对于旋转和映射没有使用公式而是使用一个scanner函数表，不同的方向各自一个，本质上就是对于源的一个scan顺序，目标只要使用scanner表离得任何一个通过检测就OK了。里面没用公式，推导公式我觉得不如组织好的代码更不容易出错。而且效率差不多。而且当时觉得scanner的状态可能对后面解题有帮助。（其实没有-_-!）

过了题目中的简单数据，提交上去，立刻WA...

（总是在拉屎的时候思路稍微清晰），如果两个相同的星系相互侵入，那么直接通过标记来判断就不对了，必须保留星星属于哪个星系的信息，否则再重标记之后就会导致以后的检测错误。简单了，再加个数组，存储星tag为他们所在星簇的idx.

OK。过了。
对于效率，因为数据量很小，并没有去做一些一优化，稍微加了一个星星总数判断，但是没有什么改观。
但是如果数据量很大，有一点值得思考，类似KMP的字符串普配算法，对于星系的匹配判断是可以做优化的：
就是一个方向的检测失败，这个结果是可以使用到其他方向的，而且这个因素是这个星簇自己的属性。因此可能有这么一个算法:

当方向d1测试失败，所处scanner的位置（简单起见，用其中一个整数，行）i,有：
此时i之前的数据都是已知的，那么就会有一些方向不需要再匹配，另外一些方向只需要从某个scanner位置开始匹配。这个信息可以作为:
f(d1, i, d2) =
{
   = -1 :不可能匹配
   or d2 scanner的起始位置 (i,j)。
}//d2是新的一个方向


那么每当得到一个cluster,就可以求出这个f的集合。可以自己和自己匹配得到。
比如：
[XXXXXX]
[XXXXXX]
[------]
[VVVVVV]
[VVVVVV]
x和v表示某两个方向的匹配成功，那么对x的来说，一次匹配失败如果在-----，那么到v的方向在匹配只需要到----
开始，如果在XXXXX就完蛋了，那么V也没必要比较。

这样做要增加空间复杂度来存储这些信息。降低星簇查找形同的匹配算法的时间复杂度常数因子。但是对于数据量很小，感觉得不偿失，自己和自己的匹配也是要时间的。这个想法也是一个粗糙的，没去实现，工作比较忙，也没什么时间

#include "stdio.h"

#define MAX_STAR 160
#define MAX_CLSTR 501
#define DIR_NUM 8
#define MAX_W   101
#define MAX_H   101

static char sky[MAX_H][MAX_W];
static int  tag[MAX_H][MAX_W];
static int w;
static int h;
   

typedef struct cluster_t
{
    /*int x[MAX_STAR];
    int y[MAX_STAR];*/
    int start_c;
    int start_l;
    int end_c;
    int end_l;

    int num;
   
    int  idx;
    char mark;
}TCluster;

typedef int (* _scanner_check_dir_fct)(TCluster * c1, TCluster * c2);
typedef int (* _scanner_step_dir_fct)(
    int *pi, int *pj, int sc, int ec, int sl, int el);

TCluster clusters[MAX_CLSTR];
int clusters_count = 0;

static int
simlar_check_star(
   TCluster * c1, int i1, int j1, TCluster *c2, int i2, int j2)
{
    return (      
                    (tag[i1][j1] == c1->idx && tag[i2][j2] == c2->idx)                  
               ||   (tag[i1][j1] != c1->idx && tag[i2][j2] != c2->idx)
              
           );
}




static int
_scanner_check_dir_wh(TCluster * c1, TCluster * c2)
{
    int w1, h1, w2, h2;
    w1 = c1->end_c - c1->start_c + 1;
    w2 = c2->end_c - c2->start_c + 1;
    h1 = c1->end_l - c1->start_l + 1;
    h2 = c2->end_l - c2->start_l + 1;
    if(w1 == w2 && h1 == h2 && c1->num == c2->num)
    {
        return 1;
    }
    return 0;
}

static int
_scanner_check_dir_hw(TCluster * c1, TCluster * c2)
{
    int w1, h1, w2, h2;
    w1 = c1->end_c - c1->start_c + 1;
    w2 = c2->end_c - c2->start_c + 1;
    h1 = c1->end_l - c1->start_l + 1;
    h2 = c2->end_l - c2->start_l + 1;
    if(w1 == h2 && w2 == h1 && c1->num == c2->num)
    {
        return 1;
    }
    return 0;
}

static int
_scanner_step_dir_lrtb(int *pi, int *pj, int sc, int ec, int sl, int el)
{
   
    (*pj)++;
    if(*pj > ec)
    {
        *pj = sc;
        (*pi) ++;
        if(*pi > el)
        {
            return 0;
        }
    }
    return 1;
}

static int
_scanner_step_dir_rltb(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pj)--;
    if(*pj < sc)
    {
        *pj = ec;
        (*pi) ++;
        if(*pi > el)
        {
            return 0;
        }
    }
    return 1;
}

static int
_scanner_step_dir_lrbt(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pj) ++;
    if(*pj > ec)
    {
        *pj = sc;
        (*pi) --;
        if(*pi < sl)
        {
            return 0;
        }
    }
    return 1;
}



static int
_scanner_step_dir_rlbt(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pj) --;
    if(*pj < sc)
    {
        *pj = ec;
        (*pi) --;
        if(*pi < sl)
        {
            return 0;
        }
    }
    return 1;
}


static int
_scanner_step_dir_tblr(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pi) ++;
    if(*pi > el)
    {
        *pi = sl;
        (*pj) ++;
        if(*pj > ec)
        {
            return 0;
        }
    }
    return 1;
}

static int
_scanner_step_dir_btlr(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pi) --;
    if(*pi < sl)
    {
        *pi = el;
        (*pj) ++;
        if(*pj > ec)
        {
            return 0;
        }
    }
    return 1;
}

static int
_scanner_step_dir_tbrl(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pi) ++;
    if(*pi > el)
    {
        *pi = sl;
        (*pj) --;
        if(*pj < sc)
        {
            return 0;
        }
    }
    return 1;
}



static int
_scanner_step_dir_btrl(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pi) --;
    if(*pi < sl)
    {
        *pi = el;
        (*pj) --;
        if(*pj < sc)
        {
            return 0;
        }
    }
    return 1;
}



/*l:0, c:1*/
static int _scanner_start[DIR_NUM][2] = {
    {0, 0},
    {0, 1},
    {1, 0},
    {1, 1},
    {0, 0},
    {1, 0},
    {0, 1},
    {1, 1}};



static _scanner_step_dir_fct _scanner_step_funcs[DIR_NUM] = {
    _scanner_step_dir_lrtb,
    _scanner_step_dir_rltb,
    _scanner_step_dir_lrbt,
    _scanner_step_dir_rlbt,
    _scanner_step_dir_tblr,
    _scanner_step_dir_btlr,   
    _scanner_step_dir_tbrl,
    _scanner_step_dir_btrl
};

static _scanner_check_dir_fct  _scanner_filter_funcs[DIR_NUM] = {
    _scanner_check_dir_wh,
    _scanner_check_dir_wh,
    _scanner_check_dir_wh,
    _scanner_check_dir_wh,
    _scanner_check_dir_hw,
    _scanner_check_dir_hw,
    _scanner_check_dir_hw,
    _scanner_check_dir_hw
};


static int
is_same(TCluster * c1, TCluster * c2, int * pdir)
{
    int dir;
    int i1, j1;
    int i2, j2;

  

    for(dir = 0;  dir < DIR_NUM; dir ++)
    {
        if(_scanner_filter_funcs[dir](
            c1, c2) == 0)
        {
            continue;
        }
        i2 = (_scanner_start[dir][0] == 1)?(c2->end_l):(c2->start_l);
        j2 = (_scanner_start[dir][1] == 1)?(c2->end_c):(c2->start_c);

        for(i1 = c1->start_l; i1 <= c1->end_l; i1 ++)
        {  
            for(j1 = c1->start_c; j1 <= c1->end_c; j1 ++)
            {              
                if(simlar_check_star(c1, i1, j1, c2, i2, j2))
                {
                    _scanner_step_funcs[dir](
                        &i2,
                        &j2,
                        c2->start_c,
                        c2->end_c,
                        c2->start_l,
                        c2->end_l);
                    continue;
                }
                else
                {
                    goto LB_NextCheck;
                }
              
            }           
        }
        *pdir = dir;
        return 1;
LB_NextCheck:;
    }

    return 0;
}


static void
remark_as_old(TCluster * clstr, int curmark, int oldmark)
{
    int i;
    int j;
    for(i = clstr->start_l; i <= clstr->end_l; i ++)
    {
        for(j = clstr->start_c; j <= clstr->end_c; j ++)
        {           
            if(sky[i][j] == curmark && tag[i][j] == clstr->idx)
            {
                sky[i][j] = oldmark;
            }
        }
    }
    clstr->mark = oldmark;
   
}

static int
find_and_merge_cluster(int c_idx)
{
    int i;
    int dir;
    TCluster * clstr;
    TCluster * old_clstr;

    clstr = clusters + c_idx;
   
    for(i = 0; i < c_idx; i ++)
    {
        old_clstr = clusters + i;
        if(is_same(old_clstr, clstr,  &dir) == 1)
        {
            remark_as_old(clstr, clstr->mark, old_clstr->mark);
            return 1;  
        }
    }
    return 0;
}


static void
build_cluster(int c_idx, int i, int j, char cur_mark)
{
    if(i <>= h || j >= w)
    {
        return;
    }

    if(sky[i][j] == '1')
    {
        sky[i][j] = cur_mark;
        tag[i][j] = c_idx;
        clusters[c_idx].num ++;
      
        if(i < clusters[c_idx].start_l)
        {
            clusters[c_idx].start_l = i;           
        }
        if(j < clusters[c_idx].start_c)
        {
            clusters[c_idx].start_c = j;           
        }
        if(i > clusters[c_idx].end_l)
        {
            clusters[c_idx].end_l = i;           
        }
        if(j > clusters[c_idx].end_c)
        {
            clusters[c_idx].end_c = j;           
        }
     
    }
    else
    {
        return;
    }

    build_cluster(c_idx, i - 1, j - 1, cur_mark);
    build_cluster(c_idx, i    , j - 1, cur_mark);
    build_cluster(c_idx, i + 1, j - 1, cur_mark);
    build_cluster(c_idx, i + 1, j    , cur_mark);
    build_cluster(c_idx, i + 1, j + 1, cur_mark);
    build_cluster(c_idx, i    , j + 1, cur_mark);
    build_cluster(c_idx, i - 1, j + 1, cur_mark);
    build_cluster(c_idx, i - 1, j    , cur_mark);
}




static void
get_clusters()
{
    int i, j;
    int idx;
    char cur_mark = 'a';
   
    for(i = 0; i < h; i ++)
    {
        for(j = 0; j < w; j ++)
        {
            if(sky[i][j] == '1')
            {
                idx = clusters_count;

                clusters[idx].mark      = cur_mark;
                clusters[idx].start_c   = MAX_W + 1;
                clusters[idx].end_c     = -1;
                clusters[idx].start_l   = MAX_H + 1;
                clusters[idx].end_l     = -1;
                clusters[idx].idx       = idx;
               
                build_cluster(idx, i, j, cur_mark);
                /*Not found old the same*/
                if(find_and_merge_cluster(idx) == 0)
                {
                    cur_mark ++;
                }

                clusters_count ++;
            }
        }
    }
}

static void
output()
{
    int i;
    int j;

    for(i = 0; i < h; i ++)
    {
        for(j = 0; j < w; j ++)
        {
            printf("%c", sky[i][j]);
        }
        printf("\n");
    }

}

int p_1175_go()
{
    int i;
    int j; 
    char inp;

    scanf("%d\n", &w);
    scanf("%d\n", &h);

    for(i = 0; i < h; i ++)
    {
        for(j = 0; j < w; j ++)
        {
            scanf("%c", &inp);           
            sky[i][j] = inp; 
            tag[i][j] = -1;
        }
        scanf("%c", &inp);
    }
   
    get_clusters();
    output();    
}
int main(void)
{
   
    p_1175_go(1175);
}

BT的第一题

做ACM题计划刚开始就让自己撞了个大钉子，随便选了一个题目，1011，没想到是个超级BT的搜索剪枝题。
Description

George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.
Input

The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.
Output

The output should contains the smallest possible length of original sticks, one per line.
Sample Input

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
Sample Output

6
5刚看到这个题目觉得还挺简单的，（其实主要原因是有个中文翻译-_-~~). 大概思路就是一开始根据题目的条件有范围确定，接着就是可以回朔搜索了。搜索的时候要剪枝。。.
但是做了就知道根本不是这么简单的。TLE了无数次。
问题的特点就是除了快速求满足一个长度棍子的解之外，还得快速去掉解。
第一个很容易想到的，求解范围，需要整除棍子长度之和，不能小于最大的小棍子长度，个数在小棍子数之内。这些想不到，这题目直接88.
然后搜索的策略，我一开始就走的不对，一开始的方案是让小棍子选择原始棍子的标号搜索，然后剪去原始棍子标号重复。但是这个办法剪枝太难了，因为很容易进入很深的搜索却还对局势没有掌握。放弃。
只能一根根根子去求解，这里面剪枝就多了，棍子排序（自然会想到排序的，快点从大棍子的失败中解脱，并且在后面是的搜索本身呈现顺序性，易于剪枝），然后就是单独原始棍子的后续不要重复的剪枝，还有一个同一长度不在再次使用（在前面排了序，这儿就方便了）的剪枝。有些明显的东西比如长度要刚好满足一个棍子不能叫做剪枝了。上传TLE. TLE. TLE .......
上班比较忙，周末回家才想了一些新办法，但是不知道有些剪枝是不是有问题，最后找到几个可能的剪枝，但是实现起来，代码看着越来越烦了，真不想做了，后来才发现代码里有个保守的错误，这个错误改掉。AC.....大概600MS,虽然不是0MS，我也满意了，痛苦啊。。虽然还有可剪的，但是我已经不想再折磨自己了。
后来才知道1011是个经典的，BT的搜索剪枝题目。
BS 自己。

PS.那个排序用C qsort，速度比泡泡慢 -_~
代码改了很多，看着有点想吐！
#include "stdio.h"

int inp_b[64];
int inp_c = 0;
int min_inp;
int max_inp;
int curL[64];
int curCount[64];

/*int dbg_lay[64][5];*/
int lay[64][64];
int maxC;
int minL;

int used[64];
int usedCount = 0;
static int curSrcIdx;

#define USE(idx)\
do{\
used[idx] = 1;\
curL[curSrcIdx] += inp_b[idx];\
curCount[curSrcIdx] ++;\
usedCount ++;\
/*dbg_lay[curSrcIdx][curCount[curSrcIdx] - 1] = inp_b[idx];*/\
lay[curSrcIdx][curCount[curSrcIdx] - 1] = idx;\
}while(0)
#define UNUSE(idx)\
do{\
curL[curSrcIdx] -= inp_b[idx];\
used[idx] = 0; \
curCount[curSrcIdx] --;\
usedCount--;\
/*dbg_lay[curSrcIdx][curCount[curSrcIdx]] = 0;*/\
lay[curSrcIdx][curCount[curSrcIdx]] = 0;\
}while(0)

static int tryloop2(int lastIdx)
{
int idx;
int last = 100000;
int ret;
  
if(inp_c - usedCount < idx =" lastIdx;" last =" inp_b[idx];" cursrcidx ="="" ret =" tryloop2(lay[curSrcIdx" cursrcidx ="="" ret ="="" ret ="tryloop2(idx))" ret ="="" i =" 0;" i =" 0;" usedcount =" 0;" cursrcidx =" 0;"> *((int *)p2) )
{
 return -1;
}
else if(*((int *)p1) < *((int *)p2))  {   return 1;  }  else   {   return 0;  } } void b_sort(int inp_b[], int inp_c) {  int i;  int j;  int t;  for(i = inp_c - 1; i >= 0 ; i --)
{
 for(j = 0; j <> inp_b[j])
  {
   t = inp_b[j + 1];
   inp_b[j + 1] = inp_b[j];
   inp_b[j] = t;
  }
 }
}
}
int main(void)
{

int i;


int s = 0;


while(1)
{
 scanf("%d", &inp_c);
 if(inp_c == 0)
 {
  return 0;
 }

 for(i = 0; i < s =" 0;" max_inp =" 0;" min_inp =" 100;" i =" 0;"> inp_b[i])
  {
   min_inp = inp_b[i];
  }
  if(max_inp < max_inp =" inp_b[i];" maxc =" inp_c;"> 0; maxC --)
 {
 
  if(s % maxC == 0)
  {
   minL = s/maxC;
   if(minL < max_inp)
   {
    continue;
   }
  
   //An possible minL;
   if(start_tryloop() == 1)
   {
    break;
   }
  }
 }
}
}

在Linux下面开发GL

自从开始用DFB重新实现GL,但是终于要到目标平台上面做Porting,效果很差，问题很多。这段时间都很忙。看得很紧，今天终于出来界面了，但是问题太多了。Linux和以前的嵌入式的OS差距太大了。首先问题就是地址，以前的地址都是没有用户空间和内核空间的区别，现在有了，问题就出来了，关键是以前留下的代码很难更改。加上要实现的接口是一个用了好几年的一个庞大的库，自我有对下面Driver的依赖，转接到DFB上面也是相当的麻烦的扭捏。 这段时间到时真的学了一点点Linux开发，不过到现在Linux命令还不熟，真倒。

难写25周岁之后

2月6号过去了，还是个除夕。在窗外一片白茫茫中，和爸妈一起迎来了我的25周岁。 本来想做个25年来的大总结，大反省，大计划。可是一打开Blogger,就手发僵，不愿多写。又不是皇帝老子，粉饰和批评都没啥意思。 想写一个流水帐，把我记住的故事写下来，人不能丢掉记忆。我想写我的小学，中学，大学，想写我的亲人，朋友，爱人，想写编程，漫画，游戏... ...25年经历的东西太多了，怕自己忘记，可又怕写的不好，反而让美好的东西变成俗套。 我以为在这篇BLOG会写很多东西，但是这件草稿一直都没办法继续下去。以后看看找点系列来写。。。BS 自己

雪灾黄丝带

我们都想回家过年！ 请关注中国雪灾 虽然近在咫尺，我确都不一定能回成家。车票紧张，车更紧张。

最近不顺！

最近凡事不顺啊，没有一件顺心的。 1.尾牙没有中奖，连个安慰奖都没有，。。。。 2.一次奇异的团队组建活动，ORZ那些袜子的味道！ 3.工作烦躁。那些扭曲的接口，真恶心。

尾牙未中奖

昨天晚上尾牙，没有中奖！郁闷！

又被拉走

因为一个组做嵌入Linux到平台，实现Graphics library出现困难。我又被拉过去了。这次要用DirectFB. 其实我现在对2D的Graphics早就没什么兴趣，但是没办法，吃饭问题。 忘了，祝福BT聚会在我不能出席的情况下圆满成功!

设计过度有时候也是一种设计不足

一般我不太喜欢去记录软件工程方面的思考，容易泛泛而谈。今天到时有点想法记录一下，也是对自己的警醒。 经常听到两个词，设计过度和设计不足。有极限编程和重构等帮助下，过度设计肯定被认为是不好的。但是设计不足一般会用简洁作为借口来掩盖。当然，在一个成熟的团队中，明显的设计不足一般是不存在的。 某些快速开发中，强调变化和简洁设计。但是初期如果没有大观的的设计部署，有时候也是比较失败的事情。即使强调了简洁，也会有不可避免的设计过度。因为整体的设计不足可能导致某个局部的模块设计过度，这样的例子是有的。缺乏大局控制才导致的整体设计不足却用局部的过度来试图弥补。

新年展望

最重要的是找到新的生活方式，让自己快乐起来！走出抑郁的感觉。 最大的愿望是家人和我都身体健康，没有什么烦恼。 关于编程，还有很多有意思的东西可以去做。也是将来生活的乐趣之一。 继续打乒乓球，唯一的锻炼身体的方式，也是生活乐趣之一。 08年会拿到房子，还要装修，希望能不那么痛苦的熬过那段可怕的日子，反正就是把钱往里扔。 工作继续现在的态度，不用太热，也不能太冷，养家糊口。可能会有很烦，很忙，很累。