Shell's Home

May 28, 2012 - 1 minute read - Comments

语言的效率差异3

在总结前,我们首先搞明白三个问题的差异“效率的决定因素”,“语言效率差异”和“日常使用中造成运行效率差异的因素”。 代码的效率最根本因素绝对不是语言的效率,我一直这么确信。代码效率的决定因素必然是算法的正确选择和实现的优秀程度。这里面包括了正确评估问题,选择合适的数据结构,使用合适的算法等。例如对给定数据的高速查询,用红黑树去跑查询肯定跑不过预编译的哈希算法和哈希表。即使前者使用汇编实现,而后者只是python实现。(对于这点,我对比过一个大规模数据的查询,数据是固定的。数据库效率最差,C++用红黑树的map次之,效率最好的是python的dict,底层是hashtable。当然,为了防止某些人补充,我自己先说了——我最后用了stlport的hash_map) 语言效率的差异,有很多因素。例如编译型/解释型语言,动态语言和静态语言,是否带jit优化等,都会造成很大的性能差异。甚至同样是C,不同的编译和优化参数也会造成很大规模的差异,做优化的朋友一定心里有数。然而大多数情况下,决定语言效率的关键因素都不在语言自身的效率上,而是在于底层库实现的效率上。当然,如果底层库使用该种语言直接写成(我也比较喜欢这种风格),那么归根结底还是考验语言本身的效率问题的。以正则测试为例,实际上python是一种性能很差的语言,但是在测试上并不很低。因为python的库实现是直接引用了C库,其效率仅仅是C加上一个不高的值。而lua得分不足只能说是库的实现比python差。 最后一个问题相信大家最关心,即日常使用中造成运行效率差异的关键。到底是什么,决定了我们每天写的代码的效率? 可能要出乎大家的意料,从实际测试来看,实际上是测试能力和可变性。我们能够大致预料某些性能特别差的情况,然而对于性能在50%-200%以内变化的细节,实际上是很难提前预测的。也许我们会“猜测”某种情况性能比较优秀,但是实现下来情况可能完全不是这么回事。例如我曾经就一个C代码进行优化,预期应当能提高4倍性能,当时测试的结果是性能提高3-5倍,但是实际生产环境跑下来觉得没区别。后来发现,我自己测试用的是-O0,而生产系统是-O2。我的优化实际上在-O2的时候就全部被自动优化掉了。如果你觉得你的经验够丰富,能够预测-O2会优化你的哪些代码。那么你可以考虑一下,CPU的指令流水优化呢?系统上所安装版本的libc的实现细节和内核细节呢?如果都能精通,您可以忽略我这篇文章。但是对于我自己而言,我只能预计某个做法可能优化,而不能确定。 这时候,对于这个优化的实现难易程度,和实现完成后进行测量的难度就成为了关键。尤其是精确测量耗费时间的代码,执行时的瓶颈,这些能力才是优化代码的关键所在。我曾经写过为什么python效率不比C低,有人不服。我说了,并且反复强调了,这个仅限于“两者的生产速度一致”这个前提下。实际上如果真满足这个前提,大部分情况下C这边都输的没法测试的。因为完成同样任务,python的编码时间大约只有C的一半到1/4。即使算上优化,python完成项目的时间,C都不一定能写的完代码。更不提后面还要进行泄漏测试,复查,复杂的调试。等全部通过,开始关注效率问题,生产时间早超了。 作为日常生产,我想大部分程序员都有这么个经验。决定代码质量的实际上是项目的时间是否充裕,程序员是否用心严谨,生产流程管理是否到位。除非程序员太差劲,否则技术性代码质量差异并不特别多——一般都是远远小于赶代码造成的严重问题的。如果您那里不是这样,我建议您更换一批靠谱的程序员。同样,在真实的日常生产中,大部分项目都没有那个机会对代码进行多次的复查,深层次优化所有问题。基本是写,写完了查,没有什么表面问题。然后检查一下,用户体验效率是不是很差,找最差的地方优化一下,然后直接交货。很少有像理论代码那样,反复优化和测试,甚至受到来自不同程序员的交叉检测和沟通。如果有这种级别的反复优化,毫无疑问的,C会是常用语言中的效率之王。在shootout>给出的速度评测上,仅有Intel自己实现的fortran超越了C。当然,我相信汇编会更加优秀。 然而杯具的是,日常生产中恰恰相反,至少我是没什么时间去优化每行代码的。大部分时候,为了处理一个排序问题,我不会去网络上找一个vector库,而是直接开一个100的数组,然后qsort。前方报错了,改1000的数组。在写python的时候,也不会精细的考虑每个地方是否都用了合适的方法,某点是生成器好还是list好。大不了觉得某个程序慢了,cProfile一把,然后对着花时间最长的几个点看看是否有问题。自我感觉而言,python项目在做完之余,我还能泡个茶聊会天,自然也有功夫去看两眼代码,是否有哪里写的太难看了。而C代码就是不停的debug,即使我好容易喘口气,也绝对不会想去再看了。 最后说一下sbcl,在自身性能测试中,是当之无愧的语言之王。速度是python的一倍不到,代码量是python的一半。常规来说,出错概率,维护难度,都是和代码行数直接相关。一半的代码量基本就意味着维护成本削减一半,而一倍的速度基本和java持平,在C后面紧追不舍。但是,以上常理对lisp均不适用。lisp的学习难度惊人不说,维护难度和代码行数没有直接关系,而是取决于写作者的水平。水平越好的写作者,代码越容易维护,反之,初心者写出来的玩意那是看都看不懂的。冰河在博客上说他找了个职业lisp程序员的工作,人家视若珍宝。我不知道是哪年的blog,但是从老板的角度来说,这才是程序员的悲哀。老板喜欢什么语言?最好有个点子,跑去人才市场插个牌子,上书“我要人”。然后就会有一堆人云集过来,脖子上面都套着“五行一元”,“精通XXX”的草标。抓一只大个的,给个项目经理的头衔,让他管着别人。每个月扔一麻袋饲料下去,过两个月就能收程序了。 看起来和农场有点像,不是么?遗憾的是,lisp看来是达不到这个要求了。全国能用的python程序员不会超过5000,lisp程序员大概连500都不到。如果哪个老板不幸脑残,用了lisp来做项目,那么在招人这个问题上会比python更难执行。从这个意义上说,这才是lisp程序员不流行的关键——不好找工作。即使运行效率再高,语言本身再好,也没法过老板那关。

