编程随想

前一个帖子 ，俺介绍了胡先帝的悼念活动3天内席卷天朝各地。到了4月18日这天，帝都的大学生们已经不满足于纯粹的悼念。他们想借助这次声势浩大的悼念，提出进一步的政治诉求。所以，18日这天出现了（六.四.运.动中）第一次 政治性 的抗议活动——人民大会堂静坐请愿。 ★”北大七条”的出台 　　话说17日晚间，有几位北大的学生制作了一块10米长2米宽的横幅，上书”中国魂——部分北大校友暨师生敬挽”。然后拿着这个长条幅在校园内游行。到了深夜时分，参与校内游行的学生越聚越多。大伙儿就提议，干脆到广场上去。于是，一干人等（据说有上千人）就从北大校园一路走到天.安.门（到达广场的时候已是次日凌晨4点，精神可嘉）。 　　那会儿还是大清早，广场上除了学生，大概也没多少市民。于是这拨学生就开始考虑接下来该咋办？估计很多学生对2年多以前的 八.六.学.潮 还是记忆犹新。八.六.学.潮没有持久，有很多原因（俺的分析在” 这里 “），其中之一就是：缺乏明确的，统一的政治诉求。所以，纪念碑周围的学生们就开始讨论他们的政治诉求。最终商定了七条要求——也就是后来闻名海内外的”北大七条”。 ★”北大七条”的两个版本 　　为了写这个系列，俺特地参考了不少相关的资料（书籍、网站），以求尽量真实。关于”北大七条”，俺发现有两个版本，流传较广。 ◇版本1 一，公正评价胡耀邦的政绩，肯定民主自由的宽松的政治环境； 二，彻底否定”清除精神污染”与”反自由化”运动，并为这次运动中蒙受不白之冤的人平反； 三，要求党和国家领导人及其子女向全国人民公布其财产状况； 四，允许民办报纸，开放报禁，制定新闻法； 五，增加教育经费，提高知识分子的待遇； 六，取消北京人大常委会违反宪法而制定的限制游行的”十条”； 七，对此次活动作出公开的报道，见诸党政机关报。 ◇版本2 一，重新评价胡耀邦同志的是非功过，肯定其民主、自由、宽松、和谐的观点； 二，彻底否定清除精神污染和反对资产阶级自由化，对蒙受不白之冤的知识分子给予平反； 三，国家领导人及其家属年薪及一切形式的收入向人民公开，反对贪官污吏； 四，允许民间办报，解除报禁，实行言论自由； 五，增加教育经费，提高知识分子待遇； 六，取销北京市政府制定的开于游行示威的”十条”规定； 七，要求政府领导人就政府失误向全国人民作出公开检讨，并通过民主形式对部份领导实行改选。 ◇哪个版本是真的？ 　　这两个版本的头6条大同小异。但是 第7条完全不同 。那么，到底哪一个版本是真实的捏？ 　　版本1的出处比较丰富，有如下几个： 香港记者协会出版的《 人民不会忘记 》（相关页面在” 这里 “） 当事人之一 张伯笠 的个人网站（相关页面在” 这里 “） 当事人之一 李进进的文集 （相关页面在” 这里 “） 《”六 • 四”事件民间白皮书》第30页（书中的备注称：提及的”北大七条”引自李进进文集） 　　版本2的出处比较单一，主要来自于《 天.安.门文件 》（又名《中国”六 • 四”真相》）。 　　另外，维基百科的 “六四事件”词条 不知何故也采用此版本。不过维基百科还算客观，在该词条的备注中，注明了”北大七条”存在多种版本，维基引用的是《中国”六 • 四”真相》的版本。 　　从资料出处来看：版本1有多个比较可信的来源。比如：张伯笠是那天参与讨论北大七条的学生之一；李进进是当天向人大常委会递交请愿书的学生代表之一。 　　从当时形势来看：18日那天，大学生刚开始准备政治请愿，学生和政府之间的矛盾还没有激化，不太可能提出像”版本2″这么激进的政治要求。 　　综上所述，俺倾向于认为： 版本1是真实的 。 ★《天.安.门文件》为何失实？ 　　至于《天.安.门文件》一书，为啥会出现如此严重的失实，俺顺便来聊一下： 　　在 前一个帖子 ，俺大致介绍过这本书的来历。此书很大一部分内容，是当时的党国爪牙（比如国安人员）发给裆中央的报告。照理说，”北大七条”是学生提出的最主要的政治诉求，当时广场上肯定有便衣人员把这一幕给详细记录下来。这帮爪牙连某某大学在几月几日几点几分贴出几张大字报，都数得一清二楚。如此敬业的爪牙，没道理把”北大七条”这么重要的东西给搞错了。 　　所以，比较大的可能性是：爪牙们提交报告之后，在到达裆中央之前，中途被人篡改了。那么，会是谁干的捏？ 　　为了说清楚这个问题，俺先来聊一下当时朝廷高层的情况。 本系列 的头几个帖子，俺已经花了很多口水，介绍当时朝廷中的两大派系——改革派和保守派。这两派的关系，可谓水火不容。想当初老胡就是因为八.六.学.潮没处理好而下台。老胡被废之后，保守派本来想趁机拿下总书记的宝座，可惜老邓又扶了赵.紫.阳，让保守派美梦落空。如今，大学生借着悼念老胡，掀起新一轮学.潮。对保守派而言，这是个天赐良机。如果八.九.学.潮老赵没处理好，也很可能下台并导致改革派元气大伤，那保守派就可以从中得利。 　　而当时帝都的市长是陈希同，市委书记是李锡铭。此2人恰好都属保守派，据说他俩跟李鹏的关系还挺密切。而李鹏这个人，一直不满足于总理这个位置，老想把赵.紫.阳挤掉，自己当总书记。所以，当这份报告送到北京市政府手中的时候，很可能就被篡改了。 　　篡改者的目的，就是故意夸大学生的要求，让高层（主要是八元老）觉得学生很激进。大伙儿想想看，”北大七条”的最后一条被改为： 要求政府领导人就政府失误向全国人民作出公开检讨，并通过民主形式对部份领导实行改选 。这样一种说法，无疑会激怒八元老，尤其会激怒老邓。后续的帖子，俺还会提到保守派的另外一些伎俩——通过这些伎俩，保守派逐步地让老邓觉得，这帮大学生已经不是”人民内部矛盾”，而是”敌我矛盾”。 ★人民大会堂的请愿 　　分析完”北大七条”的真伪，接下来稍微介绍一下那天的请愿过程。 　　话说那天拟定出7条政治诉求后，还没到上班时间。于是学生们就到人民大会堂门前等着（人民大会堂就在天.安.门.广.场边上）。等到里面上班了，就选出4个学生代表（ 王丹 、李进进、 郭海峰 、张志勇）进大会堂提交请愿书。 　　当时和学生代表交涉的，是人大信访办的官员。这些官员根本就没把这些学生放在眼里，拿到请愿书之后，只是简单说了句”要研究一下”，就想把学生们打发走。大会堂门口的这些学生，当然晓得政府官员在敷衍了事。但是他们都比较犟，一定要全国人大派出正式代表，接受学生的请愿书。而全国人大的官员，在上级没有指示之前，又不敢轻举妄动。于是双方就这么耗着——从上午耗到下午，再从下午耗到晚上。很多学生是17日深夜从北大徒步走到广场，然后又在大会堂门口不吃不喝，静坐到18日晚上，实在是毅力惊人。 （香港《亚洲新闻周刊》89年5月那期的封面，地上铺的是”中国魂”横幅，横幅上放的白纸写着”北大七条”，拿话筒的是李进进） 　　随着时间的流逝，大会堂门口的学生越来越多，各个大学的人马都加入进来——很多学生本来要到纪念碑搞悼念活动的。搞完悼念，也顺便加入到静坐的队伍中。据李进进回忆，他当时已经做好连续静坐几天几夜的准备，还叫人回北大拿些棉衣棉被。 　　到了晚上7点多，随着静坐队伍迅速扩大，官方终于做出让步——人大常委会派出几个知名的代表（宋世雄、刘延东、等）到大会堂外面跟学生见面，并当面接受了请愿书。顺便说一下：刘延东当时任全国青联主席，如今已高升政治局委员；至于宋世雄，央视体育频道的名嘴，90前的网友应该很熟悉。 　　既然人大已经派代表接受了学生的请愿，一部分现场静坐的学生认为目的已经达到，纷纷散去；但还有一部分学生不满意——毕竟刘延东当时只是个小官，宋世雄虽然名气大，也还是个小官。这部分学生认为，政府应该派出级别更高的官员出来跟学生见面并接受请愿书。于是，这群不甘心的学生就高举着”中国魂”的大横幅，一路奔向中南海（朝廷重量级的官员都住在那儿）。之后，就发生了六四运动中，第一起流血事件——新华门事件。 　　下一个帖子，俺介绍一下新华门事件的经过。 回到本系列的目录 版权声明 本博客所有的原创文章，作者皆保留版权。转载必须包含本声明，保持本文完整，并以超链接形式注明作者” 编程随想 “和本文原始地址。 学习翻墙 发信给 help_gfw@yahoo.com 可获取翻墙教程 (用国外邮箱以免被墙) 如有其它问题, 用 program.think@gmail.com 联系俺

