2008年5月8日
流是通过延时求值实现的,Ruby中实现stream也是可以做到,可惜就是没有尾递归优化。按照sicp,首要的是两个函数:delay和force:
def mem_proc(exp)
alread_run=false
result=false
lambda{
if !alread_run
result=exp.call
alread_run=true
result
else
result
end
}
end
def force(delayed_object)
delayed_object.call
end
def delay(exp)
mem_proc(lambda{exp})
end
delay函数返回延时对象,就是对于未来某个时间求值表达式的承诺;force函数以延时对象为参数,进行相应的求值工作,这里的mem_proc用于记忆已经求值过的表达式。定义stream的constructor和selector函数:
def cons_stream(a,b)
return a,delay(b)
end
def stream_car(s)
s[0]
end
def stream_cdr(s)
force(s[1])
end
def stream_null?(s)
s.nil? or s==[]
end
用Ruby中的数组充当“粘合剂”,stream_car直接返回第一个元素,而stream_cdr需要用force求值表达式,履行承诺。另外,将空数组[]作为the-empty-stream。再定义几个高阶函数,map和foreach,其他如filter与此类似:
def stream_enumerate_interval(low,high)
if low>high
return []
else
cons_stream(low,stream_enumerate_interval(low.succ,high))
end
end
def stream_ref(s,n)
if n==0
stream_car(s)
else
stream_ref(stream_cdr(s),(n-1))
end
end
def stream_map(proc,s)
if stream_null?(s)
[]
else
cons_stream(proc.call(stream_car(s)),stream_map(proc,(stream_cdr(s))))
end
end
def stream_for_each(proc,s)
if stream_null?(s)
:done
else
proc.call(stream_car(s))
stream_for_each(proc,stream_cdr(s))
end
end
def display_stream(s)
stream_for_each(lambda{|item| puts item},s)
end
def stream_filter(pred,s)
if stream_null?(s)
[]
elsif pred.call(stream_car(s))
cons_stream(stream_car(s),stream_filter(pred,stream_cdr(s)))
else
stream_filter(pred,stream_cdr(s))
end
end
最后,看下例子:
puts "s:"
s=stream_enumerate_interval(1,5)
display_stream(s)
puts "odd_s:"
odd_s=stream_filter(lambda{|x| x%2==1},s)
display_stream(odd_s)
puts "ss:"
ss=stream_map(lambda{|x|x*x},s)
display_stream(ss)
2008年5月5日
前段时间看了这篇文章《
Ropes:理论与实践》。这两天为了提高工作中某个系统对外接口的效率,才认真学习了一番。本质上Ropes是将字符串表示为一棵二叉树,特别适用于长字符串的处理,貌似c++ STL库中也有这么个实现。具体实现和原理还是看这篇
paper。《
Ropes:理论与实践》一文中给出的测试数据相当惊人,Ropes比之String和StringBuffer在append,insert,delete等操作上的效率都有一个数量级以上的差距。跑下作者给出的测试程序,其实在测试的字符串不是很长的情况下,这个差距并没有那么大,这也从侧面说明了Rope的应用范围:即只有在大量修改大型字符串的应用程序中才能看到明显的性能提升。那么是否可以用Rope替代StringBuffer做append生成字符串(比如我要的生成xml)。作者也说啦:
“由于
Rope 的附加性能通常比
StringBuffer 好,这时使用 rope
是否有意义呢?答案还是否。不论何时将输入的数据组合在一起形成格式化输出时,最漂亮最有效的方法是使用模板引擎(例如 StringTemplate
或 FreeMarker)。这种方法不仅能干净地将表示标记与代码分开,而且模板只进行一次编译(通常编译为 JVM
字节码),以后可以重用,从而使它们拥有极佳的性能特征。”
我用Rope for java替代了StringBuffer做XML生成,效率提升在5%-30%左右,xml字符串不是很长,这个提升显然有限,也带来了不必要的复杂度。因此最后还是用Velocity模板引擎来生成XML,测试的结果效率并没有多少改善,但是显然更容易维护和开发了。回到Rope的话题,我用Ruby实现了个版本,Rubyforge上有一个Rope的实现,但是看了源码,与paper所述算法有点差异,因此照着Rope for java也实现了一个
Rope4r。测试的结果证明在长字符串的累积操作上,Rope4r的append比之String的+=性能可以快上3倍左右,而如果采用String的<<操作,不是immutable的,当然是最快了;比较郁闷的是slice和insert操作都比String的慢上几倍,因为Ruby的String、Array的内建对象都是直接用c写成并做了优化的,我猜测原因在这。
2008年4月28日
我们现在做的项目是典型的小型项目,整个组也就4、5个人,一个迭代周期基本在两周左右。尽管没有明确有“迭代”这么说法,却是以业务人员的策划案做分期实现。这个分期,按我的理解其实就是迭代。最近发现的一个问题是,在迭代开始后,业务人员却没有办法保证需求在这个迭代周期完成前的稳定性,甚至在各个模块集成之前,大家就提出N多意见,并且这些意见很多时候都是前后矛盾的。特别是在客户端的开发上,显然,客户端UI和操作习惯方面是最多变的地方。可怜我们公司唯一的MM程序员快陷入变更频繁的泥潭了,改过去改回来是家常便饭。其实也是她过于老实,要我来说,你们要改,可以,但是我要向业务人员确认,他是我唯一的变更来源,你们有什么需求向他反应,他来收集和甄别。在《敏捷软件开发》中说到,迭代开始后,客户就同意不再更改当次迭代中的素材的定义和优先级别,可惜这一点貌似很难做到了,业务人员经常屈从于管理层或者其他小组意见的压力。在我看来,在当次迭代完成前的所有建议或者说需求,都可以收集起来,由业务人员负责收集、甄别和决定,放入下一个迭代版本的开发,因为我们的迭代周期一般也在两周左右,这个周期足够辨别这些需求的合理性和响应需求的及时性,而不是像现在这样大家七嘴八舌地提意见,技术人员疲于奔命,乃至于发脾气(入夏真是脾气坏的季节);系统各部分迟迟无法进行集成测试,造成新的修改意见没有做完,预定的迭代版本的更无法按时完成的局面。
山僧昔在双径归堂,未及一月,忽于睡中疑著万法归一,一归河处?自此疑情顿发,废寝忘食,东西不辨,昼夜不开,开单展钵,屙屎放尿,至于一动一静,一语一
默,总只是个一归何处,更无丝毫异念,了不可得。正如钉钉胶粘,摇撼不动,虽在稠人广众之中,如无一人相似。从朝至暮,从暮至朝,澄澄湛湛,卓卓巍巍,纯
清绝点,一会万年,境寂人忘,如痴如兀,不觉至第六日,随众在三塔讽经次,抬头看见五祖演和尚真,蓦然触发日前仰山老和尚问拖死尸句子,直得虚空粉碎,大
地平沈,物我两忘,如镜照境,百丈野狐,狗子佛性,青州布衫,女子出定语,从头密举验之,无不了了。般若妙用,信不诬矣。(见《古尊宿语录》)
想来王阳明龙场悟道的感觉也不过如此。王阳明的心学归结就是“致良知”三个字,不说“致”,仅“良知”二字就是何等宝贵?看看安徽阜阳儿童们的命运,这个接二连三发生诡异事件的地方,当地的公仆们可有“良知”在心中?我们保留了文化传统,却抛弃了传统文化。
2008年4月23日
在blogjava和javaeye上的两个blog的顶部广告都售出了,热烈庆祝:)