May 24, 2012 - 1 minute read - Comments

天朝重大灾害事件的行为思考

当事人 在天朝遇到重大灾害事件,当事人的指导思想是自主逃生,切切不可指望救助。这点不仅是在天朝,而且在全世界各个国家都同样成立。总体来说,天朝救助动员体系的效率在全球那是首屈一指的高。然而比较操蛋的事情是,往往在救助的时候会来几个记者或者领导。这时候不但不能快速把你救出来,而且在慢慢救助的过程中,你还会受到“你现在疼不疼阿”,“坚持住,我们的人民解放军马上就把你救出来拉”之类的废话骚扰。更操蛋的是,你还得表现出受灾的痛苦和得救的感激——不过鉴于天朝有效的动员体系,你就权当缴“表情税”了吧。 当然,在救助的时候,一个更可怕的事情是,你受灾的事实可能会对领导的政绩产生不良影响。因此,当有一点证据表明可以不救的时候,哪怕不足72小时,你都可能被直接埋掉。所以,更不要指望救助。 具体来说,有以下几个具体建议: 受到外来冲击的时候先护住头和胸,尤其是后脑勺。缺胳膊少腿的叫残疾人,缺脑袋少心脏的叫僵尸。 尽量逃离灾害现场。你永远不知道那里会再发生什么问题。 再贵的东西都没有命值钱。 被困等待救援的时候,最容易死亡的因素是缺水。如果你有瓶水,千万别浪费了。如果有个瓶子,千万别浪费自己的尿。如果你什么都没有,那就想法弄一个。 NGO 作为NGO,在灾害救助的时候,首要任务是组织,管理,信息传递。尤其是最后一个,千万注意时效。网上经常出现无效的求助,尤其是围脖出来后,情况尤其严重。有人曾经验证过,一条求助推,被转发上千次。但是之后的感谢推,只有不到百次。结果就是,事情已经做完,或者过时,但是信息还在传递。这种无效的信息垃圾,会严重的干扰救灾体系的运作。 作为一个比较好的对应方案,建议可以由几个人,携带便携电脑,在灾害现场收集信息,来源,时间,然后通过邮件发送给联系人。使用邮件的好处是,可以离线收集信息和编写,通过3G网络发送,信息量大,冗余数据消耗小,对带宽要求小。即使没有3G网络,邮件也可以通过tf卡携带工作(就是把邮件输出成EMAIL编码,托人带到有网络的地方发送)。不过,为了保证邮件发送人的可靠,建议考虑邮件签名技术。 受灾后,最重要的信息是,有哪些人受灾,他们需要什么物资,他们需要联络什么人(寻人报平安)。正确的第一现场信息,有助于征集社会资源,解决实际问题。为时效性考虑,每种信息都应当有一个注销和过期特性。 旁观者 作为旁观者,千万不要试图录像,或者表现出试图录像。如果你手机有偷拍能力,偷偷的拍是可以的,被发现了就删除,或者干脆把手机扔给对方,不要拿自己的命开玩笑。你对面一群人的领导,可能在这次灾害中锒铛入狱,也可能风平浪静。如果你的录像有害他入狱甚至挂掉的可能,他不会介意让你直接挂掉的。 如果你平时要救助别人,注意留下你不是肇事人的证据。但是在大型灾害面前,你没有被起诉的可能(总不能说地震是你搞的吧),因此不要吝啬于给与帮助。注意,在帮助别人的时候注意保护自己,不要轻易的到危险地带去帮助别人。如果你也变成当事人,别人还得帮助你。如果你挂掉了,家里人会伤心。 在灾害发生的第一时间,你的捐献不要考虑审计,红十字,之类的问题。就算知道有问题,你的捐献能够让多一个人活下来,就比坚持真相更有意义。然而做为后续捐助,我的建议是,自己做,或者不捐。中国的救助体系已经变成了一门生意,而且很不透明。当你不知道你的捐助做了什么用途的时候,你可以选择不捐助。当然,如果你和几个朋友(注意,这里一定需要互相认识,因为针对非特定对象的募集是违法的),有人愿意去开车送一些东西什么的,那会更好一些。 如果你到了现场,注意收集信息。在灾害信息全靠官方,官方信息全看领导的天朝,有个其他的信息流通渠道是非常重要的。 具体来说,有以下几个具体建议: 不要围观,尤其是在进出通道上围观。 看到有人受伤,不要着急忙荒抬着跑,先看看有没有伤,意识是否清醒。如果有骨折,固定后再移动,否则会产生二次伤害。 如果是外伤,尽力止血。如果外伤见骨,或者有脊髓液流出,不要着急包扎,谨防感染。可以在靠近心脏端进行扎紧,减少血流。 如果呼吸心跳停止,做CPR。CPR具体参考CPR手册,或遵医嘱。实在不会的,简单来说,捏住鼻子往嘴里吹气,然后胸压15次,两秒一次。特别注意,必须保持气管通畅,没有喉管闭合或者呕吐物堵塞,否则人工呼吸一下就送命了。另外即使出现心跳呼吸,也尽量坚持直到救护车来。当然,最后一点在灾区急救中就有点奢求了。

