Monthly Archives: February 2010

Python Notes: Reference and Dynamic Type

内容较水,让大牛们见笑了。Python语言采用所谓的“动态类型”,顺序执行如下三条语句是完全合法的:

>>> loli = 5
>>> loli = 3.142
>>> loli = "hello"

这种类型系统与静态类型的语言如C和Java等有很大不同。我认为比较容易理解的表述方式是:数据的类型与对象有关,与名字无关。变量名只是一个名字而已,它没有类型,可以理解成一个C语言里的(void*),类型信息是存储在变量指向的对象中。这个对象是内存中的一块区域,里面包含具体的值、这块对象的类型、引用计数等等信息。对于上面三条语句,可以理解为有一个叫做loli的变量,一开始指向一个整数对象,然后指向一个浮点数对象,最后指向一个字符串对象。

如前所述,Python变量表示的是对对象的“引用”,对象分为可变和不可变两种(这一点和Java类似),数值、字符串、tuple是不可变的,其余的是可变的。比如下面两条语句

>>> loli = 3
>>> roba = loli

首先loli指向一个整型对象(3),然后roba也指向同一个对象。Python有个id()函数,可以查看对象的内存地址,可以发现id(loli)和id(roba)是相同的。如果继续执行

>>> roba = roba + 1

则id(roba)可以发现指向的不同的位置。此时roba指向4,而loli仍指向3。因为整型对象是不可变的,所以roba必须指向一个新申请的叫做4的对象,而不能改变原来指向的那个3。与此相反,如果

>>> loli = [3]
>>> roba = loli
>>> roba[0] = roba[0] + 1
>>> loli
[4]
>>> roba
[4]

这里对象是可变的list,所以修改roba[0]的时候,loli指向的对象值也变了,因为它们始终指向同一个对象。如果我们想让他们指向不同的对象,则需调用copy.copy()进行复制。(关于copy和deepcopy的区别就以后再说吧)

在传递函数参数的时候也要注意这个问题,如果传的是不可变类型,在函数内部的修改不会影响到外面,如果是可变类型则有影响。

UyHiP Jan 2010 Part 1

原题见此:http://brand.site.co.il/riddles/201001q.html

题目大意是这样,要把一个1到n的数组成的序列排成升序,排序的方法是:每次对于某个不在正确位置的数k,如果它的正确位置在现在位置的左侧,则可以把它插入到正确的位置。每次移动哪个数是无限制的。比如序列(3 1 2)可以经过两次操作排序(3 1 2)->(1 3 2)->(1 2 3)。现要求证明这个方法确实能完成排序。并求出在何种初始序列下,采用何种移动策略,使得完成排序所花的步骤最多。

几天前看到这个题目,想了一下觉得挺有意思,我的方法和标准解答很接近,不过不如人家表述得优美。

第一步证明比较简单:对于任意序列,如果某个数在正确的位置上,则记为1,否则记为0,这样得到了一个n位的二进制数。如果我们把左边当作高位的话,会发现每一次操作都会让这个数增加(因为每次都是把某一个0变成1,其余的变化都在比这一位更低的地方)。而最终升序序列对应的正是一串1,所以这个数是一定能达到的。

进一步的观察会发现,最右边那一位是不可能被“主动”影响到的,所以我们忽略最右一位,上面的证明仍然成立,并且说明步数的上界是2^(n-1)-1。实际上这个上界是可以达到的,也就是说对应的二进制序列值从(000…0)每次加1加上去,也就是说,每次选择最右边的0变成1,然后把其右边的1们都变成0,对应到序列操作就是每次把最右边的那个数插到合适的位置。但这里的困难是如何构造初始序列使得此过程能进行下去,这里并不显然,我是直接写了程序找的规律,而官方解答则比较巧妙:因为最终的(111…1)对应的序列已经确定,每次插入的位置也都确定,所以可以将这个过程倒过来考虑,倒推出初始序列。例如n=3时,倒过来的二进制序列是11->10->01->00,每步插入的位置分别是左数第二位、左数第一位、左数第二位,对应的原始序列倒回去是(123)->(132)->(321)->(312)。最终可得,满足要求的初始序列是(n 1 2 3 …(n-1)),操作过程是每次选择最右边的数插入正确位置,共花2^(n-1)-1步。

