Xiaoguang Xing's Blog

原来对摄影一直有兴趣，对dslr也研究了一下，这趟去巴黎让我几乎断绝了这个念头，一天几百张拍下来，哪有功夫去考虑光圈快门ISO什么的，大概有个构图，光线合适，就按一下快门走人了，出来的效果也还可以。所以由扇C家的400D到扇C家的IXUS 850，在卢浮宫还碰到一个女孩用这个，让我帮她拍一下全身照。以后有钱了先上卡片机，等中毒再深些才上dslr吧

http://picasaweb.google.com/Xiaoguang.Xing/MeYanInParis

今天去学校办事，本来是很久以前的表格，最近因为要申请论文，整理资料的时候考试中心发现问题，原来是相关的教授在考试单子上签字了，可是系里总负责的教授没有签字，要去补个签字，还有我的一门专业方向不是学校规定的，要自己申请才行，我不太清楚手续，所以也一并前去打探一番，负责的秘书Frau Dahlheim人真是好到家，每次找她办事甭管成不成都让你心里舒服，偏巧今天一周一次的办公时间教授有事不能来，网上的通知我忘了看了，到地方了才发现门上的小红纸条，抱着试试看的心理敲开了Dahlheim的门，一通交涉后Dahlheim女士帮我弄妥了，说等下周Prof. Boit来了签上字就Ok了，我说有点着急她就说我帮你想办法，你周四来吧。这叫什么精神，国际主义精神，好人啊！

出了门和羊羊汇做一处，时候尚早，于是直奔肯德基，今天是鸡翅的特价日。我们来过几次了，对其他的也不感兴趣，只每人要了六只鸡翅，坐在一角，有滋有味的吃起来了，你说这垃圾食品我咋这么喜欢呢，真是不可药救。

回家要坐S-Bahn。今天来学校的时候特意用手机算了一下，车从东边的Alexsander Platz开到西边的Zoologische Garten，这两个我经常要往返的车站，一共用了12分钟，算是相当快了，不禁再次对北京的交通产生很多期待。这时车厢里有人说话，意思就是，您好，您吃了吗，您肯定吃了，要不怎么这么红光满面印堂发亮呢，您发财，我是卖小报的，您买一份，您不买赏几个小钱也行，陪一笑脸加几句好话。其实就是德国给失业人士的一种资助，办一种报纸让他们去车上卖，有点福利。这人话说完就四处转，看有没有人给钱。一般给钱的都是老人，心肠好又有闲钱，给俩不在乎。我正要从兜里掏手机看用了多长时间了，可巧这位到我身边了，我闹一大红脸，摆摆手，人家也就过去了。回家的时候刚上车坐定就有人说话，您的车票。

德国公交系统实行一票通，一票可以做市内的任何公共交通，包括汽车地铁城铁有轨电车渡船。并且是自动售票检票，所以车上是没有人检票的。如果有人不买票也照样坐车，于是交通公司就找一些人随机的在车上检票，开口都是那句，您的车票。

车里的人都要掏车票，这人又说了，您的车票，我是不看的，要不您买份报纸？哦，又是他！

太可惜了，我真正喜欢的相声演员之一，宇宙牌香烟，五官争功，经典中的经典啊。希望马老师一路走好...

今日(20日)10：25分，著名的相声演员马季在北京安贞医院因心脏病去世，终年72岁

马季生于1934年，原名马树槐，祖籍天津宝坻，本人生于北京。曾做过工厂学徒和书店店员，1951年起因爱好，业余表演相声，1956年由中央广播文工团说唱团吸收为专业相声演员，师从侯宝林边学习边表演。

新浪娱乐消息，他善于表演反映现实生活的新相声作品，在相声艺术长于讽刺的传统之外，开启了以赞美新生活和新的英雄人物为主题的“歌颂型”对口相声的新生面，其中以《登山英雄赞》、《画像》和《找舅舅》等节目影响为大。之后马季的创作和表演趋于全面，除能表演传统节目外，中年开始还创作演出了对口相声如《友谊颂》、《舞台风雷》、《多层饭店》，单口相声《宇宙牌香烟》和群口相声《五官争功》等。马季也很重视对相声理论的研究，力图使自身的艺术创造更趋自觉。为此，他不仅有《马季相声选》出版，还著有《相声艺术漫谈》一书行世。但马季毕竟主要是相声表演艺术家，他的表演、热情洋溢，挥洒自如；技巧运用上以说为主，注重谐趣。

代表作有：

《找舅舅》、《英雄小八路》、《登山英雄赞》、《画像》、《新桃花源记》、《女队长》、《白骨精现行记》、《舞台风雷》、《五官争功》等。