May 23, 2012 - 1 minute read - Comments

几个小技巧

virtualbox中使用物理硬盘 省略权限,物理硬盘分区结构基础知识,最核心只有一句话: VBoxManage internalcommands createrawvmdk -filename sdc -rawdisk /dev/sdc -relative 在不重启的情况下调试awesome的方法 省去安装和man,也只有一句: Xephyr -ac -screen 1024x768 -br :1

May 22, 2012 - 1 minute read - Comments

python中调用C的几种方法

引言 别废话了,我觉得这都应当是常识的。除去最后几种包装框架,剩下都是基本知识问题。即使不知道怎么做,也应该知道有这种方法。所谓经验,很多时候不是把知识装脑子里,而是把索引装内存,数据丢硬盘。 C模块 最基本的方法,直接写个C模块。具体很长,你去找python-doc,看“Extending and Embedding”这章,全看完就差不多了。如果没空,看几个例子就上也可以。 优点:基本没有,写起来很麻烦,要维护额外的C代码,还有交叉版本固定,跟随C升级等等麻烦。唯一的优点,就是这是唯一一个“绝对没有问题”的方法,而且没有额外依赖。如果下面几个路子全出了问题,就用C模块吧。 ctypes 去看python-doc的ctypes模块。本质上是提供一个C模块,去载入和使用其他模块。 优点:写起来很方便,修改便捷,而且跨各个python实现。 缺点:只能调用动态库,对静态库没啥办法。某些复杂数据类型的转换很麻烦,据说有时还有效率问题。 swig 自己找,一个叫做swig的项目,目标是制作C语言的各种平台包装。实现上看,会生成一个动态库和一个py。 优点:跨平台多。如果你的C代码不仅是python需要调用,还有其他语言(例如php),那么swig用起来很舒服。 缺点:编译时引入额外依赖,而且调用范式也是受限的。不过别担心,一般你也用不到范围以外的范式。 boost.python boost的自带库,只能用于C++。 优点:对C++的支持是极好的。 缺点:要依赖boost这么个坑爹玩意,摔。 Pyrex 我知道douban的python-libmemcached是使用这个来包装的,不过没用过,不是很清楚。

