你应该知道的几件事情
请到下面的链接看吧，我就不转载了。教育网的同学需要代理访问。
davies 发表于 2008 年 07 月 3 日 | 1 条留言
用 Q 求解回文数等
有人用 J 语言来解决欧拉问题 36，我用 Q 语言的解法为：
q)0 {x+y*(all yy=reverse yy:string y)&all b=reverse b:(-32+b?1b)#b:0b vs y}/ til 1000000
或者
q)sum where {all (x=reverse x:string x),b=reverse b:(-32+b?1b)#b:0b vs x} each til 1000000简要说明一下：
是否是十进制的回文数：{all x=reverse x:string x}
是否是二进制的回文数：{all b=reverse b:(-32+b?1b)#b:0b vs x}
产生一百万以下的数组：til 1000000
如果用 K 语言来写，肯定跟 J 语言一样短而晦涩。Q 语言的可读性还是强不少的。
他还做了第35题，用 Q 语言实现如下：
q) repu:{raze $[1<n:count x;x {x[y] ,/: repu x _y }/: til n;x]} /全排列
q) primes:00b,999998#1b / 初始化质数标志位
q) {$[primes[x];primes[x*2_til floor 1000000%x]:0b;0b]} each 2+til 499999 / 标记非质数
q) sum where {all `boolean$ primes "I"$repu string x} each til 1000000 /
Q 还是相当精炼的语言，唯一的不足是不知道怎么实现惰性求值，或者协程(concurrence)，有的话可以进一步提高效率。
davies 发表于 2008 年 06 月 10 日 | 0 条留言
志愿者归来
上周五由重庆转机回到北京，结束了志愿者使命。这些天的事情比较繁杂，心情也跌宕起伏，无法用一两句话来概括，所以请不要问我“感受如何”之类的问题，实在难以回答。
这几天的见闻，没什么特别的，大体上如媒体所说，总体上是很好的，也有个别让人心寒的。
现在秀水镇已经在逐步恢复正常生活，灾后重建将是一个漫长的过程，需要从长计议。感觉自己在那边已经做不来多少很有用的事，于是就回来了。
从全国各地涌来的热心志愿者，如果没有医疗救护方面的特长，一般都是配合红十字协会做一些后勤保障方面的工作，了解灾区的情况，申请物资，运送物资，再协助配发到灾民手里。当然也有一些有实力的户外运动爱好者，可以到山区去帮助村民撤离到安全地带。
志愿者的力量毕竟有限，重要的问题还是得依赖政府组织人力来解决，诸如救援、安置、防疫、重建等。在那些政府力量未能照顾到的地方，志愿者的灵活机动就发挥了优势，可以查漏补缺，他们的热情可以温暖人心。
如果需要，我还会是一名志愿者，不求顶天立地，但愿尽心尽力。
davies 发表于 2008 年 05 月 26 日 | 12 条留言
第一批北京志愿者的工作情况
第一批北京志愿者于15号下午一点左右从北京出发，三点抵达成都，到成都红十字协会报到，安排随运送物资的车队前往绵阳市安县秀水镇，另有两名志愿者加入（共16人），补充好三到五天的食品，晚上八点出发，夜里一点到达，在一所集散救灾物资的中学操场上扎营。
第二天大家分散到周围的村子了解受灾情况。大部分房屋已经倒塌，少数未倒也是危房，不能住人，当地百姓住在损毁房屋附近的自制简陋棚子里。所幸地震时正是农忙，大部分村民都在天地里，伤亡不算严重，初步估计两三百人遇难。秀水镇目前有七万民众，缺水缺粮，救灾物资短缺加上配送速度不够，难以满足需求。我们将了解到的情况快速反馈给红十字协会，请求增援短缺物资和志愿者，到这条晚上，情况大大好转，大量救灾物资到达，并且县里的工作组在本地召集乡村了几百米志愿者来配发物资。现在有大量的物资需要投放到灾区，物资的运输和分配的工作量很大，当地的志愿者扮演了很重要的角色，效率也很高，大家都在战斗。
目前补充到秀水镇的只有瓶装纯净水，难以满足居民的生活饮用水需求，只能到邻近的白水河等取水，都知道水质很差但不得不用。我们四处联系检测水质量的方法和途径，由于通信等各方面问题导致进展缓慢。很高兴的是，下午得知省环保局的工作人员已经在当地采集水就地检测，今天凌晨发布检测结果说当地的水源未受到地震影响，各项指标均符合生活饮用水标准。没电导致水泵无法工作，生活饮用水仍然是个问题，需要尽快想办法解决。
昨天夜里，部分志愿者搭乘物资车辆返回成都，补充一些急切但又需求量不大的物资，同时连夜将我们的所了解到的情况汇总，通过互联网的形式发布出来，为后面的志愿者行动提供参考，完成任务后将立即返回秀水，之后可能会进一步扩大工作的范围。继续留在秀水的志愿者继续了解更为偏远的乡村的情况，尽力为村民解决一些问题。
2008.5.17 上午九点 成都
davies 发表于 2008 年 05 月 17 日 | 19 条留言
大量小文件的实时同步方案
传统的文件同步方案有rsync(单向) 和 unison(双向)等，它们需要扫描所有文件后进行比对，差量传输。如果文件数量达到了百万甚至千万量级，扫描所有文件将非常耗时。而且正在发生变化的往往是其中很少的一部分，这是非常低效的方式。
之前看了Amazon的Dynamo的设计文档，它们每个节点的数据是通过Hash Tree来实现同步，既有通过日志来同步的软实时特点(msyql, bdb等)，也可以保证最终数据的一致性(rsync, unison等)。Hash Tree的大体思路是将所有数据存储成树状结构，每个节点的Hash是其所有子节点的Hash的Hash，叶子节点的Hash是其内容的Hash。这样一旦某个节点发生变化，其Hash的变化会迅速传播到根节点。需要同步的系统只需要不断查询跟节点的hash，一旦有变化，顺着树状结构就能够在logN级别的时间找到发生变化的内容，马上同步。
文件系统天然的是树状结构，尽管不是平衡的数。如果文件的修改时间是可靠的，可以表征文件的变化，那就可以用它作为文件的Hash值。另一方面，文件的修改通常是按顺序执行的，后修改的文件比早修改的文件具有更大的修改时间，这样就可以把一个目录内的最大修改时间作为它的修改时间，以实现Hash Tree。这样，一旦某个文件被修改，修改时间的信息就会迅速传播到根目录。
一般的文件系统都不是这样做的，目录的修改时间表示的是目录结构最后发生变化的时间，不包括子目录，否则会不堪重负。因为我们需要自己实现这个功能，利用Linux 2.6内核的新特性inotify获得某个目录内文件发生变化的信息，并把其修改时间传播到它的上级目录(以及再上级目录)。Python 有 pyinotify，watch.py的代码如下：
在已经有Hash Tree的时候，同步就比较简单了，不停地获取根目录的修改时间并顺着目录结构往下找即可。需要注意的是，在更新完文件后，需要设置修改时间为原文件的修改时间，目录也是，保证Hash Tree的一致性，否则没法同步。mirror.py的代码如下
如果源文件不在同一台机器上，可以通过NFS等共享过来。或者可以通过支持列目录的HTTP服务器来访问远程目录，mirror.py 已经支持这种访问方式。server.py 是用webpy做的一个简单的只是列目录的文件服务器。由于瓶颈在IO上，它的性能不是关键。server.py的代码如下：
为了获得更好性能，以达到更好的实时性，Hash Tree最好是平衡的，比如BTree。如果一个文件发生变化，同步它需要进行的IO操作为N*M，其中N为数的层数，M为每层的文件数目。现在我们N为2，M最大为10000，适当减少它可以获得更好的性能，比如N为4，M为100。在以后创建目录结构时，最好能够考虑这方面的因素。
之前hongqn推荐过一个利用inotify的文件同步方案，同步方式类似于mysql和bdb等，由于过于复杂导致不可靠而没有采用。上面这个方案只用了一百多行Python代码就基本解决问题了，是不是很帅？:-)
davies 发表于 2008 年 04 月 24 日 | 6 条留言