★引子 　　前天，俺在《 俺的招聘经验[4]：通过笔试答题能看出啥？ 》一文，以”求质数”作为例子，介绍了一些考察应聘者的经验。由于本文没有政治敏感内容，顺便就转贴到俺在CSDN的镜像博客。 　　昨天，某个CSDN网友在留言中写道： 老实说,这个程序并不好写,除非你背过这段代码 如果只在纸上让别人写程序,很多人都会出错 但是如果给一台电脑,大多数人都会把这个程序调试正确 出这个题目没啥意义 只能让别人觉得你出题水平低 　　首先，这位网友看帖可能不太仔细。俺在文中已经专门强调过了，评判笔试答题， “思路和想法”远远比”对错”更重要 ，而他/她依然纠结于对错；其次，这位网友居然觉得这道题目没啥意义，这让俺情何以堪啊？！看来，有相当一部分网友完全没有领略到此中之奥妙啊！ 　　算了，俺今天就豁出去了，给大伙儿抖一抖这道题目的包袱。当然，抖包袱的后果就是：从今天开始，就得把”求质数”这道题从俺公司的笔试题中去掉，然后换上另外一道全然不同的。这么好的一道题要拿掉，真是于心不忍啊 :-( ★题目 　　好，言归正传。下面俺就由浅入深，从各种角度来剖析这道题目的奥妙。 　　为了避免被人指责为”玩文字游戏”（有些同学自己审题不细，却抱怨出题的人玩文字游戏），在介绍各种境界之前，再明确一下题意。 　　 前一个帖子 已经介绍过，求质数可以有如下2种玩法。 ◇需求1 请实现一个函数，对于给定的整型参数 N，该函数能够把自然数中，小于 N 的质数，从小到大打印出来。 比如，当 N = 10，则打印出 2 3 5 7 ◇需求2 请实现一个函数，对于给定的整型参数 N，该函数能够从小到大，依次打印出自然数中最小的 N 个质数。 比如，当 N = 10，则打印出 2 3 5 7 11 13 17 19 23 29 ★试除法 　　首先要介绍的，当然非”试除法”莫属啦。考虑到有些读者是菜鸟，稍微解释一下。 　　”试除”，顾名思义，就是不断地尝试能否整除。比如要判断自然数 x 是否质数，就不断尝试小于 x 且大于1的自然数，只要有一个能整除，则 x 是合数；否则，x 是质数。 　　显然，试除法是最容易想到的思路。不客气地说，也是最平庸的思路。不过捏，这个最平庸的思路，居然也有好多种境界。大伙儿请看： ◇境界1 　　在试除法中，最最土的做法，就是： 　　假设要判断 x 是否为质数，就从 2 一直尝试到 x-1。这种做法，其效率应该是最差的。如果这道题目有10分，按照这种方式做出的代码，即便正确无误，俺也只给1分。 ◇境界2 　　稍微聪明一点点的程序猿，会想：x 如果有（除了自身以外的）质因数，那肯定会小于等于 x/2，所以捏，他们就从 2 一直尝试到 x/2 即可。 　　这一下子就少了一半的工作量哦，但依然是很笨的办法。打分的话，即便代码正确也只有2分 ◇境界3 　　再稍微聪明一点的程序猿，会想了：除了2以外，所有可能的质因数都是奇数。所以，他们就先尝试 2，然后再尝试从 3 开始一直到 x/2 的所有奇数。 　　这一下子，工作量又少了一半哦。但是，俺不得不说，依然很土。就算代码完全正确也只能得3分。 ◇境界4 　　比前3种程序猿更聪明的，就会发现：其实只要从 2 一直尝试到√ x ，就可以了。估计有些网友想不通了，为什么只要到√ x 即可？ 　　简单解释一下：因数都是成对出现的。比如，100的因数有：1和100，2和50，4和25，5和20，10和10。看出来没有？成对的因数，其中一个必然小于等于100的开平方，另一个大于等于100的开平方。至于严密的数学证明，用小学数学知识就可以搞定，俺就不啰嗦了。 ◇境界5 　　那么，如果先尝试2，然后再针对 3 到√ x 的所有奇数进行试除，是不是就足够优了捏？答案显然是否定的嘛？写到这里，才刚开始热身哦。 　　一些更加聪明的程序猿，会发现一个问题：尝试从 3 到√ x 的所有奇数，还是有些浪费。比如要判断101是否质数，101的根号取整后是10，那么，按照境界4，需要尝试的奇数分别是：3，5，7，9。但是你发现没有，对9的尝试是多余的。不能被3整除，必然不能被9整除……顺着这个思路走下去，这些程序猿就会发现：其实，只要尝试小于√ x 的 质数 即可。而这些质数，恰好前面已经算出来了（是不是觉得很妙？）。 　　所以，处于这种境界的程序猿，会把已经算出的质数，先保存起来，然后用于后续的试除，效率就大大提高了。 　　顺便说一下，这就是算法理论中经常提到的： 以空间换时间 。 ◇补充说明 　　开头的4种境界，基本上是依次递进的。不过，境界5跟境界4，是平级的。在俺考察过的应聘者中，有人想到了境界4但没有想到境界5；反之，也有人想到境界5但没想到境界4。通常，这两种境界只要能想到其中之一，俺会给5-7分；如果两种都想到了，俺会给8-10分。 　　对于俺要招的”初级软件工程师”的岗位，能同时想到境界4和境界5，应该就可以了。如果你对自己要求不高，仅仅满足于浅尝辄止。那么，看到这儿，你就可以打住了，无需再看后续的内容；反之，如果你比较好奇或者希望再多学点东西，请接着往下看。 ★筛法 　　说完”试除法”，再来说说筛法（维基百科的解释在” 这里 “）。俺不妨揣测一下：本文的读者，应该有2/3以上，从来没有听说过筛法。所以捏，顺便跟大伙儿扯扯蛋，聊一下筛法的渊源。 　　这个筛法啊，真的是一个既巧妙又快速的求质数方法。其发明人是公元前250年左右的一位希腊大牛—— 埃拉托斯特尼 。为啥说他是大牛捏？因为他本人精通多个学科和领域，至少包括：数学、天文学、地理学（地理学这个词汇，就是他创立的）、历史学、文学（他是一个诗人）。真的堪称”跨领域的大牛”。 　　他最让俺佩服的是：仅仅用简单的几何方法，测量出了地球的周长、地球与月亮的距离、地球与太阳的距离、赤道与黄道的夹角……而且，这些计算结果跟当代科学家测出的，相差无几。要知道他生活的年代，大概相当于中国的春秋战国。而咱们的老祖宗，一直到明朝还顽固地坚信：天是圆的、地是方的、月亮会被天狗给吃喽…… 　　好了，扯蛋完毕，言归正传。 　　估计很多人把筛法仅仅看成是一种具体的方法。其实， 筛法还是一种很普适的思想 。在处理很多复杂问题的时候，都可以看到筛法的影子。那么，筛法如何求质数捏，说起来很简单： 　　首先，2是公认最小的质数，所以，先把所有2的倍数去掉；然后剩下的那些大于2的数里面，最小的是3，所以3也是质数；然后把所有3的倍数都去掉，剩下的那些大于3的数里面，最小的是5，所以5也是质数…… 　　上述过程不断重复，就可以把某个范围内的合数全都除去（就像被筛子筛掉一样），剩下的就是质数了。维基百科上有一张很形象的动画，能直观地体现出筛法的工作过程。 　　明白了”筛法”的原理，大伙儿应该看出，筛法在速度上是明显优于”试除法”的。当然，筛法的程序实现也分为不同的境界。而且，筛法可讲究的门道更多了。下面，俺分别从不同角度，聊一聊筛法都有哪些讲究。 ◇如何确定质数的分布范围？ 　　这是采用筛法首先会碰到的问题。文本开头给出的那两种需求，其处理的方式完全不同，俺分别说一下。 需求1 　　对于需求1，这个自然不是问题。因为在需求1中，质数的分布范围就是 N，已经给出了，很好办。 需求2 　　但是对于需求2，就难办了。因为需求2给出的 N，表示需要打印的质数的个数，那么这 N 个质数会分布在多大的范围捏？这可是个头疼的问题啊。 　　但是，来应聘的程序猿如果足够牛的话，当然不会被这个问题难倒。因为素数的分布，是有规律可循滴——这就是大名鼎鼎的 素数定理 。 　　稍微懂点数学的，应该知道素数的分布是越往后越稀疏。或者说，素数的密度是越来越低。而素数定理，说白了就是数学家找到了一些公式，用来估计某个范围内的素数，大概有几个。在这些公式中，最简洁的就是 x/ln(x) ，公式中的 ln 表示自然对数（估计很多同学已经忘了啥叫自然对数）。假设要估计1,000,000以内有多少质数，用该公式算出是72,382个，而实际有78,498个，误差约8个百分点。该公式的特点是：估算的范围越大，偏差率越小。 　　有了素数定理，就可以根据要打印的质数个数，反推出这些质数分布在多大的范围内。因为这个质数分布公式有一定的误差（通常小于15%）。为了保险起见，把反推出的素数分布范围再稍微扩大15%，应该就足够了。 　　可能有同学会质疑俺：谁有这么好的记性，能够在笔试过程中背出这些质数分布公式捏？ 　　俺觉得：背不出来是正常滴。但是，对于有一定数学功底的应聘者，假如他/她知道质数分布公式，即便不能完整写出来，只要在答题中体现出：”此处通过质数分布公式推算范围”，那么俺也是认可滴。 　　再啰嗦一次：关键是看idea！ ◇如何设计存储容器？ 　　知道了分布范围，接下来就得构造一个容器，来存储该范围内的所有自然数；然后在筛的过程中，把合数筛掉。那么，这个容器该如何设计捏？不同层次的程序猿，自然设计出来的容器也不同啦。 境界1 　　照例先说说最土的搞法——直接构造一个整型的容器。在筛的过程中把发现的合数删除掉，最后容器中就只剩下质数了。 　　为啥说这种搞法最土捏？ 　　首先，整型的容器，浪费内存空间。比方说，你用的是32位的C/C++或者是Java，那么每个 int 都至少用掉4个字节的内存。当 N 很大时，内存开销就成问题了。 　　其次，当 N 很大时，频繁地对一个大的容器进行删除操作可能会导致频繁的内存分配和释放（具体取决于容器的实现方式）；而频繁的内存分配/释放，会导致明显的CPU占用并可能造成内存碎片。 境界2 　　为了避免境界1导致的弊端，更聪明的程序猿会构造一个定长的布尔型容器（通常用数组）。比方说，质数的分布范围是1,000,000，那么就构造一个包含1,000,000个布尔值的数组。然后把所有元素都初始化为 true。在筛的过程中，一旦发现某个自然数是合数，就以该自然数为下标，把对应的布尔值改为 false。 　　全部筛完之后，遍历数组，找到那些值为 true 的元素，把他们的下标打印出来即可。 　　此种境界的好处在于：其一，由于容器是定长的，运算过程中避免了频繁的内存分配/释放；其二，在某些语言中，布尔型占用的空间比整型要小。比如C++的 bool 仅用1字节。 境界3 　　虽然境界2解决了境界1的弊端，但还是有很大的优化空间。有些程序猿会想出按位（bit）存储的思路。这其实是在境界2的基础上，优化了空间性能。俺觉得：C/C++出身的或者是玩过汇编语言的，比较容易往这方面想。 　　以C++为例。一个bool占用1字节内存。而1个字节有8个比特，每个比特可以表示0或1。所以，当你使用按位存储的方式，一个字节可以拿来当8个布尔型使用。所以，达到此境界的程序猿，会构造一个定长的byte数组，数组的每个byte存储8个布尔值。空间性能相比境界2，提高8倍（对于C++而言）。如果某种语言使用4字节表示布尔型，那么境界3比境界2，空间利用率提高32倍。 ★总结 　　看到俺写”总结”二字，很多网友心想：总算看完了，知道该怎么求质数才是最优的了。 　　其实，你们又错了，本文才写了不到一半。考虑到篇幅已经有点长，而且俺打了这么多字，也有点累了，暂时刹住话匣子，下次接着聊。 　　希望看了今天这个介绍，大伙儿应该明白一个道理：山外有山、天外有天。每一个技术领域里面的每一个细小的分支，深究下去都有很多的门道与奥妙。在你深究的过程中，必然会学到很多东西。深究的过程也就是你能力提高的过程。 　　本文后续的内容，会介绍刚才提到的按位存储法还有哪些缺陷，该如何解决。另外，还会介绍其它一些求质数的方法。 版权声明 本博客所有的原创文章，作者皆保留版权。转载必须包含本声明，保持本文完整，并以超链接形式注明作者” 编程随想 “和本文原始地址。 学习翻墙 发任意邮件到 help_gfw@yahoo.com 获取翻墙扫盲教程 (用国外邮箱以免被墙) 如有其它问题, 用 program.think@gmail.com 联系俺