May 18, 2012 - 4 minute read - Comments

语言的效率差异2

问题 为了更深入的测试语言,我做了一个经典问题——24点。 这个问题主要是测试递归,循环效率,还有数组和树的复制性能。 为了简化问题,方便测试,我的问题是这样描述的: 有一个数组,里面有多个正整数。有一个操作数组,其中每个都是双目操作符。找出以两者构成算式,其值等于给定值的所有表达式组合。 要求不得遗漏,可以有少量重复。例如可交换算符的交换同构暂不做排重。 实际运行的时候,取+-*/和3 4 6 8,运行100次,查看时间消耗。正确的单次输出结果应当是这样的。 (((8 + 4) / 3) * 6) = 24 (6 / (3 / (8 + 4))) = 24 (((8 + 4) * 6) / 3) = 24 (((8 / 4) + 6) * 3) = 24 (((8 - 6) * 3) * 4) = 24 (((8 - 6) * 4) * 3) = 24 (((3 * 4) - 8) * 6) = 24 ((8 - (6 / 3)) * 4) = 24 (((4 + 8) / 3) * 6) = 24 (6 / (3 / (4 + 8))) = 24 (((4 + 8) * 6) / 3) = 24 (((8 / 4) + 6) * 3) = 24 (((4 * 3) - 8) * 6) = 24 (((8 - 6) * 3) * 4) = 24 (((8 - 6) * 4) * 3) = 24 ((8 - (6 / 3)) * 4) = 24 python python的解很复杂,长达31行,以下是我写的解。当然,还有更简单的版本,我可以用eval来干这个事情,代码只有24行,但是确实给人很evil的感觉。

May 14, 2012 - 2 minute read - Comments

语言的效率差异1