ABSTRACT.
Most emerging radio technologies for Wireless Personal Area Networks such as the
Bluetooth protocol are designed to operate in the 2.4 GHz ISM band. Since both Bluetooth
and IEEE 802.11 devices use the same frequency band and may likely come together in a lap-
top or may be close together at a desktop, interference may lead to significant performance
degradation. The main goal of this paper is to describe the interference problem and to high-
light a coexistence framework for these technologies to operate in a proximal environment. We
give an overview of several coexistence solutions proposed for various interference scenarios.
We study several factors that may impact interference such as fragmentation and the choice of
packet encapsulation and give simulation results for selected scenarios and configurations of
interest.

有的时候还是跟自己说要多原创，可是有的时候是没时间，有的时候是懒，有的时候是没心情。这两篇东西都很有意义，算是学习笔记也好吧。

李开复：算法的力量

算法是计算机科学领域最重要的基石之一，但却受到了国内一些程序员的冷落。许多学生看到一些公司在招聘时要求的编程语言五花八门就产生了一种误解，认为学计算机就是学各种编程语言，或者认为，学习最新的语言、技术、标准就是最好的铺路方法。其实大家都被这些公司误导了。编程语言虽然该学，但是学习计算机算法和理论更重要，因为计算机算法和理论更重要，因为计算机语言和开发平台日新月异，但万变不离其宗的是那些算法和理论，例如数据结构、算法、编译原理、计算机体系结构、关系型数据库原理等等。在“开复学生网”上，有位同学生动地把这些基础课程比拟为“内功”，把新的语言、技术、标准比拟为“外功”。整天赶时髦的人最后只懂得招式，没有功力，是不可能成为高手的。

算法与我

当我在1980年转入计算机科学系时，还没有多少人的专业方向是计算机科学。有许多其他系的人嘲笑我们说：“知道为什么只有你们系要加一个‘科学’，而没有‘物理科学系’ 或‘化学科学系’吗？因为人家是真的科学，不需要画蛇添足，而你们自己心虚，生怕不‘科学’，才这样欲盖弥彰。”其实，这点他们彻底弄错了。真正学懂计算机的人（不只是“编程匠”）都对数学有相当的造诣，既能用科学家的严谨思维来求证，也能用工程师的务实手段来解决问题——而这种思维和手段的最佳演绎就是 “算法”。

记得我读博时写的Othello对弈软件获得了世界冠军。当时，得第二名的人认为我是靠侥幸才打赢他，不服气地问我的程序平均每秒能搜索多少步棋，当他发现我的软件在搜索效率上比他快60多倍时，才彻底服输。为什么在同样的机器上，我可以多做60倍的工作呢？这是因为我用了一个最新的算法，能够把一个指数函数转换成四个近似的表，只要用常数时间就可得到近似的答案。在这个例子中，是否用对算法才是能否赢得世界冠军的关键。

还记得1988年贝尔实验室副总裁亲自来访问我的学校，目的就是为了想了解为什么他们的语音识别系统比我开发的慢几十倍，而且，在扩大至大词汇系统后，速度差异更有几百倍之多。他们虽然买了几台超级计算机，勉强让系统跑了起来，但这么贵的计算资源让他们的产品部门很反感，因为“昂贵”的技术是没有应用前景的。在与他们探讨的过程中，我惊讶地发现一个O(n*m)的动态规划(dynamic programming)居然被他们做成了O(n*n*m)。更惊讶的是，他们还为此发表了不少文章，甚至为自己的算法起了一个很特别的名字，并将算法提名到一个科学会议里，希望能得到大奖。当时，贝尔实验室的研究员当然绝顶聪明，但他们全都是学数学、物理或电机出身，从未学过计算机科学或算法，才犯了这么基本的错误。我想那些人以后再也不会嘲笑学计算机科学的人了吧！

网络时代的算法

有人也许会说：“今天计算机这么快，算法还重要吗？”其实永远不会有太快的计算机，因为我们总会想出新的应用。虽然在摩尔定律的作用下，计算机的计算能力每年都在飞快增长，价格也在不断下降。可我们不要忘记，需要处理的信息量更是呈指数级的增长。现在每人每天都会创造出大量数据（照片，视频，语音，文本等等）。日益先进的纪录和存储手段使我们每个人的信息量都在爆炸式的增长。互联网的信息流量和日志容量也在飞快增长。在科学研究方面，随着研究手段的进步，数据量更是达到了前所未有的程度。无论是三维图形、海量数据处理、机器学习、语音识别，都需要极大的计算量。在网络时代，越来越多的挑战需要靠卓越的算法来解决。