实际上写程序的话也很容易就能看出结果是(n 1 2 3 … (n-1)),然后可以归纳法证明步数是2^(n-1)-1。当n=2时显然只花1步。对于更大的n,我们首先把(n 1 2 3 … (n-1))变成(n 2 3 … (n-1) 1),然后把1归位得到(1 n 2 3 … (n-1)),再最终变成(1 2 3 … (n-1) n)。可以发现这里第1步和第3步实际上是很类似的,都是把后(n-2)个数向前移到一位到正确位置,同时把前面那个数“挤”到最后去,而这步操作正是当n-1时的原问题,根据归纳法的假设,这两步都分别要花2^(n-2)-1步。所以就有2^(n-1)-1 = (2^(n-2) – 1) + 1 + (2^(n-2) – 1)

[转载]唯有进步值得信仰——《十月围城》评论

RoBa注:抱歉又是转载文,嘿嘿。早就想关于这个电影写点啥,看完这一篇以后发现不用写了,人家比我的文笔优美深刻百倍。

原文地址:http://www.douban.com/review/2870206/

现在是2009年,华丽丽的建国六十年,荧屏与荧幕上都充满了DANG单方面的回忆与歌颂,按照我老爹的总结就是:全面展示我们如何弄倒国民党。
今年秋天,我陪朋友一起看赫赫有名的献礼电视剧《人间正道是沧桑》。她从小到大是个好孩子,学习好,思想好,行为积极上进,党员,国家机关从业人员,不看毒草,不听靡靡之音,更不会有丝毫反动思想。
我们一起看到影片中的瞿恩就义,孙淳叔叔一边喊着口号一边倒下。我朋友哄笑起来嗤之以鼻:真假,太假了,你说是不是?!我说不是的,虽然你不 相信,但是当时这位瞿恩的原型叫做瞿秋白,他的确是唱着国际歌,喊着共产主义万岁死掉的。DANG今天很操蛋,并不代表所有信仰这种主义的人都很操蛋。
从什么时候开始,连好孩子们也开始什么都不相信。
不相信有人会为了主义而慷慨赴死;
不相信有人会大公无私舍身取义;
不相信有人立志为生民请命为万世开太平。
执政者将自身的理想与主义抬得越高,我们所感受到现实的就越荒谬,实用主义君临时代,娱乐精神空前风行。
文革时,家乡有青年在街头打闹嬉戏,高喊着:你们敢打革命爷,你们敢打革命姐。至此,“革命”再也不是一个神圣的词语,它完全沦为一个笑话。
我们还没开始建构,就已经开心地拥抱解构,我们还没开始做梦,就已经嘲笑理想,我们还没学会相信,就开始提防欺骗。最终我们打倒了神圣,最终 我们热情地拥抱庸俗,最终未能建筑起自身核心价值的社会,不可避免地以大量物质享受来弥补空虚与维持稳定,我们被忽悠太久,产生最大恶果不是我们笨了,而 是我们奸诈了,我们谁也不相信包括自己。