问题 为了测试语言的效率,做一个正则解析。 预先说好,正则解析的问题是老板正在做的一个实际问题,我把其他和效率无关的部分去了。因此我接受“用法不正确”这样的反驳理由,但是不接受“这不是典型用例”的理由。我欢迎你指正我的用法错误,或者对语言不了解导致的效率低下,但是别来和我吵吵这种例子太特殊。另外,在调整代码和评估速度的时候,顺便注意一下代码行数。我知道用汇编逐行写和优化会很优秀,但是这对实际工作基本没有帮助。 问题是这样的: 有一个文本文件,每行两个数,要求解析出来这两个数。 我用python生成了数据,代码是这样的 with open(sys.argv[1], 'w') as fo: for i in xrange(500000): fo.write('%d %dn' % (i, random.randint(0, 10000))) 正则分析速率,是个典型的CPU密集操作。对于非编译型语言而言(这里的编译是指正则表达式的解析预编译,实际上除了lisp还真没有编译型的,即使是go也是现场拿到正则进行解析的),这主要是看正则库的实现效率。很多时候,语言的效率问题并不取决于语言本身,还取决于语言的库的实现。大部分情况下我们都不可能砍掉系统的库重新来一个,那还不如换一门语言。 python 我首先贴出python语言的解答。 reline = re.compile('(d+) (d+)') def main(): with open(sys.argv[1], 'r') as fi: for line in fi: reline.match(line).groups() 这是性能 real 0m0.466s user 0m0.436s sys 0m0.012s common lisp 我找了N个正则包,实际能用的只有ppcre。有些包号称很快,实际测试下来还不如ppcre。 (require :cl-ppcre) (defun grepfile (filename) (let* ((cl-ppcre:*use-bmh-matchers* t) (cl-ppcre:*regex-char-code-limit* 256) (scanner (cl-ppcre:create-scanner "d+ d+"))) (with-open-file (in filename) (loop for line = (read-line in nil) while line do (cl-ppcre:split scanner line))))) 代码在slime里面测试(time (grepfile “data.

May 11, 2012 - 1 minute read - Comments

新闻和八卦和概率聚集

新闻和八卦有个共同点,就是会扭曲我们常规的概率体验,例如:今天摔了一架飞机。我们的结论往往是,飞机好危险。然而,世界上有很多没问题的飞机,这个你是不会从新闻和八卦里面听到的。因此,以这些东西为基础得出的结论,往往是错的。 从这点说开去,其实我们会发现很多东西都不可靠。首先说八卦。八卦之不可靠是全世界皆知的,要是有人神神秘秘和你说个事情,要么是一点不着边的瞎猜,要么就是一枪命中的内幕。可惜的是,到底是哪个,在事先完全无法分辨。香农说,信息就是减少不确定性,从这点来说,这些八卦里面的信息量是负数——本来一个事情挺明白,八卦一传,搞不好当事人都不明白是怎么回事了。 其次我们再说新闻,新闻倒是有信息量,但是新闻的不可靠也是人尽皆知。中国的文艺宣传理论就不去说了,老美也经常骂,大新闻集团只挑符合他们利益的说。不过幸好,人家新闻利益集团有好几个,岳飞打张飞之下,总算还有不少东西给披露出来。 最后,你的亲眼所见一定是真么?我在以前的一篇blog里面说过,我对问题的分析是偏颇的,因为我做不到随机取样。我周围的朋友,一定是具备某个特性/符合某个范式的。例如熟悉电脑,受良好教育的城市青年,中国人,这些总是没办法的事情。如果以此为样本来分析相关问题,相信一定会南辕北辙。例如你以我的gtalk和twitter好友来分析python和emacs用户的比例,那一定是高的异乎寻常。这是当然的,我本来就是以python和emacs作为自己的标签,无论是朋友也好,会fo我的人也好,多半是此道同好。以此类推,若是你不仔细分析,即使以亲眼所见,也未必能得到结论。

May 10, 2012 - 1 minute read - Comments

全部和谐音程表(泛音表)

>>> for i in [(i, j, 12 * math.log(float(j)/i, 2)) for i, j in itertools.permutations([1,2,3,4,5,6], 2) if i < j]: print i ... (1, 2, 12.0) (1, 3, 19.019550008653876) (1, 4, 24.0) (1, 5, 27.863137138648348) (1, 6, 31.019550008653873) (2, 3, 7.019550008653875) (2, 4, 12.0) (2, 5, 15.863137138648348) (2, 6, 19.019550008653876) (3, 4, 4.980449991346124) (3, 5, 8.843587129994475) (3, 6, 12.0) (4, 5, 3.863137138648348) (4, 6, 7.019550008653875) (5, 6, 3.1564128700055254)

May 9, 2012 - 1 minute read - Comments

论医

医生的道德标准 要摆正医患关系,首先就必须将医生的道德标准降下来,从“白求恩精神”,降低到一般人标准。 为什么?有一则故事,叫做“子贡赎人”,挺有名的,大家可以自查。跳过故事本身,我直接说其中的观点: 如果将道德标准提高到没有人能够接受的地步,就不会有人照做了。 类似,大家都是人,为什么让别人去遵循“白求恩精神”,或者其他变态的精神,而让自己能够得利呢?拥有这种精神的毕竟是少数。以这个为标准要求多数人的结果,就是没有人能够成为医生。 医生的标准,只要能够诚实的提供服务就好了。动辄就拿奉献说事,实则是用大帽子压人,和文革无异。 当然,现今最主要的问题,是以白求恩精神要求医生的同时,连诚实服务都贯彻不下去。这种动辄涉及人命的事情上不公开透明是会出人命的。只要有一小撮是贯彻不下去的,那病人就会连剩下的医生一并怀疑,然后杀医生的戏码就会层出不穷。 貌似要立法阻止杀医什么的,其实我说,这也就是对纯粹的医闹管用,真的爆上新闻的,多半不会是医闹。道理很简单,医闹的目的是拿钱,耍赖撒泼软语哀求的目的都是拿钱而不是报仇。就算他再和医生横眉竖眼,也不会往死里下手——真的往死里整的,多半是豁出一条命的家伙。人不畏死,奈何以死惧之。解决这个问题的最好途径不是阻拦,而是有个心平气和能让他解决问题的途径。 不实施抢救的道德标准 我认为,以下两种情况下,不实施抢救不应当受到责难。 病人死亡。 病人不可避免的向死亡发展,其中会为本人或家属带来极大痛苦。 医疗会耗尽社会的剩余资源 我觉得这是不言自明的。人类社会从原始社会仅够自己温饱,发展到目前的状态。实则目前一个人的工作供养数人足矣。或者换个表达方式,全球所有人所需的食物/衣物/住房等资源,并不需要所有的人类进行生产。若非如此,贫困救助体系和养老体系都没有发展的前提。多余的人产生的物资,即是社会的剩余资源。 社会目前的剩余资源,必然会有一个出口。一方面,第三产业,娱乐业,都是基于剩余资源的。也可以看作,从事生产的人为他们提供食粮,而他们为从事生产的人带来娱乐。而另一方面,科技发展,医疗和医疗技术发展,也是基于这些资源的。 随着科技发展,人类的剩余资源冗余度会越来越大。人类需要的必需品只需要更少的人进行生产,更多的人会投身非直接产生必需品的行业。在这种情况下,我更希望他们参与医疗和科技发展。并不是说娱乐业不好,或者不需要。只是科技和医疗能够带给人更好的生活——我是这么相信的。

May 7, 2012 - 1 minute read - Comments

升调降调的规则

为什么C加一个升调变成G? 这个要从大调式讲起。 大调式是以大三度为基础构建的调式,主音到中音为大三度,中音到属音为小三度,两者构成大三和弦。主音到属音为纯五度,属音到主音为纯四度,大调式的三个基础音之间,都是和谐音程关系。以C大调而言,就是do mi so。 好吧,C大调之所以叫做C大调,是因为以中音C为do。那么G大调呢?以中音G为do?对的,问题是,C大调的所有音,是否能够不做任何变化的构成G大调的音? 这是不可能的,C大调的音不做变化唯一能够构成的只有a小调。G大调一定需要对C大调的音做升降的。 为什么?因为C大调的音程关系是全全半全全全半,这个在小学就教了。通过这个,你可以数出上面说的三个纯音关系。当我们位移到G=do的时候,你会发现,不做变化的话,音程就变成了全全半全全半全,这就糟了。所以,需要对C调的fa(即F)升半个音,来回复大调调式。 常识上我们知道,12平均率是对称关系,所以上述过程可以运用数学归纳法作用于整个中音音阶。即,每个大调可以通过升该调中的fa半个音,变成另一个大调。后者刚刚好比前者高一个纯五度。 降调关系亦然,可以类比。 小调关系亦然,不过小调使用全半全全半全全作为结构,主音到中音为小三度,中音到属音为大三度,两者构成小三和弦。主音到属音为纯五度,属音到主音为纯四度,小调式的三个基础音之间,也都是和谐音程关系。 稍微数一下就知道,小调式上的所有音,可以构成比自己高小三度的大调,两者称为关系大调和关系小调。 虽然音是一样的,然而主音中音属音的位置完全不同,因此调式色彩完全不同。