前几天JeffChen告诉我他要学习Python，后来他找到了SPOJ这个在线的算法竞赛网站，可以支持很多种不同的编程语言，其中包括Python。而我突然发现我很久以前就注册了我的帐号，现在一下又来了兴趣。虽然在中学的时候也搞过信息学奥赛，不过没有出过江苏省，和ACM的差距还是非常非常大。因为我数学功底不行，这方面没法深入，所以转投应用领域，加上很懒，所以喜欢用脚本语言。 言归正传，下面把我解决PRIME1这道问题的方法记录下来： 求质数最经典的方法是Eratosthenes筛选法，一般都是利用一个布尔数组作为筛选器，将下标作为目标数，元素作为该目标是否为质数的标志，并且对于给定范围1~n之间的数，只需要筛选掉1到sqrt(n)之间的质数的所有倍数，剩下的就都是质数了。 起初我使用Python是直接利用range函数生成列表，并没有用到筛选表，通过filter函数和取模%筛选掉质数，最后直接得到整个列表。但是问题在于性能低，另外对于大数则会内存不够（无法生成给定长度的列表），我也尝试过使用dict对象来建立筛选器，不过都失败了。 问题关键在于Python是脚本语言，对于速度，尤其是列表的遍历，不应该使用filter或者for循环，应该使用列表理解，,并且抛弃%运算，配合python列表的slice语法，即x[start:end:step]=[...]的方法，进行定长步长（以质数为步长）的批量替换。 对于内存不够，可以建立一个映射关系，最后的筛选数组中，不考虑偶数，把奇数转换成筛选数组的索引（n/2-3），但需要一些算法精确配合上面的slice语法计算起始位置和长度。
Monthly Archives: 十月 2008
找房子
2008年10月26日 – 6:23 下午
找房子确实是一件非常麻烦的事情，尤其是在上海，因为房子少，好房子更少，又好又便宜的房子几乎就没有了。但在搬了若干次家之后，我却发现事情并没有想象中那么糟糕（也就稍微好一点点）。 一般而言，房价受到这几个因素影响：房源少，房租就贵；房子面积越大则越贵；房子越新越贵；房子装修越好则越贵；小区环境好、周边好则贵，即地段因素。 通常情况下，我们会认为谁出钱多房东就租给谁。然而事实上房屋出租并不像普通的货物的一锤子买卖那样，房东往往会挑剔房客。这可能是因为租房子是服务周期较长的服务业，由房东提供房子，房客来租，这段时间内，房客和房东会保持互相影响。一般一些（曾经是）自住的房子的房东，往往会希望房子能保持地比较干净，而且不希望有过多的集体活动，忌房客的背景不干净，所以常常会挑高素质的房客。 我爸爸被调到南京长期工作，妈妈也过去照顾他，所以准备租一套房子，单位补贴的标准是1500元／月。他们看了不少房子，最后看到有一户房子不错，是房东以前的房子，由于比较干净，所以房东要价至少要1600元／月就不肯再低。爸爸就犹豫了两天，后来联系的时候房东已经把东西租出去了。然而再过了一周，事情出现了转机，房东突然又打电话问爸爸要不要住，要住就1500可以。情况原来是这样，因为原来签约的房客，其实公司里打算弄成公司的宿舍，房东不希望这样，所以就毁约了，而我爸妈这种两口子是最令房东满意和放心的。 同样地，我在租房的过程中也听到房东说过，前几天还有个女的，打扮的很艳，要价XXXX元都不还价（比给我的价格高很多），房东觉得太爽快肯定不是自己赚的钱，不放心，而看我和我GF都是白领，高级知识分子，才租给我们。 所以，租房子这个事情，就好比谈恋爱，还要符合双方意愿和条件。房东的房子的情况和他对房客的要求，决定了房客的群体，然后如果价格越高，群体就越小。所以即使我不能出更好的价钱，但是我本身的情况算是付出的一种特殊的价钱。 说的有点乱了，转个寓言： 《吕氏春秋》记载了这样一个故事：洧水发了大水，淹死了郑国富户家的一员。尸体被别人打捞起来，富户的家人要求赎回。然而捞到尸体的人要价太高，富户的家 人不愿接受，他们找邓析出主意。邓析说：“不用着急，除你之外，他还会卖给谁？”捞到尸体的人等得急了，也去找邓析要主意。邓析却回答：“不要着急，他不从你这里买，还能从谁那里买？” 另外，在新浪网上看到一则新闻沪群租市场仍很火 房东10分钟接3个看房电话。只能群租的人，肯定是暂时买不起房子的。另外一方面，能提供群租的房东，肯定都是有钱的炒房者，自己的房子哪会随便出租给群租呢。
Windows黑屏
2008年10月26日 – 5:21 下午
最近Windows黑屏的事情炒得比较热，从网上的辩论来看，庆幸的是还有很多人是有良知有是非判断能力的，心寒的还是有那么多愚昧无知又自以为是的人。 现在我是不惧怕黑屏的，我已经用了很久Linux（Ubuntu），而且在用Linux之前，我的笔记本上都是预装的OEM版Windows，而在这个系统上，我用得绝大部分是开源软件，比如我没有装Microsoft Office，用的是OpenOffice.org，少部分用的是免费的软件，例如Visual Studio Express Edition。 当然我出身也不光彩，我在上高中的时候，还一直用的盗版软件，依稀记得当年97年左右老家的新华书店上卖盗版的光盘，还要25元/张。所以首先我觉得应该感谢微软，至少微软曾经的默许，让尚处于困难时期的中国和中国群众能用上好用的Windows，开启了中国信息产业的大门。有人认为这是微软的阴谋，我认为无论如何我们还是应该从感恩的角度来看微软，我认为微软的所做所为还是对得起我们的。 至于这次，我觉得微软做得事情虽然很有争议，我也觉得是一件好事，至少可以让大家一起来讨论，也唤醒一部分人对于版权的意识。 最后还是说那一句，出来混迟早是要还的。尤其是我们搞软件的，自己都用盗版，怎么能指望别人买自己作的正版呢！ 延伸阅读：李子暘：小偷强盗也需要私有产权
网速问题2
2008年10月20日 – 8:59 下午
上一次说过ADSL网速的问题，后来因想把Ubuntu升级到8.10，然而国内的镜像没有跟进，于是选择美国的镜像，有些镜像下载速度非常快，可以接近200KB/s，然而这往往都是短暂的，通常不过10s，速度就会立刻降为0，然后在0-10KB/s以内波动，比原先认为的20KB/s还惨。我百思不得其解，幸好在国外有个朋友，让他在他的服务器上给我开了个帐号，我利用SSH通道作代理来下载文件，结果效果还是不错的，下载速度可以在50KB/s左右，速度还是比较稳定的，至少不用担心降到0K起不来。为何加密通道则影响不大呢？大家可以讨论讨论。
手机直板的问题
2008年10月16日 – 11:47 上午
我个人一直是用直板机，也没有用过翻盖，一方面因为比较懒，不喜欢翻盖子，另外一方面直板机通常比翻盖和滑盖的结实。但是直板的有个致命弱点就是容易误按键，如误拨号等问题。翻盖的则没有这个问题，因为合上了，按不到按键了。于是直板机出现了键盘锁，可以极大减少误操作，但是有个问题无法解决，那就是无法保证有来电的时候不误接听。随着现在智能手机越来越多，很多手机都是一个大屏幕，但是下边还是有一个接通键和一个挂断键，滑盖机也是一样。我女友买了个新手机，经常出现包里晃荡的时候不小心拨通了我的手机，或者是我在拨她的电话的时候，莫名地接通了却没有人说话。 不知道直板机如何最终避免这个问题。
横向扩展（Facebook）
2008年10月13日 – 10:46 上午
原文：Scaling Out 作者：Jason Sobel (notes) 翻译：ShiningRay 我于2007年四月加入了Facebook，在结束了几周的课程之后，我的经理Robert Johnson来找我。我们谈了很久，不过内容可以归结为： Bobby: “那么，Jason，我们要在2008年之前在弗吉尼亚开一个新的数据中心。你能去帮点忙吗？” Me: “呃…. 可以?” Bobby: “很好！” 我在Facebook的第一个项目上投入的要比我预期的多一点点，但是我认为这是为何我们拥有如此一个非常强大的工程组织的原因；我们还有很多难题有待解决，这里每个人都迫不及待要立刻去解决他们。我开始了解为何我们需要建造一个新的数据中心以及我们需要解决什么问题才能让他正常工作。 有何必要？ 在东海岸建造一个新的数据中心的主要原因就是“延迟”。在一个高速连接上发送一个包横穿大陆需要大概70微秒的时间，而对于普通的互联网用户而言，可能会需要的时间就长得多。通过将服务器放在弗吉尼亚，我们可以大大减少给东海岸和欧洲的用户传送网页的时间。 第二个关注点是空间、能源和灾难恢复。在我们位于加利福尼亚的主数据中心中已经没有多少物理空间了，而弗吉尼亚的点可以给我们充分的空间添加东西。我们还有一个类似问题就是要给予充足的电能驱动所有的服务器。最后，如果把我们限制在某个单独的地方，意味着如果出现灾难事件（断电、地震、怪兽），可能会导致Facebook长时间无法访问。 开始构建！ 在我们能处理应用级的问题之前，我们的小组在弗吉尼亚投入了大量的心血构建服务器和物理空间。他们还完成了数据中心之间的网络和低延迟光线通道连接。这些工作是非常巨大的工程，然而我们顶尖的团队使之看上去像是小菜一碟。 网络和硬件都到位后，我们搭建了标准的3层架构：Web服务器，memcache服务器和MySQL数据库。在弗吉尼亚的MySQL数据库作为西海岸的数据库的从数据库（Slave）运行，所以我们花了几周的时间复制所有的数据，然后建立同步复制流（replication stream）。 现在硬件、网络和基础的设备都已经建立好，那现在就要面对两个主要的应用级的挑战：缓存一致性（Cache Consistency）和流量路径选择（traffic routing）。 缓存一致性 先说一下我们的缓存模型：当一个用户修改了数据对象后，我们的底层设施会向数据库写入新的值，并且从memcache中删除旧的值（如果存在）。下一次用户请求该用户对象的时候，我们从数据库中取出新的结果并写入memcache。后续的请求就会直接从从memcache中取出数据直到缓存过期或者被另外一次更新删除。 这种设置在只有一套数据库的时候运行得很好，因为我们只有当数据库完成了新值的写操作之后才删除memcache中的值。这种方式保证了我们能够从数据库中获得新值并且放入memcache中。然而，当在东海岸有一个从数据库后，情况就有些棘手了。 当我们在西海岸的主数据库中更新了一些数据之后，在东海岸的从数据库能正确反映这些新数值之前，中间有一个同步复制的延迟。通常这个延迟小于一秒钟，但是在高峰时期，它可能会延长到20秒。 现在我们假设在更新了加利福尼亚的主数据库的同时，我们从弗吉尼亚的memcache层中删除了旧值。然后有一个对弗吉尼亚的从数据库的读操作可能由于复制延迟还是看到的旧数值。然后弗吉尼亚的memcache可能会更新为旧的（不正确）的数值，然后它可能被“困住”直到被删除。如你所见，最差的情况是弗吉尼亚的memcache层可能总是同一个版本而非正确的数据。 考虑下面的例子： 我将我的名字从“Jason”改成了“Monkey” 我们把“Monkey”写入了加利福尼亚的主数据库并且从加利福尼亚和弗吉尼亚的memcache中删除了原来的名字 有个人在弗吉尼亚访问我的信息 在memcache中没有找到我的姓名信息，所哟我们从弗吉尼亚的从数据库中读取，由于复制的延迟获得了“Jason” 我们将姓名“Jason”存入弗吉尼亚的memcache 同步复制上来了，我们将名字信息在从数据库中更新为“Monkey” 另一个人在弗吉尼亚访问我的信息 我们在memcache中找到了名字并返回“Jason”。 在我再更新我的名字或者数据过期需要再访问数据库之前，我的名字在弗吉尼亚会一直显示为“Jason”，在加利福尼亚显示为“Monkey”。混乱吧？确实。欢迎来到分布式系统的世界，在这里一致性确实是一个难题。 幸好，解决方案要比问题容易解释。我们对MySQL做了一个小小的改动，让MySQL能在同步复制流中附加一个额外的信息。我们利用这个功能将要变更的所有数据对象追加到给定查询上，然后当从数据库“看到”这些对象后，要负责在进行了数据库更新后将这些值从缓存中删除。 我们是怎么做到的呢？MySQL是用了一个词法解析器和yacc语法来定义查询的结构然后对其进行解析。为了解释方便，我对其进行了简化，这个语法最顶层差不多如下： query: statement END_OF_INPUT {}; statement: alter | analyze | backup | call [...]
真让人无语的事
2008年10月12日 – 3:57 下午
今天阳光明媚，于是在阳台外面晒被子。终于看到快4点可以收被子了，突然听见阳台上有滴水的声音，一看，被子怎么湿了，难道上面有人洗衣服，抬头一看，只有六楼有条裤子，而且上午就晒在那里，不可能有水。然后突然看到有双手在那里拧抹布，只见水就滴下来了。我™就大叫，同学你注意点，我摸摸滴下来的水，感觉还有点奶味。顿时很火，刚转身再把头伸出窗外，感觉头上被淋了，抬头一看，一个脑袋嗖得进去了。好像是一个小孩。好啊，我™已经骂过了，还和我玩，那我和他玩到底。 把湿了的被子拿回来，然后径直走到6楼找那个小孩，那小孩还偷偷从门缝里看我，就是不开门。好吧，刚好房东就在4楼，直接找房东解决。我把这个事情和房东一说，房东告诉我那家人正准备搬到一楼，然后就到一楼去找人，找到了家里的奶奶，然后再去六楼开门，原来有一男一女两个小孩在房子里，整个房子里特别乱。结果我还没开口说啥，小女孩就哭。接着房东到我家，我给他看了罪证，他说要拿去给小孩的大人看看。这时最让我无语的事情发生了。 小孩的奶奶看到了这淋湿的被套说，“这个只是粉笔灰的水”，“香的哇”，我艸，你™就是香水，我允许了吗？我晚上睡觉怎么办。我想说几句，小孩的奶奶却说，“小孩哇，没办法”，我就说了，“我不是说要怪罪他们，我希望他们知道他们这么做是错的，以后不要在犯了”，小孩的奶奶保证说，“以后我们就搬到一楼了，不会再有这种事情了”。 我就郁闷，有这种小孩就是你们这种大人教育出来的，可能以后到了一楼确实不会再弄水到我的被子上，但有可能还会搞别的花样。连是非都不知道如何去分辨，连错误都不知道承认。长辈不知道如何做正确人，小孩又怎么会知道。我本来还只是想稍微教育一下小孩，不过这样的长辈就算了。 我下楼之前，小孩的奶奶还说，“我来帮你洗”，“我来帮你洗”。 谢谢噢谢谢，我不需要你帮我洗，我有洗衣机，我只是希望不要出现类似事件，我希望这样小孩能从中学到点什么东西。不过看到这样的长辈，我知她不会有出息了。 PS: 这并不是第一次，之前阳台的窗台上被人扔过一个口香糖，粘得很恶心，现在我也知道了。
网速问题
2008年10月11日 – 10:28 上午
我一直用的是中国电信的2M ADSL，在下载无数东西之后，发现一个规律：从国外（尤其是美国）的服务器下载内容，无论一开始速度如何地快，达到200K/s，在5s之后，速度会立刻降低到20K/s左右，我一直想不明白这是为什么，猜想那些服务器都有流量控制，但为何不控制前5s呢？而国内下载则不出现这些问题。因此我认为应该是诸如电信这样的ISP，为了降低国际带宽（很可能是为了省钱）而想出来的方法。
超酷3D JavaScript相册
2008年10月10日 – 12:02 下午
实现了3D鱼眼效果，不过相对于Flash做的东西，还不够流畅和炫。 另外，我在Chrome(0.3.154.0)中预览本网页，发现有明显的滞后感，而在Firefox 3.0.3上则非常流畅，IE7也很流畅。可能在于它用到了一些滤镜特效，Chrome对于图像渲染的速度上可能还比较慢——Chrome在字体渲染上也比较差——即便他的JavaScript引擎速度很快。 http://www.dhteumeuleu.com/runscript.php?scr=photo3D.html
亚原子粒子有自由意志吗？
2008年10月3日 – 11:39 下午
作者：Julie Rehmeyer 原文：Do subatomic particles have free will? 翻译：ShiningRay 如果我们有自由意志，那么亚原子粒子也有，有数学家说可以证明。 “如果原子永不为创始那些攫取命运的纠葛和永恒的因果循环的新运动而转向，那么什么才是这地球上的生物所拥有的自由意志的源泉？” ——卢克莱修，罗马哲学家兼诗人，公元前99-55。 人类自由意志可能哲学主题中最模棱两可的，超出数学证明范畴。然而两位德高望重的普林斯通数学家，表示他们已经证明了如果只要人类有那么一点点最小量的自由意志，那么原子本身的行为就一定无法预测。 该发现不会给多数物理学家造成困扰，因为量子力学的传统解释已经包含了不确定性了。量子原理表示，最好的方式是预测一个粒子的某种方式的行为的可能性。 但是爱因斯坦开始的物理学家则对这个想法非常不满。爱因斯坦最著名的抱怨——“上帝不掷筛子”。确实，自从量子理学诞生那刻起，一些物理学家给出了它的等式的替代解法，旨在消除其不确定性原理。最著名的替代法由物理学家David Bohm给出，他在1950s争论说，亚原子粒子的行为完全由无法被观测的“隐变量”决定。 Conway和Kochen说该研究是没戏的，同时他们表示不确定性是继承自这个世界本身，而不是在量子理论中。并且他们二人对支持Bohm的物理学家以及其他类似想法的人说：放弃确定性，要么就放弃自由意志。即使是一点点自由意志。 他们的论点源自Kochen在40年前用Ernst Specker创建的证明。亚原子粒子有一个特性叫做“自旋”，它可以绕任意轴进行。已有实验证明了一类自旋为1粒子有一中独特的属性：选择三个相互垂直的坐标，然后探测该自旋为1的粒子确定它绕哪个轴为的自旋0。确切地结果是，其中一个轴会自旋为0，另外两个会有非0自旋。Conway和Kochen称之为1-0-1规则。 自旋是目前物理学家尚不能在探测之前事先预测的特性之一。然而，任何人都可能会想象粒子绕任意轴的自旋是在任何人去探测它之前就已经确定好的。这也是我们在生活中的常见假设。我们不会想象，比如，一个栏杆是因为我们看到了它，所以它变成了白色——我们认为它应该一直都是白色。 但是Kochen和Specker证明了这个假设——栏杆一直是白色——在奇异的亚原子粒子的世界中是说不通的。他们是用了一个纯数学的论据表明了粒子无法用一种与1-0-1规则一致的方式来选择绕每一个可想到的轴旋转。实际上，一个只有33个轴的集合已经足够令粒子变成一个悖论。它可以选择绕前32个符合该规则的轴自旋，然而对于最后一个，无论0或者非0都不可能。选择零自旋将会创建一套有两个零点的正交的三个轴，选择非零自旋则会创建另一套，有正交的三个轴，以及三个非零点，两种方式都会打破1-0-1规则。 这也就意味着，粒子在被测量之前不可能在任何一个方向都有一个确定的自旋，Kochen和Specker总结到。如果该情况成立，那么物理学家应该能偶然观察到它打破了1-0-1规则，而这个从未发生过。相反，它必须在瞬间“决定”怎么自旋。 Conway将该情况与“二十个问题”游戏进行了比较。如果你公平地玩该游戏，你在一开始就确定了某个对象，然后诚实地回答每个问题，然后祈祷对手不会过早推出你的想法。然而一个机灵的玩家会去骗人，在玩了一半就去改变自己选的对象。在这种情况下，它的答案就不能事先确定了。Kochen和Specker说，粒子就像一个会骗人的玩家。他们发现没有哪个单一的对象能一次完全满足所有“问题”（或者说所有33个轴）。 但是还有另外一种可能的解释。如果粒子的自旋是完全确定的——但是依赖于和这个宇宙的状态相关的别的东西。这就好像“二十个问题”中的一个玩家它不管对手问什么问题，只要对方问的问题是以“是不是”开头，那么这个玩家就在脑子里确定选一个驴子，并回答是，否则，这个玩家就选马，并回答否。在这种情况下，它的回答也是可预先确定的即使他在脑子里一个对象也没选。 Conway和Kochen说他们闲在证明了粒子的响应是无法被预先确定的，即使后面这个认为可行的解释中。“我们可以证明没有任何算法和方法，能让粒子可以事先给出唯一以及确切的答案，”Conway说。“我还是很惊奇我们居然能证明这一点。” 他们为他们的证明编造了一个想法上的实验。可以纠结两个自旋1的粒子这样他们的自旋就在每一个可能的轴上都一样，并且保持如此，即使他们彼此相隔很远。这样纠结两个粒子，然后将其中一个发给位于火星的叫做Alice的物理学家，另一个发给位于地球叫做Bob的物理学家。根据相对论，这两个粒子之间是不能传递信息的。Alice和Bob分别在某个他们自由选择的轴上探测粒子。如果 Alice和Bob碰巧选择了相同的轴，那么他们会得到相同的答案。 现在，想象该粒子就像“20个问题”的玩家，它选的对象有时候是一头了驴，有时候是一匹马，根据不变的规则决定什么时候回答哪种动物。无论规则是什么，它都作用于纠结的两个粒子中的每一个，并且可以造成他们有同样的自旋。这就好像“20 个问题”的玩家被克隆了，并且二者都被强制针对相同的动物给出回答。 但是Conway和Kochen证明了这种情节对于互不通信的粒子是不可能的。他们调用了老的Kochen-Specker悖论来证明如果自旋1粒子的行为是可预先确定的那么它就不允许“改变它的动物”，它就不能给出与1-0-1相一致的答案。所以如果Alice和Bob幸运地选择了同样的轴，那么他们应该能强迫粒子要么结果不同要么违反1-0-1理论——这与实验结果相矛盾。 Kochen和Conway说解决悖论的最佳方法就是接受粒子的自旋只有到它被测量的时候才存在这个论断。不过还有一种方法跳出他们的套：假设当时Alice和Bob对于选择哪个轴进行测量并非自由的选择。那么大自然会神秘地阻止他们去选择会触犯规则的那些轴。Kochen和Conway不能完全消除这种可能性，不过Kochen说，“任何走在大街上的人都会说：‘别搞笑了’很自然的感觉是，当然了，我们会根据我们自己的自由意志来做。不能完全消除这种可能性，但是就目前我们所知而言，无疑我们可能选择在实验中按哪个按钮。” 理想情况下，一个数学证明应该解决一切的不确定性，但是Kochen和Conway并没有让很多他们提到的物理学家相信。“我不相信”，Rutgers大学的Sheldon Goldstein说，他是一名Bohm支持者。他认为这些言论没有包含什么新东西，而且他对自由意志只是实际存在（而非原理上）的观点感到满意。四年前，两位数学家发布了他们的成果后，他和他的助手花了很长时间与两位科学家探讨了这些问题。两位科学家的新版理论，在7月21日，发表在了 Arxiv.org，旨在根据批评的观点来强化理论结果。然而，大家还未达成共识。“当人们不能互相沟通的时候，还是非常郁闷的”Goldstein 说，“我们知道在原则上是对的，但是你认为这不可能。” 不过，荷兰的Utrecht大学的Gerard’t Hooft——他获得了1999年的诺贝尔物理学奖——说他俩的解决是合法的，不过他选择了确定性原理而非自由意志。“作为一个坚定的确定论者，我会说那没错，一个实验者选择去测量什么是从开天辟地那时就已经确定了，包括那些东西——他决定称之为光子——的属性，”’t Hooft说。“如果你坚信确定性原理，你必须自始至终坚信它。不能逃避。Conway和Kochen这里用一种优美的方式证明了对伪确定性原理的半心半意的信仰是无以为继的。”