一直以来,我不喜欢革命,我恐惧它巨大的破坏力,我厌恶它的血腥后果,我讨厌它可以随时成为攻击异己的工具,我更憎恶它随时变化的面孔,吞噬自身儿女时比吞噬敌人更加凶狠。
一直以来,我不喜欢主义,尤其那些认为自身的道路才是人类终结目的的主义,当他们被压迫的时候他们表演得如此纯洁理想,当他们成为主流,他们所表现出的排外性与空前专制往往比前任统治者更甚。
所以,我看《十月围城》不仅仅是抱着八卦的心态,更是因为被它片花中孙中山的一段独白给触到。
“欲求文明之幸福,必经文明之痛苦,而这痛苦,就叫做革命。”
应该说这是我见过的关于革命最好的解读,它让我在某种程度上,终于和“革命”这个词握手言和。
我可以厌恶革命,可以反对主义,但是对于革命者,对于为主义而赴死的人,甚至被主义吞噬的人们,我心怀尊重。
我今日之所感所知所思所享,无不来自于百年来这些努力去实现臆想中“中国明天”的人们。他们或伟大或浅薄或愚蠢或无私或卑劣或聪明或成功或失败或一代领袖或千古罪人,我可以评判他们,同时心怀某种敬畏与感激。
我们已经无法体会到当初那些热情,因为我们失去了那个感知热情的时代环境。
革命、民主、自由、主义、共和、共产、大同……都是曾经被用以呼唤理性、现代性、个性、人性与新的时代,同时也这些词也被用以唤起多数人的暴力,用以巩固权力,用以践踏权利与扭曲人性、创造同质化。
就在不远的年代里,人们感知国家的衰败与无望,人们有着各自臆想的正义与理想,人们为了捍卫思想而厮杀,当思想成为组织,人们卷入其中,最终组织的荣衰代替了思想的成败,最终组织的目的代替了过程的正义,组织代替了理想,成为正义本身。
《十月围城》中,革命者臆想着只要保卫组织,保卫领袖就等于保卫正义,于是可以欺诈义士作为诱饵引开杀手,清廷官员臆想着只要保卫朝廷统治与社会的安稳就等于保卫正义,于是可以大开杀戒血流成河。
相同的是,他们都认为自身是正义。
影片的主角并不是这“正义”的双方,而是那些为了这场理想之争、,明天之争而付出生命的小人物,他们倒在政党、革命家、政治家、军阀、党魁、知识分子、大商人们叱咤风云的舞台下,他们是渺小的配角,他们所求的无非是俗世幸福,而时代给了他们一个小时,去成就历史。
我总是想起茨威格在《人类群星闪耀时》中关于马赛曲的故事,马赛曲的作者一生除了写出这首歌之外乏善可陈。仿佛时代在两个小时的时间中选择了那个普通的人物,借他的手写出来这伟大的旋律。
或许,在中国从来都没有出现过一个伟大的组织;或许,在中国社会的方向抉择中,我们总是抽到下下签;或许,我们任何一个机会都导向失败;或许。我们总是一遍遍重复着历史的错误与悲剧;或许,我们至今还不知自己来自何方,去向何处。
在衰败、痛苦与危机重重的年代里,青年们“闭上眼就能看到中国的明天”,这种深刻的幸福与乐观,在今天的我们从未体会过。

去年回家时在飞机上读顾准,在生命的倒数第二年,他在信件中和自己的弟弟探讨“终极目的”这一命题——
“从来都没有什么终极目的,有的,只是社会的进步。”
从来都没有任何一个人,一个组织,一种主义能够解决所有的问题,也没有任何一个人,一个组织,一种主义值得你去放弃自身的判断力。也没有任何一个人,一个组织,一种主义能够替代进步本身。
所以,值得信仰的是进步本身,而不是任何标榜“进步”的组织。
今天的主流,无非也是昨日的异端,今天的异端,也许就是明日的主流。
归根结底,时代一定会以自己的方式向前进步,任何人“万万岁”的说梦,任何组织“代表人民”的意淫,任何主义“永远先进”的自欺欺人,最终都会落败于时代的力量,这或许是我们仅存的乐观与希望所在。