再举另一个网络时代的例子。在互联网和手机搜索，如果要找附近的咖啡店，那么搜索引擎该怎么处理这个请求呢？最简单的办法就是把整个城市的咖啡馆都找出来，然后计算出它们的所在位置与你之间的距离，再进行排序，然后返回最近的结果。但该如何计算距离呢？图论里有不少算法可以解决这个问题。

这么做也许是最直观的，但绝对不是最迅速的。如果一个城市只有为数不多的咖啡馆，那么这么做应该没什么问题，反正计算量不大。但如果一个城市里有很多咖啡馆，又有很多用户都需要类似的搜索，那么服务器所承受的压力就大多了。在这种情况下，我们该怎样优化算法呢？

首先，我们可以把整个城市的咖啡馆做一次“预处理”。比如，把一个城市分成若干个“格子(grid)”，然后根据用户所在的位置把他放到某一个格子里，只对格子里的咖啡馆进行距离排序。

问题又来了，如果格子大小一样，那么绝大多数结果都可能出现在市中心的一个格子里，而郊区的格子里只有极少的结果。在这种情况下，我们应该把市中心多分出几个格子。更进一步，格子应该是一个“树结构”，最顶层是一个大格——整个城市，然后逐层下降，格子越来越小，这样有利于用户进行精确搜索——如果在最底层的格子里搜索结果不多，用户可以逐级上升，放大搜索范围。

上述算法对咖啡馆的例子很实用，但是它具有通用性吗？答案是否定的。把咖啡馆抽象一下，它是一个“点”，如果要搜索一个“面”该怎么办呢？比如，用户想去一个水库玩，而一个水库有好几个入口，那么哪一个离用户最近呢？这个时候，上述“树结构”就要改成“r-tree”，因为树中间的每一个节点都是一个范围，一个有边界的范围（参考:http://www.cs.umd.edu/~hjs/rtrees/index.html）。

通过这个小例子，我们看到，应用程序的要求千变万化，很多时候需要把一个复杂的问题分解成若干简单的小问题，然后再选用合适的算法和数据结构。

并行算法：Google的核心优势

上面的例子在Google里就要算是小case了！每天Google的网站要处理十亿个以上的搜索，GMail要储存几千万用户的2G邮箱，Google Earth要让数十万用户同时在整个地球上遨游，并将合适的图片经过互联网提交给每个用户。如果没有好的算法，这些应用都无法成为现实。

在这些的应用中，哪怕是最基本的问题都会给传统的计算带来很大的挑战。例如，每天都有十亿以上的用户访问Google的网站，使用Google的服务，也产生很多很多的日志(Log)。因为Log每份每秒都在飞速增加，我们必须有聪明的办法来进行处理。我曾经在面试中问过关于如何对Log进行一些分析处理的问题，有很多面试者的回答虽然在逻辑上正确，但是实际应用中是几乎不可行的。按照它们的算法，即便用上几万台机器，我们的处理速度都根不上数据产生的速度。

那么Google是如何解决这些问题的？

首先，在网络时代，就算有最好的算法，也要能在并行计算的环境下执行。在Google的数据中心，我们使用的是超大的并行计算机。但传统的并行算法运行时，效率会在增加机器数量后迅速降低，也就是说，十台机器如果有五倍的效果，增加到一千台时也许就只有几十倍的效果。这种事半功倍的代价是没有哪家公司可以负担得起的。而且，在许多并行算法中，只要一个结点犯错误，所有计算都会前功尽弃。

那么Google是如何开发出既有效率又能容错的并行计算的呢？

Google最资深的计算机科学家Jeff Dean认识到，Google所需的绝大部分数据处理都可以归结为一个简单的并行算法：Map and Reduce（http://labs.google.com/papers/mapreduce.html）。这个算法能够在很多种计算中达到相当高的效率，而且是可扩展的（也就是说，一千台机器就算不能达到一千倍的效果，至少也可以达到几百倍的效果）。Map and Reduce的另外一大特色是它可以利用大批廉价的机器组成功能强大的server farm。最后，它的容错性能异常出色，就算一个server farm宕掉一半，整个fram依然能够运行。正是因为这个天才的认识，才有了Map and Reduce算法。借助该算法，Google几乎能无限地增加计算量，与日新月异的互联网应用一同成长。

算法并不局限于计算机和网络

举一个计算机领域外的例子：在高能物理研究方面，很多实验每秒钟都能几个TB的数据量。但因为处理能力和存储能力的不足，科学家不得不把绝大部分未经处理的数据丢弃掉。可大家要知道，新元素的信息很有可能就藏在我们来不及处理的数据里面。同样的，在其他任何领域里，算法可以改变人类的生活。例如人类基因的研究，就可能因为算法而发明新的医疗方式。在国家安全领域，有效的算法可能避免下一个911的发生。在气象方面，算法可以更好地预测未来天灾的发生，以拯救生命。