准备啥时候去绑定个支付宝,把我的一块五毛钱取出来,刚好够买两个包子

。还是阿里妈妈好,来的实在,google广告的1.2美元这辈子看来是指望不上了,人民币还在持续升值中......
2008年4月22日
推荐两篇blog:
《java NIO 类库selector机制解析(上)》
《java NIO 类库selector机制解析(下)》
有一个奇怪的现象引出的话题,为了
Selector.wakeup功能做到跨平台,每个Selector.open()时,在Windows会建立一对自己和自己的loopback的TCP连接;在Linux上会开一对pipe(pipe在Linux下一般都是成对打开)。java为了跨平台真是无所不用其极,此中冷暖谁知啊。
2008年4月19日
17日的南方周末的一篇报道《17岁的残酷青春》,让我心神不宁,甚至昨日晚上做了噩梦。我很奇怪,每次看报纸,看到不正常的事总是愤愤地发表一番评论,乃至于老婆认为我有毛病:)。原文在
这里
想的最多的是一个词,不停的在脑海中打转——异化。是什么样的原因让一个17岁的少年做出如此残忍的事情?对自己爱慕的同班同学下手,并冷静地分尸抛尸。是什么样的因素让他的情感异化到这样的地步?不热爱生命,不尊重生命。如果不热爱自己的生命,那是不可能尊重生命的。仅仅是网游的问题吗?这样的总结是不是太苍白了。文章的最后,记者听到少年们说他们大多数都有心理问题,就问是什么问题呢?“他和其他几名“90后”学生互相看了看,一脸茫然”。茫然是正常的,茫然和郁闷也是我中学时代最常用的字眼,认为全世界没有人理解自己,其实问题在于我没有想去理解这个世界,理解身边的人,特别是父母。可是再怎么茫然,不应该也不至于做出如此残忍的事情,对生命的漠视到如此程度,有没有想过?那可是一条鲜活的生命啊!作为人的情感是怎么异化到这样的程度?其实从文中也可以看出蛛丝马迹:长期与父母分离,家庭充斥着“吵架”、“离家出走”,沉迷于网络,喜欢血腥读物和影视作品,个性上的孤僻和冲动,对学校生活的厌恶......而根本的原因在哪?我不知道答案,社会问题?电影分级什么时候出来?网吧禁止未成年人入内什么时候真正做到过?留守孩子的心理问题谁有关注过?教育问题?填鸭式的、应试为目的的教育什么时候能真正改革?我们时候才能真正地以培养“
人”、培养合格的公民作为我们的教育目标?这一连串的问题可以继续追问下去,却不知道答案什么时候会存在。
我现在还不敢再去看一遍《
牯岭街少年杀人事件》,我昨天还在想,伟大的电影总是不敢看第二遍,看这样的电影的时候,感觉灵魂在煎熬。
最后,请热爱生活。
2008年4月17日
最近碰到个需求,计算游戏得分的规则,类似这样:
|
游戏人数
|
第一名获得赌注
|
第二名获得赌注
|
第三名获得赌注
|
第四名获得赌注
|
|
二人
|
100%
|
0%
|
—
|
—
|
|
二人(出现2个第1名时)
|
50%
|
50%
|
|
|
|
三人
|
70%
|
30%
|
0%
|
—
|
|
三人(出现3个第1名时)
|
33.3333%
|
33.3333%
|
33.3333%
|
|
|
三人(出现2个第1名时)
|
50%×2
|
0%
|
|
|
......
......
这些奖励规则没有什么规律,随着人数增多,就越发复杂了,并且业务人员可能随时改变这些规则。
显然,奖励规则可以采用策略模式,定义策略接口,根据游戏人数定义不同的规则,本质上就是利用动态的多态调用。可以想见,还是少不了复杂的case...when语句,以及繁多的代码。恰好最近读《unix编程艺术》和《代码大全2》,两者都提到一个结论:人类阅读复杂数据结构远比复杂的控制流程容易,或者说数据驱动开发是非常有价值的。《代码大全2》声称这个是表驱动法。因此,这个奖励系数的计算,能否转化成一个查表过程呢?注意到,在游戏中,名次是根据个人的积分在所有玩家中的排位来决定,大概会有这么个排序的玩家积分数组[100,50,3],这个数组表示3个玩家,第一名100分,第二名50分,第三名才3分。依据规则,第一名的奖励系数就是0.7,第二名就是0.3。我想到类似这样的数组其实都有个形式表示它们的内置结构,比如[100,50,3]数组的“结构”是"111",代表3个位置都有一个人。将"111"作为关键码去查表不就OK了?
将每个排好序的积分数组解码为这样的关键码,然后去查预先写好的奖励系数表,这个奖励系数表大概类似:
@@award_rate_hash={
:"2"=>{
:"11"=>{:"1"=>1,:"2"=>0},
:"20"=>{:"1"=>0.5,:"2"=>0.5}
},
:"3"=>{
:"111"=>{:"1"=>0.7,:"2"=>0.3,:"3"=>0},
:"300"=>{:"1"=>0.33},
:"201"=>{:"1"=>0.5,:"3"=>0},
:"120"=>{:"1"=>1,:"2"=>0}
},
:"4"=>{
:"1111"=>{:"1"=>0.65,:"2"=>0.30,:"3"=>0.05,:"4"=>0},
:"4000"=>{:"1"=>0.25},
:"3001"=>{:"1"=>0.33,:"4"=>0},
:"1300"=>{:"1"=>1,:"2"=>0},
:"2020"=>{:"1"=>0.5,:"3"=>0},
:"1201"=>{:"1"=>0.7,:"2"=>0.15,:"4"=>0},
:"1120"=>{:"1"=>0.7,:"2"=>0.3,:"3"=>0},
:"2011"=>{:"1"=>0.35,:"3"=>0.3,:"4"=>0}
}
}
一个三级hash表,首先根据玩家人数查到特定的系数表,比如要查3个玩家、积分数组是[100,50,3]的奖励系数表就是
@@award_rate_hash[:"3"],然后积分数组[100,50,3]
解码为:"111",继续查,如此规则的奖励系数表就是@@award_rate_hash[:"3"][:"111"]——也就是 {:"1"=>0.7,:"2"=>0.3,:"3"=>0},那么查积分是100的玩家系数就是@@award_rate_hash[:"3"][:"111"][([100,50,3].index(100)+1
).to_s.to_sym],也就是:"1"=>0.7。[100,50,3].index(100)+1
就是积分100的玩家在数组中的名次(即1),也就是:"1"指向的结果0.7。其他玩家的查表过程与此类似,不细说了。
这样,我们所有的奖励规则就是维护这么一张hash表,这个表看起来复杂,其实完全可以自动生成,让业务人员来提供样例数据,解码样例数据并生成这个表是很简单的事情。积分数组的“解码”,我给一个Ruby版本:
#解码数组为字符串关键码
def decode_array(array)
len=array.size
trace_list=[]
result=[]
len.times do |time|
result[time]=0
trace_list[time]=false
end
array.each_with_index do |item,index|
result[index]=count_times(array,trace_list,index,len)
end
return result.join('').to_sym
end
def count_times(array,trace_list,index,len)
item=array[index]
result=0
(index..len).each do |i|
if array[i]==item and !trace_list[i]
result+=1
trace_list[i]=true
end
end
return result
end
2008年4月16日
sicp的习题3.22,也就是以消息传递的风格重新实现队列,我的解答如下:
(define (make-queue)
(let ((front-ptr '())
(rear-ptr '()))
(define (set-front-ptr! ptr) (set! front-ptr ptr))
(define (set-rear-ptr! ptr) (set! rear-ptr ptr))
(define (empty-queue?) (null? front-ptr))
(define (front-queue)
(if (empty-queue?)
(error "FRONT called with an empty queue")
(car front-ptr)))
(define (insert-queue! item)
(let ((new-pair (cons item '())))
(cond ((empty-queue?)
(set-front-ptr! new-pair)
(set-rear-ptr! new-pair))
(else
(set-cdr! rear-ptr new-pair)
(set-rear-ptr! new-pair)))))
(define (delete-queue!)
(cond ((empty-queue?)
(error "DELETE! called with an empty queue" queue))
(else
(set-front-ptr! (cdr front-ptr)))))
(define (dispatch m)
(cond ((eq? m 'front-queue) (front-queue))
((eq? m 'empty-queue?) (empty-queue?))
((eq? m 'insert-queue!) insert-queue!)
((eq? m 'delete-queue!) delete-queue!)
(else
(error "Unknow method" m))))
dispatch))
(define (front-queue z) (z 'front-queue))
(define (empty-queue? z) (z 'empty-queue?))
(define (insert-queue! z item) ((z 'insert-queue!) item))
(define (delete-queue! z) ((z 'delete-queue!)))
由此,我才知道自己竟然一直没有想到,scheme完全可以模拟单向循环链表,整整第三章都在讲引入赋值带来的影响,而我却视而不见。在引入了改变函数后,数据对象已经具有OO的性质,模拟链表、队列、table都变的易如反掌。首先,模拟节点对象,节点是一个序对,包括当前节点编号和下一个节点:
(define (make-node n next) (cons n next))
(define (set-next-node! node next) (set-cdr! node next))
(define (set-node-number! node n) (set-car! node n))
(define (get-number node) (car node))
(define (get-next-node node) (cdr node))
有了节点,实现了下单向循环链表:
(define (make-cycle-list n)
(let ((head (make-node 1 '())))
(define (make-list current i)
(let ((next-node (make-node (+ i 1) '())))
(cond ((= i n) current)
(else
(set-next-node! current next-node)
(make-list next-node (+ i 1))))))
(set-next-node! (make-list head 1) head)
head))
make-cycle-list生成一个有N个元素的环形链表,比如(make-cycle-list 8)的结果如下
#0=(1 2 3 4 5 6 7 8 . #0#)
Drscheme形象地展示了这是一个循环的链表。那么约瑟夫环的问题就简单了:
(define (josephus-cycle n m)
(let ((head (make-cycle-list n)))
(define (josephus-iter prev current i)
(let ((next-node (get-next-node current)))
(cond ((eq? next-node current) (get-number current))
((= 1 i)
(set-next-node! prev next-node)
(josephus-iter prev next-node m))
(else
(josephus-iter current next-node (- i 1))))))
(josephus-iter head head m)))
从head节点开始计数,每到m,就将当前节点删除(通过将前一个节点的next-node设置为current的下一个节点),最后剩下的节点的编号就是答案。
2008年4月14日
《王阳明大传》序,作者:周月亮
一生极重践履的阳明,本身就象只鞋。这只鞋上插着高贵的权力意志的权杖。形成心学的倒T字型结构——不是十字架,也不是钻不出地平线的大众的正T字型。他的“致良知”工夫就是要你站在地平线上。然后脚不离地的无限的向上升华,把人拉成顶天立地的大写的人。
拔着头发离地球的是阿Q,当缩头乌龟的是假洋鬼子,只是鞋而无权杖的是读书没有悟道的士子。只耍权杖而不愿当鞋的是政治流氓——那个意志不是高贵的权力意志,只是反人道的独裁欲望。
阳明的心学是这样一种生活方式:既生活在这里,又生活在别处!
《明
史》阳明本传只附了一个学生,既因为别的成了气候的学生都有传,还因为这个学生最能体现阳明学的“鞋”精神,他叫冀元亨,他因去过宁王府而被当成阳明通宁
王的证据给抓起来,在锦衣卫的监狱里受百般折磨,但他对人依然象春风一样,感动得狱吏和狱友一个劲的哭,他把坐大狱当成了上学堂。所有的司法人员都以为
奇,问他夫人:“你丈夫秉持什么学术?”她说:“我丈夫的学问不出阃帏之间”。闻者皆惊愕不已。
但是,人皆在阃帏之间,谁有这种境界、风范?只生活在这里,反而得不到这里;单生活在别处,自然更得不到这里。
先作只鞋,再插上权杖,也不是阳明学的精神。那就是把鞋的大地性当成了手段,断断成不了圣雄,只能成为枭雄。
再高贵的鞋,也是踩在脚下;但路也正在脚下。不能生活在别处的人的所谓脚下之路,只是不得不走的路;有生活在别处之权力意志的人才能“践履”在希望的道路上。
在比做什么事成什么人更哲学的语义上说:穿什么鞋走什么路。
阳明这只鞋,至少有亲在性、超越性、诗性、葆真性、有应必变的践履性.....许多人最大的痛苦就是找不到一只合脚的鞋。阳明这只鞋可以叫真、善、忍;可以叫真、智、乐,叫六通四辟...
致良知,就是要你找到可以上路的合脚的鞋。致者,找也。能否找到呢?就看你肯不肯去找——因为,它就在你自身「心即理」。阳明这样解释孔子说的上智下愚不移——不是不能移,只是不肯移。
说无路可走的人,是没有握住自家的权杖,把生命的舵送给了别人——那人哪怕是上帝也会变成魔鬼——上帝的真诚包含着上帝的欺骗。
心学或曰阳明学并不给世人提供任何现成或统一的鞋,如果有那种鞋就是枷锁和桎铐了,心学只是告诉人们:每个人都能找到自己的那双合脚的上天堂的鞋——找这双鞋的工夫与上天堂的工夫是同一个工夫。
路在脚下,鞋在心中。你的任务是找与走,走着找,找着走,边找边走...
这样边找边走,就凸现出权杖的“权道”来——已发生语义转换,这个权道的“权”是秤砣、以及因此衍生的权衡、权宜的那个权。对于人心来说,权,就是“感应之几”,“几”就是微妙的恰好,象秤砣一样随被秤之物的轻重而变动,找到那个应该的恰好。所谓道,
就是“体乎物之中以生天下之用者也”「王夫之《周易外传》卷一」。权道就是追求“时中”即永远恰当的人间至道。约略等于具体问题具体分析这个马克思主义的活的灵魂。
没有这个权道,权杖只是个摆设,有了这个权道,权杖才能变成如意金箍棒,草鞋才能变成船,驶向理想的港湾。通权达变,是孔子认可的最高境界。不能通权达变就只能刻舟求剑、守株待兔...儒学在近代陷入困境就因为秉政的儒臣们失去了权道。
这个权道就是在践履精神上加上权变智慧——绝对不是无标准的变色龙、流氓。一讲权变就滑向流氓,为杜绝流氓就割断权道,都是找不到权道、反权道的表现。权,这个衡量万物的标准,用阳明的话说就是良知。良知在你心中,不用到别处去找。
所以,阳明这只鞋还带着秤砣,是风铃也是驼铃。