前段时间,我还很得瑟地数落过香港影业,演员凋敝,市场缩水,一线花旦均被大陆包揽,香港导演只能来大陆找投资、找演员、找市场。
现在看来,对比刚刚上映的《三枪》,我觉得张艺谋可以找块豆腐撞撞。相比较大陆导演在“大片”中每况愈下的表现,尽管资金缺、市场缺、演员缺,香港电影依旧完胜。内地的投资,内地的演员,却进一步成就了香港这座城市,香港电影人不可撼动的文化地标位置。、
我虽然有点难过,但是不得不服,也不得不承认——
我一直希望中国影坛出现《十月围城》这样的片子。
它触及了我一直很感兴趣的时代与人物,同时它很好看。
在中国这么漫长的历史岁月里,我们值得骄傲的不仅仅是那些老祖宗的家底,更是自晚清以来为中国明天而不断奋斗的人们,尽管每一个人心中都有自己臆想的正义与未来,尽管并非每个人都被时代所青睐,但是他们却代表着进步的可能性。
小时候不喜欢读近代史,憋屈而令人心烦,古代史多好,我们多牛x,我们是世界第一。
现在能慢慢体会到,读懂它,才会真正理解今日之中国从何而来,才能有资格去思索今日之中国向何而去。
可惜,对于那段历史,我们缺乏空间去探求,媒体议题缺失,社会平台狭小,它沉入戏说、样板戏、娱乐的海洋深处。
找不到一个社会的普世价值不可怕,可怕连寻找价值的人都没有,可怕的是我们连探讨它的空间都没有,更可怕的是我们没有探讨它的兴趣。
革命成功了,民主不一定会来。
一个党成功了,民主不一定会来。
一个主义成功了,民主不一定会来。
千千万万人死去,民主不一定会来。
甚至我们知道,民主只是个孩子,它能被不同主义,不同党派抱来抱去,被打扮成不同摸样。
但是如果我们失去了对民主的兴趣,我们失去了对进步的相信,我们无法正视在追寻民主与进步中的鲜血、失误、愚蠢、卑劣与其他种种最坏的事情,我们永远不值得去享受它的光明与幸福。
玛丽莲梦露说的好,如果你无法忍受我最坏的一面,你也无法得到我最好的一面。
古往今来,所有让人奉献才华、勇气、激情乃至生命的美好事物皆如此。

在看完《人间正道是沧桑》之后,我去查了查瞿秋白的故事,在他生命的最后关头,他写了最后的文章《多余的话》,他说如果他还有生存的机会,他 宁愿做一个普通的学者与知识分子。那一瞬间,相对于我DANG那些最终走上历史前台的男一号们,这位最终死在历史中的男配角显得更为亲近。他不再是曾经的 党魁,他也无非是时代选中的一个普通人。
所以,容我最后再推荐一次《十月围城》,一部关于时代中普通人抉择的影片——
这是一部很有诚意的片子。
这部片子节奏紧凑且台词功力非常出色。
这部片子终于实现了“一个好看的故事”和“一个深刻的故事”的融合。
这部片子中不少演员贡献了迄今为止最优秀的表演,尤其是王学圻与甄子丹。
这部片子以历史洪流中小人物的命运最终书写了一个宏伟的命题。
这部片子内涵极其丰富,导致于我在观影途中,脑海中不断浮现各式各样的人物与姓名。
这部片子没有单方面歌颂革命,也不是简单的正邪之战或者好坏之争。
这部片子没有我写的这么沉重,相反它很商业,它非常好看。
……
这是我在豆瓣的第一篇影评,也是我打出的第一个评级。
并非我看的其他影片不足以打动我,而是从这部影片开始,我看到了华语电影的某种可能性,我看到了“民主、革命、主义、未来……”这些词汇重新 以严肃姿态回归主流议题的可能性,即使有人是为了去看偶像,有人是为了去看笑话,有人是为了去看武打,只要有人去看,我还是看到了思考的可能性,看到在这 个娱乐时代中,我们愿意再次拥抱沉重的可能性。
鉴于以上珍贵的可能性,我给它五颗星。
值得迷信的不是陈可辛,也不是香港电影,而是终究会到来的进步,更是精神不灭的薪尽火传。