所以，如果你把计算机的发展放到应用和数据飞速增长的大环境下，你一定会发现；算法的重要性不是在日益减小，而是在日益加强。

给计算机专业的同学学计算机的一些建议

1. 先请你热爱这个专业。只有这样，你才会从抽象的理论中找到实实在在的快乐。如果你不热爱她，或者只因为这是个热门专业，那么极力要求你放弃这个专业，因为计算机是一把双刃剑，学好了你会飞黄腾达，学不好你毕业后会极其痛苦，高不成低不就，没有发展潜力，如同学英语专业的人到了美国一样。

2. 不要用功利眼光对待这个学科，这绝对不是点点鼠标就能挣钱的专业。不要去想做网站挣钱，不要想*点击率增加广告，这个在4年前已经过时，如果你现在仍然这么想，千万别说出来，因为我会觉得你很土。计算级专业的成就感总是伴随着身体上的痛苦而来，肩周炎，颈椎病，眼睛干涩，掉头发，腰椎间盘突出，关节炎，不夸张，这么帅的我工作了两个月以后发现开始掉头发了。

3.搞明白计算机“科学”与“技术”的含义。做网页，做图片，做flash，玩游戏，上网，听歌，录mp3,搞电影字幕，装windows,改注册表，为软件皮肤……这通通不叫计算机科学与技术，如果你是计算机的学生，会做以上事情，那是你应该的，不会做，也没什么丢人的，我们需要的不是让别人称作“高手”。

4.明确你最终的专业方向是软件还是硬件。方向是网络？网络不是专业方向。网络是最优秀的软件工程师、最优秀的硬件工程师与最优秀的通信工程师的智慧结晶。如果你是软件方向，请你在学精一揽子数学、数据结构、算法设计、数值分析、汇编语言、操作系统、编译原理、数据库原理、软件工程之类课程后，仔细的听一听硬件课程，他对你有用。软件工程绝对不是背背就能过的课，计算机理论可能是一个人就能研究出来，软件工程是成千万网软件工程师几十年来失败的教训凝结成的结晶，请认真听课。不要问我应该学什么语言，计算级专业的人必须具备任何语言1小时上手的能力，最起码要在10分钟把”hello world” 做出来。如果说有必须学的两种语言，那他们是c++与java,学他们不是在学语言，而是在学thinking in c++, thinging in java，一个是软件的基础理论，一个是面向对象的基础理论，从来没有人听说过“thinking in basic”。如果你说c++过时了，那么千万别告诉别人你的名字，因为很丢人。山科大的老师只会教给你c，不会教给你++，所以不要被他蒙蔽，大胆的问他++，如果他不会，干脆换老师。学硬件的同学在认真听听以上课程后，学精除了政治以外的其他课程。

5.即使你学好了以上课程，我们仍然差得很远，我们只弄清学什么了，但是还不知道做什么。我们的课程设计太小儿科了，别对你在国外的同学说，否则会被笑话，所以我们要尽可能的多做设计，别一个人们闷着头做，两三个人合作一个项目，不会交流的计算机人员30岁以后肯定会下岗。题目呢，尽量是一些简单的底层开发，可以去国外大学网站上搜一搜，要自信你一定能做出来，毕竟不是什么难题，而是我们应当具备的素质。

6.如果你对网络有意，在具备了一定动手能力后从协议或者底层硬件的角度去学习它。否则你是自甘从一名高贵的计算机专业人员堕落为做着沉重机械体力劳动的民工。对网络安全感兴趣，那么你就在学会使用各种工具的一个月后从编程的角度深入学习网络协议和操作系统吧！只会用工具攻击无知人员的漏洞是一种意*的行为，如果乐此不疲，并到处叫嚷“黑客”，那么这种行为可以被称作“手*”。网上呼吁中美、中日黑客战时，希望你安心学习课程，或者睡觉休息，或者去运动娱乐，不要给祖国抹黑。

7.正确对待认证。绝大部分认证不是高薪的敲门砖，而是你上岗前的智商水平测试。如果你考过了认证，别对别人说这个认证是垃圾，请告诉别人你在学习中懂得了那些知识，如果你没有懂得知识，那么你是个paper，认证不是垃圾，你是垃圾。如果你连认证都没考就到处喊它垃圾，那么你就亲自考考试试，考过了，懂了，那么你随便；如果过了但是不懂，认证不是垃圾你是垃圾，如果没考过，那么看这个贴子的所有人都知道你是什么了。 mcse、ccna、ciw等等都有它存在的意义，只要你有钱都值得一学，他们是最正规的知识来源，是经过理论、实践、时间与市场考验的产品。