[转载]阮一峰:我为什么喜欢编程

原文链接:

http://www.ruanyifeng.com/blog/2009/10/why_i_love_programming.html

这个周末,我在家核对More Joel on Software的最后定稿。

此书已经在申请书号了,一拿到书号,就可以印刷和销售了。所以,不出意外的话,年底之前就能上架。

在复核的过程中,我又读到了书中让我最有共鸣的一段话:Joel谈为什么公正对程序员很重要。

我不知道别人的情况,我自己喜欢编程,很大的原因就是觉得程序的世界更公平公正,谁对谁错,只要运行一下代码就知道了。这同现实世界截然不同,在现实的世界中,只要你有权有钱,善于搞人际关系和钻制度的空子,你就能把错的说成对的,把黑的说成白的。老老实实、埋头苦干的人,眼睁睁看着乾坤颠倒、小人得志,而只能束手无策、一筹莫展。

我们生活的这个国家,是一个禁止自由思考、党决定一切的国家。在这里,如果你想不撒谎、不干坏事、并且被公正地对待,那么可能你只能去编程了。

==================

不搞政治

作者:Joel Spolsky

译者:阮一峰

老实说,只要有两个以上的人待在一起,就会有政治。这很自然。我说“不搞政治”的真正的意思是“不搞恶性的政治”。程序员早就练出了对公正有非常良好的判断力。代码要么能运行,要么不能。坐在那里争论代码是否有问题,这是毫无意义的,因为你可以运行代码,答案自然就有了。代码的世界是非常公正的,也是非常严格有序的。许许多多的人选择编程,首要的原因就是,他们宁愿将自己的时间花在一个公平有序的地方,一个严格的能者上庸者下的地方,一个只要你是对的就能赢得任何争论的地方。

如果你要吸引程序员,你就必须去创造出这样一个环境。当一个程序员抱怨“人际关系复杂”时,他们的意思明白无误,就是指任何个人因素超过技术因素的环境。程序员在完成手头任务时,不被允许使用最合适的编程语言,而是被命令只能使用另一种特定的语言,原因仅仅是老板喜欢这种语言;没有什么比这更让人气愤了。晋升的原因不是成果,而是人际关系;没有什么比这更让人抓狂的了。程序员被迫去做技术上落后的东西,仅仅因为上级或者得到上级支持的人坚持这样;没有什么比这更让人发火了。

没有什么比因为技术原因赢得一场由于政治原因本来要输掉的争论更让人心满意足了。当我在微软公司刚开始工作的时候,有一个正在开发中的大型项目走入了歧途,项目的代号是MacroMan,目标是创造一种图形化的宏语言。真正的程序员遇到这种语言会很有挫折感,因为图形的特性让你真地没有办法完成循环和条件判断功能。此外,对于那些非程序员的用户,这种语言也不会有很大作用,因为我觉得那些用户不会习惯算法思维,没有办法很快地理解MacroMan。当我说出对MacroMan的负面评价时,我的老板告诉我:“如果火车要出轨,没有东西能够阻挡。算了吧。”但是,我还是不放弃,一再地不断地争论。那时我刚走出学校,在微软公司中差不多跟谁都没有利害关系,所以,渐渐地,人们开始倾听我的核心观点,MacroMan后来终止开发了。我是谁并不重要,重要的是我是对的。非政治性的组织就应该这样,这种组织才会让程序员感到高兴。

总的来说,关注你的组织的社交动态变化,对创造一个健康的、令人愉悦的工作环境是很关键的,这样可以留住程序员和吸引程序员。

(完)

AT&T汇编与gcc内联汇编

在*nix阵营中,AT&T形式的汇编是更普遍的,例如gas还有gcc的内联汇编都是这种,它与我们在汇编课上熟悉Intel形式的汇编(比如,MASM支持的那些)的不同点主要在以下几方面:

1. 操作数的顺序是反的。比如movl %eax, %ebx的意思是把eax的值赋值给ebx

2. 寄存器名字前面要加%,立即操作数前面要加$。比如movl $0x1984, %eax

3. 指令加后缀b (8bit), w (16bit), l (32bit)指示操作数大小,这一条并不强制,因为汇编器基本可以根据操作数自行推断,但建议加上。比如movb %al, %bl

4. 间接寻址,用圆括号不用方括号,并且有一个很恶心的格式 imm32(base,index,scale)。例如,-4(%ebx,%eax,8)等价于Intel的[ebx+eax*8-4]

下面说GCC的内联汇编,乍一看上去很简单,只要加个asm(或者__asm__)就可以了,例如 asm(“nop”); 但是麻烦的在于让其和上下文的C代码匹配上。内联汇编的格式如下:

asm ( assembler template
    : output operands               (optional)
    : input operands                (optional)
    : list of clobbered registers   (optional)
);

后面的三个可选项就是负责指定相应的“接口”。看这样一段简单的代码,作用是把局部变量a的值赋值给b:

{
    int a=10, b;
    asm ("movl %1, %%eax; movl %%eax, %0;"
        :"=r"(b)  /* output */
        :"r"(a)       /* input */
        :"%eax"); /* clobbered register */
}

这里我们直接写类似”movl a, %eax; movl %eax, b”是不行的,因为汇编代码里不知道a和b是啥东西,所以需要在output和input这两部分指定“约束”。“约束”的格式是一个字符串后面跟一个括号里的C表达式,比如”r”(a)表示a这个变量必须放在某个寄存器中。字符串里可以包含的字符及意义:

a   eax
b   ebx
c   ecx
d   edx
S   esi
D   edi
q   eax, ebx, ecx, edx
r   eax, ebx, ecx, edx, esi, edi
m   内存
i   立即数
数字0/1...   表示引用之前出现过的

可以有多个约束,用逗号隔开。在output部分需要前面加一个等号。上面代码里%0, %1这些就是和下面output, input两部分指明的约束是对应的,最先出现的”=r”(b)对应%0,然后出现的”r”(a)对应%1。有时候我们需要在input里指明output中已经出现过的某个约束,这时候就应该用”0″, “1”这种了。另外,注意现在表示寄存器时要加两个百分号(%%eax)了。

最后的clobbered register是指明这段代码里可能会用到的寄存器,意思是告诉gcc,这些寄存器里的值可能已经让我修改了,你不能假定它们还有效。出现在input和output里的寄存器会自动被认为是clobbered的,无须再写出。

这个东西实在是很乱很难说清楚,上面说的也只是最常用的一部分内容。最后用几段典型代码展示一下:

下面这段等价于var=var+1,注意input部分的”0″的使用

asm ("incl %0" :"=a"(var):"0"(var));

下面这段是把count个字节从src拷贝到dst

asm ("cldn
repn
movsb"
: /* no output */
:"S"(src), "D"(dst), "c"(count));

最后来个货真价实的,传说中的Linux内核代码中的memcpy

static inline void * __memcpy(void * to, const void * from, size_t n)
{
    int d0, d1, d2;
    __asm__ __volatile__(
      "rep ; movslnt"
      "testb $2,%b4nt"
      "je 1fnt"
      "movswn"
      "1:ttestb $1,%b4nt"
      "je 2fnt"
      "movsbn"
      "2:"
      : "=&c" (d0), "=&D" (d1), "=&S" (d2)
      :"0" (n/4), "q" (n),"1" ((long) to),"2" ((long) from)
      : "memory");
    return (to);
}

简单来说上面那段代码的意思是一开始用movsl四字节复制,等发现快到头了,再根据剩余的情况用movsw和movsb。细节不解释了,仔细分析一下还是很好玩的 :)