Book note:《黑客与画家》

保罗·格雷厄姆有一套完整的创业哲学,他的创业公式是:

1.搭建原型

2.上线运营

3.收集反馈

4.调整产品

5.成长壮大

他认为一定要特别关注用户需要什么,这样才有办法将一个坏项目转变成好项目。他说:”许多伟大的公司,一开始的时候做的都是与后来业务完全不同的事情。乔布斯创建苹果公司后的第一个计划是出售计算机零件,然后让用户自己组装,后来才变成开发苹果电脑。你需要倾听用户的声音,琢磨他们需要什么,然后就去做。”

创始人本身比他的创意更重要。

作者目的:通过这本书让普通读者理解我们所处的这个计算机时代。

作者试图从许许多多不同的方面解释这个时代的内在脉络,揭示它的发展轨迹,帮助你看清我们现在的位置和将来的方向。

想把握这个时代,就必须理解计算机。理解计算机的关键,则是要理解计算机背后的人。

我们的时代是程序员主导的时代,而伟大的程序员就是黑客。

根据理查德·斯托尔曼的说法,黑客行为必须包含三个特点:好玩、高智商、探索精神。 黑客价值观的核心原则可以概括成这样几点:分享、开放、民主、计算机的自由使用、进步。

《黑客与画家》这个书名就是在提示应该把黑客与画家当做同一种人看待。和画家一样,黑客只是怀有一门特殊手艺、有创造天赋的普通人。这个书名还有另外一层含义,即编程时一种艺术创作,黑客就是艺术家,开发软件与画家作画、雕塑家雕刻、建筑师设计房屋并没有本质不同。 1.为什么书呆子不受欢迎

校园生活的真正问题是空虚。

学校是一个很奇怪的、人为设计出来的体系,一半像是无菌室,一般像是野蛮洪荒之地。

2.黑客与画家

黑客与画家的共同之处,在于他们都是创作者。与作曲家、建筑师、作家一样,黑客和画家都是试图创作出优秀的作品。他们本质上都不是在做研究,虽然在创作过程中,他们可能会发现一些新技术。

创造优美食物的方式往往不是从头做起,而是在现有成果的基础上做一些小小的调整,或者将已有的观点用比较新的方式组合起来。这种类型的工作很难用研究性的论文表达。 如果黑客认识到自己与其他创作者——比如作家和画家——是一类人,这种诱惑对他就不起作用。作家和画家没有”对数学的嫉妒”,他们认为自己在从事与数学完全不相关的事情。我认为,黑客也是如此。 黑客如何才能做自己喜欢的事情?我认为这个问题的解决方法是一个几乎所有创作者都知道的方法:找一份养家糊口的”白天工作”。

几乎所有的创作者在职业生涯早期都有一份”白天工作”。 从画家身上,我们还能借鉴到什么对黑客的启示呢?

画家学习绘画的方法主要是动手去画,黑客学习编程的方法也理应如此。

创作者的另一个学习的途径是通过范例。

开源运动最鲜为人知的优点之一,就是使得学习编程变得更容易了。

你不能盼望先有一个完美的规格设计,然后再动手编程,这样想是不现实的。如果你预先承认规格设计是不完美的,在编程的时候,就可以根据需要当场修改规格,最终会有一个更好的结果。 一幅优秀的作品必须比它应该有的样子更好。

坚持一丝不苟,就能取得优秀的成功。因为那些看不见的细节累加起来,就变得可见了。

就像绘画作品一样,大多数软件是为人类用户准备的。所以,黑客必须像画家一样,时刻考虑到用户的人性需要,这样才能做出伟大的产品。

普通黑客和优秀黑客的所有区别之中,会不会”换位思考”可能是最重要的单个因素。

判断一个人是否具备”换位思考”的能力有一个好方法,那就是看他怎样向没有技术背景的人解释技术问题。

“程序写出来是给人看的,附带能在机器上运行。”

——《计算机程序的结构和解释》

3.不能说的话

流行一时的不仅有衣服,还有道德观念。 训练自己去想那些不能想的事情,你获得好处会超过所得到的想法本身。

4.良好的坏习惯

不服从管教,其实是黑客之所以成为优秀程序员的原因之一。

只有深入了解当前的技术,黑客才能构想下一代技术。 公民自由使得国家富强.

如果读美国开国元勋的自述,你会发现他们听起来很像黑客。”反抗政府的精神,”杰弗逊写道,”在某些场合是如此珍贵,我希望它永远保持活跃。”

5.另一条路

我认为,大量的下一代软件都将采用这个模式。甚至最大的输家——微软公司,看来也明白了,部分软件从桌面消失将是不可避免的。如果软件从桌面移到服务器上,一切将发生根本的变化。 互联网软件运行在服务器上,用户界面就是网页。对于普通用户来说,使用这种新型软件将更容易、更便宜、更机动、更可靠,通常也比桌面软件更强大。

如果互联网软件能够击败桌面软件,一定是赢在更方便这一优势上。无论从用户的角度还是从开发者的角度来看都是如此。

用户的胜利

“你的电脑”这个概念正慢慢成为过去时,取而代之的是”你的数据”。

不会有应用软件与操作系统不兼容的问题了。

适用软件将变得非常普遍、容易。

升级不再对用户形成大的冲击。

他们必须正确地设计软件,使得它能够平滑升级,不让使用者感到困惑。

所有用户都是用同样版本的互联网软件,bug一发现就会立刻得到纠正。

适合团队协作性的应用。

数据更安全。

不容易感染病毒。

大多数windows用户使用桌面软件的时候都感到紧张,会有相当大的心理压力,释放这种压力,对你的产品将是一种巨大的推动。

代码之城

设计桌面软件就像设计一幢大楼,而设计互联网软件就像设计一座城市。

软件、硬件。

硬件需要考虑的地方,不仅仅在于怎么才能避免出现问题,还在于怎样才能最大地发挥它们 的作用。

1995年我们创立viaweb的时候,Java applet被认为是互联网软件的解决方案,。但是我们觉得,applet采用的还是过时的概念,它还是要求下载软件到客户端运行。

不同的语言适合不同的任务,你应该根据不通过场合,挑选最合适的工具。如果你不利用语言的优势,那就会听人对手超过你。

软件的发布

互联网软件带来的最大变化之一,就是软件发布方式的改变。

软件的发布可以分解为一系列的渐进式修改,而不是猛地退出一个大幅变动的版本。

软件bug

有一种编程方法叫做”函数式编程”(functional programming),对于互联网软件很有用,很难用纯粹的”函数式编程”完成整个程序,但是它可以用来编写一些重要的部分使得这些部分易于调试,因为他们不包含”状态”,非常便于不断对代码进行小幅的修改和调试。

实现某个构思,会带来更多的构思。所以,将一个构思束之高阁,不仅意味着延迟它的实现,还意味着延迟所有在是实现过程中激发的构思。

要让软件变得可靠,关键是你要全神贯注,而不是开发得很慢。

效率对互联网软件至关重要。

如果软件效率足够高,每个用户的硬件成本现在可以接近免费。

如果新事物真的有重大改进,那么它总是可以找到生存空间的。

你完全能够在只有三个人的情况下让产品开始运营。

桌面软件迫使用户变成系统管理员,互联网软件则是迫使程序员变成系统管理员:用户的压力变小了,程序员的压力变大了。

由于互联网软件的程序员非常辛苦,所以会使得经济优势根本性地从大公司向创业公司转移。互联网软件要求的那种工作强度和付出,只有当公司是其本人所有时,程序员才愿意提供。

因为互联网软件的创业不需要太多的资本,所以大公司可以与创业公司竞争的优势就所剩无几了。

互联网做起来很辛苦,还有许多特别大的压力,但是它们的唯一作用,就是使得创业公司成功的机会变大。

为什么不尝试一下?

如果你是一个黑客,并且梦想自己创业,可能会有两件事情令你望而却步,不敢真正开始采取行动。一件是你不懂得管理企业,另一件是你害怕竞争。可是实际上,这两件事都没有通电的篱笆。

首先,管理企业其实很简单,只要记住两点就可以了:做出用户喜欢的产品,保证开支小于收入。

开支:勤俭节约;编写一个互联网软件是非常便宜的。

如何做出用户喜欢的产品

从制造简洁的产品开始着手,首先要保证你自己愿意使用。然后,迅速地做出1.0版,并且不断加以改进,整个过程中密切倾听用户的反馈。

无论何时,你都要使用自己的软件。

不要只因为对方的头衔是市场专家、设计师或产品经理,就盲目听从他们的话。如果他们的观点真的很好,那就听从他们,关键是你要自己判断,不要盲从。只有懂得设计的黑客,才能设计软件,不能交给对软件一知半解的设计师。

如果你不打算自己动手设计和开发,那就不要创业。

其次,竞争。大公司害怕你胜过你害怕他们。

6.如何创造财富

如果你想致富,应该怎么做?我认为最好的办法就是自己创业,或者加入创业公司。

如果你想赚100万美元,就不得不忍受相当于100万美元的痛苦。

任何公司的成功历程中,运气都是一个很大的随机因素。

通过创造有价值的东西而致富,这种方法的优势不仅仅在于它是合法的,还在于它更简单。

财富和金钱并不是同义词。财富才是你的目标,金钱不是。

人们觉得做生意就是为了挣钱,但是金钱其实只是一种中介,让大家可以更方便地获得自己想要的东西。大多数生意的目的是为了创造财富,做出人们真正想要的东西。

人们需要的东西就是财富。

公司就是许多人聚在一起创造财富的地方,能够制造更多人们需要的东西。

我们这个世界,你向下沉沦或者向上奋进都取决于你自己,不能把原因推给外界。 “你需要去做一些人们需要的东西”。即使不加入公司,你也能做到。真正重要的是做出人们需要的东四,而不是加入某个公司。

工作就是在一个组织中,与许多人共同合作,做出某种人们需要的东西。

可测量性和可放大性

要致富,你需要两样东西:可测量性和可放大性。

业绩可以测量;你做出的决定能够产生巨大的效应。

如果你有一个令你感到安全的工作,你是不会致富的,因为没有危险,就几等于没有可放大性。

如果你想同时具备可测量性和可放大性,不一定非当上CEO或电影明星不可。你只需要成为某个攻克难题的小团体的一部分就可以了。

小团体=可测量性

这就是创业公司的真正意义。理想情况下,你与其他愿意更努力工作的人一起组成一个团队,共同谋取更高的回报。 创业公司的成败取决于最早加入公司的那十个人。(乔布斯)

我们不需要小村庄的那种”小”,而需要全明星第一阵容的那种”小”。

高科技=可放大性

什么是技术?技术就是某种手段,就是我们做事的方式。

如果你解决了一个热门的技术问题,别人都会使用你的解决方案。这就是可放大性。 创业公司如同蚊子,往往只有两种结局,要么赢得一切,要么彻底消失。你通常不知道自己会是哪一个结局,只有等到最后一刻才会明了。

你开办创业公司不是单纯地为了解决问题,而是为了解决那些用户关系的问题。

你必须时刻牢记的最基本的原则就是,创造人们需要的东西,也就是创造财富。如果你想通过创造财富使得自己致富,那么你必须知道人们需要什么。

财富和权力

没有财富的激励,技术革新就会逐渐停顿。 为什么欧洲在历史上变得如此强大:可能是因为允许赚到大钱的人保住自己的财富。 要鼓励大家去创业。只要懂得藏富于民,国家就会变得强大。让书呆子保住他们的血汗钱,你就会无敌于天下。

7.关注贫富分化 8.防止垃圾邮件的一种方法

9.设计者的品位

如果你是一个设计师,并且你不承认有一种人们共同认可的东西叫做”美”,那么你就没有办法做好工作。如果品位只是一种个人偏好,那么每个人都是完美无缺的:你喜欢自己看上的东西,那就足够了。

众多不同学科对”美”的认识有着惊人的相似度。优秀设计的原则是许多学科的共同原则,一再反复地出现。 好设计是简单的设计。

有人会说,简单就是事物本来的样子,装饰反而意味着更多的工作。但是,当人们自己从事创造性工作的时候,好像就会忘了保持简单这个原则。刚开始写作的人喜欢用浮夸的语调,

根本不像他们平时说话的样子。设计师喜欢用波浪式卷曲表现他们的艺术感。画家发现自己都是表现主义者。这些装饰都是花架子,在作家的长句、画家”表现主义”的画笔之下,根本就是空洞无物,表面的掩饰掩盖了内部的空虚,太可怕了。

当你被迫把东西做的简单时,你就被迫直接面对真正的问题。当你不能用表面的装饰交差时,你就不得不做好真正的本质部分。 好设计是永不过时的设计。

说来奇怪,如果你希望自己的作品对未来的人们有吸引力,方法之一就是让你的作品对上几代人有吸引力。

好设计是解决主要问题的设计。

eg:厨房的煤气灶,四个出火口和调节器的位置摆放。

eg:字体的设计。 好设计是启发性的设计。

eg:英国女作家简奥斯丁的作品:几乎不带有任何描述。

eg:《蒙娜丽莎》:启发式的绘画

一个建筑或一个物品应该允许你按照自己的愿望来使用。

你应该为用户提供一些基本模块,使得他们可以随心所欲自由组合,就像玩乐高积木那样。

好设计通常是有点趣味性的设计。

这是因为幽默一定程度上反映了力量。幽默感是强壮的一种表现,始终拥有幽默感就代表你对厄运一笑了之,而丧失幽默感则表示你被厄运深深伤到。所以,强壮的标志(或者至少是特点)就是轻松面对自己的人生。充满自信的人常常像燕子一样,以一种居高临下的姿态轻盈的看待周围的一切,比如希区柯克拍摄的电影、16世纪画家布勒哲的绘画(甚至莎士比亚也是一个这方面的例子)。

好设计是艰苦的设计。

如果观察那些做出伟大作品的人,你会发现他们的共同点就是工作得非常艰苦。如果你工作得不艰苦,你可能正在浪费时间。

功能决定形式:如果开发”功能”非常艰难,那么”形式”将不得不全部都由”功能”决定,因为没有多余的精力再来单独开发”形式”了。

好设计是看似容易的设计。

作家的文章看起来流畅自如,但是背后其实经过了反复修改。

科学和工程学的一些最重大的发现在形式上往往很简单,会使得你觉得自己也想到过。

在大多数领域,看上去容易的事,背后都需要大量的练习。练习的作用也许是训练你把可以为之的事情变成一种自觉的行为。

好设计是对称的设计 好设计是模仿大自然的设计。

模仿与剽窃并不相同。

好设计是一种再设计。

很少有人一次就把事情做对。专家的做法是先完成一个早期原型,然后提出修改计划,最后把早期原型扔掉。

你应该培养对自己的不满。达芬奇为了把一根线画对,经常要画五六次。

犯错误是很正常的事情。你不要把犯错误看成灾难,要用于承认、用于改正。开源软件因为公开承认自己会有bug,反而使得代码的bug比较少。 好设计是能够复制的设计。

把事情做对比原创更重要。

等你逐渐对一件事产生热情的时候,就不会满足于模仿了。你的品位就进入了第二阶段,开始自觉地进行原创。

我想,最伟大的大师最终会达到一种超脱自我的境界。他们一心想找到正确答案,如果别人已经回答了一部分,那就没理由不拿来用。他们足够自信地使用他人的成功,完全不担心因此丧失个人的特点。 好设计常常是奇怪的设计。

eg:Lisp,黑鸟超音速侦察机;《雪中猎人》

eg:爱因斯坦并不像让相对论变得很奇特,他只想找出真理,是真理本身显得很奇特。

唯一达到”奇特”的方法,就是追求做出好作品,完成之后再回过头看。 好设计师成批出现的。

eg:15世纪的弗洛伦萨涌现一大批伟大艺术家。

推动人才成批涌现的最大因素就是,让有天赋的人聚在一起,共同解决某个难题。互相激励比天赋更重要。

在历史上的任何时刻都有一些热点项目,一些团体在这些项目上做出伟大的成绩。如果你原理这些中心,几乎不可能单靠自己就取得伟大成果。

好设计常常是大胆的设计。

在任何一段历史中,人们都会把有些荒谬的东西当做正确的,并且深信不疑,以至于一旦你出言质疑,就有被排挤或者被暴力伤害的危险。

今天的实验性错误就是明天的新理论。如果你想做出伟大的新成果,那就不能对常会与真理不相吻合之处视而不见,反而应该特别注意才对。

大多数做出优美成果的人好像只是为了修正他们眼中丑陋的东西。伟大成果的出现常常来源于某人看到一样东西后,心想我能做的比这更好。

单单是无法容忍丑陋的东西还不够,只有对这个领域非常熟悉,你才可能发现哪些地方可以动手改进。你必须锻炼自己。只有在成为某个领域的专家之后,你才会听到心里有一个细微的声音说:”这样解决太糟糕了!一定有更好的选择。”不要忽视这种声音,要培育它们。优秀作品的秘诀就是:非常严格的品位,再加上实现这种品位的能力。

10.编程语言解析

开放源码的优势还不仅局限于可以总计动手解决bug。这里的关键是所有人都可以参与。所以,开源软件就像一篇经受同行评议的论文。 语言之间确实有差别,但是很难确定地说哪一种语言是最好的。 如果你非常关注运行速度,那么最好使用接近机器的语言。大多数操作系统都是用C语言写的,这并非偶然。

11.一百年后的编程语言

一种语言的内核设计得越小、越干净,它的生命力就越顽强。

编程语言进化缓慢的原因在于它们并不是真正的技术。

编程语言的进化速度更像是数学符号的进化速度,而不像是真正的技术(比如交通或通信技术)的进化速度。

浪费可以分成好的浪费和坏的浪费。我所感兴趣的是好的浪费,即用更多的钱得到更简单的设计。

essay(论文)这个词来自法语的动词essayer,意思是”试试看”。从这个意义上来说,论文就是你写一篇文章,试着搞清楚某件事。软件也是如此。 我们的思想可能往往会受限于某种现存的语言,只采用在这种语言看来更简单的形式,它对我们思想的束缚作用会大得令人震惊。新语言必须靠你自己去发现,不能依靠那些让你自然而然就沉下去的思维定势。 12.拒绝平庸

Lisp很值得学习。你掌握它以后,会感到它给你带来的极大的启发。这会大大提高你的编程水平,使你成为一个更好的程序员。尽管在实际工作中极少会用到Lisp。 13.书呆子的复仇 14.梦寐以求的编程语言

15.设计与研究

用户需要的设计,而不是用户要求的设计。

艺术的各个领域有着巨大的差别,但是我觉得任何一个领域的最佳作品都不能由对用户言听计从的人做出来。

让用户满意并不等于迎合用户的一切要求。用户不了解所有可能的选择,也经常弄错自己真正想要的东西。

除非设定目标用户,否则一种设计的好坏根本无从谈起。

如果目标用户群体涵盖了设计师本身,那么最有可能诞生优秀设计。 先做出原型,再逐步加工做出成品,这种方式有利于鼓舞士气,因为它使得你随时都可以看到工作的成效。

Published: 25 Dec 2011

一升庵经营之道

作为吃货一枚,对和饮食有关的影视作品有爱应该是很好理解的。在家看电视时,有些美食节目也会让我停下飞快换频道的手指。

看完《深夜食堂》后继续寻找,找到的第二部以食物为主题的剧集是同样来自日本的《料理仙姬》。故事并不复杂,讲述坚持传统的日本料理店一升庵里的大小事情,每集一个主题。抱着娱乐的心态来看,却从料理店的年轻老板娘半田仙(苍井优饰演)身上学到一些为人处事的道理:

1.让对方吃到美好食物的心情最重要。

这部剧给我留下最深印象的不是具体烹制食物的技法,而是工作反映出的态度。阿仙制作料理时自然发出的微笑以及对食物喃喃说出的”变得更好吃啊”,透露出她对料理制作的热爱。她几次提到,让对方吃到美好食物的心情是最重要的,这话语里是爱人之心。出于爱,还是利润,还是炫技,效果会不同,因为这背后反映出不同的动机:为己还是为人。

2.对专业极致、完美的追求。

这其实是个老话题了,日本是个特别善于在某种技艺上极致追求并且取得巨大成就的国家,令人尊敬。茶道、剑道、插花等早已是日本文化象征,本剧中同样表现了这种文化:做味增时一粒粒的挑选黄豆,切食材时刀法一丝不苟,修缮房屋的木工世代传承……我从他们身上看到了敬业和对职业的自豪感。

3.对标准的严格要求,不妥协。

极致的追求有时也会遇到现实的困难:从来都用稻草烧的米饭遇到了稻草耗尽的局面,是用柴应付过去、反正差别不大,还是坚持品质?

阿仙选择了坚持,因为一次放松就无法挽回。

4.人情练达。

一家成功的料理店不是有了好食物就能开起来的,会遇到形形色色的困难,也要和方方面面打交道。

给一升庵提供稻米原料的店铺两代老板父子间略有隔阂,随着年老父亲的身体衰弱,继承家业的儿子不再像以往一样供给最好的稻米,一升庵面临食材品质降低的风险。阿仙给稻米店送去精心制作的饭团,在稻米的香味中,父子间多了理解,原料危机也化于无形。

貌似粗鲁的卡车司机们来到店里大吃大喝,让人皱眉,可是善良的半田仙仍然尽力款待,没有区别心。正是这些无意交来的朋友,在一升庵的原料危机中帮忙运输,拯救了困局。

5.关注细节。

阿仙为前来赴宴的相亲对象定制了合适手型的筷子,而对方的手型只是在偶然一次握手时感知到的。这让男方感动不已,并且意识到自己和半田仙不在同一水平线上,甘愿退出继续磨练自我。(但是,阿仙需要的真的是同一境界的男人吗?还是一个满足她像普通女孩一样去吃汉堡愿望的、关心她的男人?)

6.团队管理。

团队成员关系的协调。店里的学徒小留为了炫技擅自在外做菜,违反了店规,大师傅清二要开除小留,而小留工作一直没有问题,罪不至此,拥有决定权的半田仙在两难中会怎样做呢?出人意料,他同意了表面提出请辞其实希望留下的小留辞职。经过几个月的反省,小留在阿仙的帮助下领悟了给对方提供美好食物不应炫技的道理,并用已经提高的厨艺在清师傅前证明了自己。此时,阿仙才正式向清师傅提出请求,接受小留回归。遵循了原则,化解了矛盾,维护了团结,并解决问题,真是智慧地处理。

团队激励:负责烧制米饭的小晴一直认真工作,但面对往昔同窗的质疑,开始怀疑自己的价值。阿仙请小晴给稻米店送去米饭制成的饭团,使她从稻米店老板对饭团的称赞与感动中体会工作的价值。阿仙拜托小晴的话语十分恳切:”小晴,以后还要拜托你煮出美味的米饭啊,不管谁说什么,一升庵不能没有小晴,因为你是煮饭名人。”真诚地赞美,让团队成员明白自己的重要性。

在追求快捷、效率成为时代主题时,一升庵显得那么固执。这是半田仙的选择:不是被时代留在原地,而是选择不变。单纯无邪的笑容下是真正的大智若愚。

Published: 11 Dec 2011

用Lucene模糊搜索和ExtJs ComboBox实现搜索建议词效果

在搜索引擎输入框中输入搜索词时,会实时得到搜索建议:

这些建议词是从搜索引擎的搜索记录中按照一定算法挖掘出的高关联度短语。如果没有搜索记录,能不能实现相关搜索建议呢?本文介绍一个简单的处理方法,下面将分别说明如何得到相关建议词和前端的实现方式。

1.相关词语的获取

最直观的相关词语是:两个词语(短语)之间具有一部分相同字,另一部分不同,它们之间相同的部分所占比例越高,则两个词语越相关。例如,在这种情况下”计算机”和”计算器”是相关的,”计算机”和”计算机网络”是相关的。如果有一个词典包含足够的词语,并且支持这种模糊的词语匹配方式,就可以实现词语建议。

Lucene专门提供了模糊查询FuzzyQuery实现上述功能[1]。它采用编辑距离算法计算两个字符串之间的相似度,编辑距离用来计算从一个字符串转换到另一个字符串所需的最少插入、删除和替换的字母个数。例如,”three“和”tree“之间的编辑距离为1。使用FuzzyQuery查询时,和查询词距离越小的词评分越高,在结果中排名越高。这样就可以通过模糊搜索获得词库中最相近的词语。

实际操作中,建立Lucene索引时每个document的索引域中只索引一个词,这样从返回的结果文档中可以直接取出该域中的词语。

《Lucene实战》中给出了下面的代码展示FuzzyQuery的用法:

[code lang=”java”] public void testFuzzy() throws Exception { indexSingleFieldDocs(new Field[] { new Field("contents", "fuzzy", Field.Store.YES, Field.Index.ANALYZED), new Field("contents", "wuzzy", Field.Store.YES, Field.Index.ANALYZED) });

IndexSearcher searcher = new IndexSearcher(directory);
Query query = new FuzzyQuery(new Term("contents", "wuzza"));
TopDocs matches = searcher.search(query, 10);
assertEquals("both close enough", 2, matches.totalHits);

assertTrue("wuzzy closer than fuzzy",
           matches.scoreDocs[0].score != matches.scoreDocs[1].score);

Document doc = searcher.doc(matches.scoreDocs[0].doc);
assertEquals("wuzza bear", "wuzzy", doc.get("contents"));
searcher.close();

}[/code]

虽然模糊搜索相比分析搜索log不够智能、缺乏时效性,但是在面向特定领域、有现成领域词典的情况下,这种方式简单而有效。例如,对专利领域,国际专利分类(IPC)的官方文件对整个技术领域做了全面的分类描述,里面出现的词语对专利方面的应用做输入建议会有不错的效果。

2.前端效果实现

ExtJs中的下拉选择框组件ComboBox可以实现输入时动态更新推荐词语列表的效果。

ComboBox的输入框右侧有一个下拉箭头(见下图),可以修改配置项使其不显示,模拟输入框的效果。

一个配置示例如下所示,几个关键的配置项做了注释:

[code lang=”javascript”] var suggestionCombo = new Ext.form.ComboBox({ hiddenName : ‘cname’, fieldLabel : ‘名称’, triggerAction : ‘all’, store : suggestionCombostore, displayField : ‘text’, mode : ‘local’, forceSelection : false, minListWidth : 270, resizable : true, allowBlank : false, editable : true, //允许输入 enableKeyEvents:true, //允许键盘输入事件 hideTrigger: true, //隐藏下拉箭头 anchor : ‘100%’ }); [/code]

为了根据用户输入动态更新列表内容,需要监听键盘输入事件,在每次输入一个字时发送当前输入内容到后端,后端获取相关词语后返回前端,重新展示。事件处理部分的代码为:

[code lang=”javascript”]suggestionCombo.on(‘keyup’,function(textField,e){ //如果键盘输入不是方向键,则更新列表 if(!e.isNavKeyPress()){ textField.getStore().load({params:{inputText:textField.getRawValue()}}); } }); [/code]

上面的textField.getRawValue()即获取当前的输入文本内容,用于后台查询建议词。

最终实现的效果如下图所示:

如果能完善索引的领域词库,改善中文分词效果,可以得到更好的搜索建议词列表。

参考文献

[1] 《Lucene实战》(第二版),P94

[2] extjs google suggest效果, http://wodar.iteye.com/blog/553067

[3] Ext.form.ComboBox实现google Suggestion效果, http://love4j.iteye.com/blog/516399

Published: 19 Nov 2011

ExtJS TreeGrid叶子节点拖拽问题和选择框使用方法

最近一直参与开发一个实验室项目,接触到了ExtJs。下面是工程中几个小问题的总结。

1.TreeGrid的叶子节点拖拽问题

我使用的是ExtJs3.1版本。ExtJs中默认在树(Ext.tree.TreePanel)的拖动中,一个节点是不能拖动到一个叶子节点中的。这样的设计有些武断,因为根据应用环境叶子节点是有可能变为父节点的。事件机制给这个问题带来了解决方案,许多地方都提到了在监听TreePanel的”nodedragover”事件时特殊处理使得叶子节点可以被drop。代码为:

[code lang=”javascript”]tree.on("nodedragover", function(e){ var n = e.target; if (n.leaf) { n.leaf = false; } return true; }); [/code]

最后的返回值设为true使得目标叶子节点接受拖动的节点。

在使用TreeGrid(Ext.ux.tree.TreeGrid)时,同样面临上面的问题。采取同样的处理方式,尽管TreeGrid是继承自TreePanel,却仍不能使叶子节点被drop:

在上面的事件处理函数中加打印语句,发现在TreeGrid有叶子节点被drop时,nodedragover事件根本就没有被触发。

试着调试一下,把页面引入的ext-all.js换成ext-all-debug.js,从触发nodedragover的地方入手逐渐分析,最终发现当TreePanel的拖拽配置为dropConfig: {appendOnly:true}时,nodedragover是不会触发的。这里TreePanel和TreeGrid的区别是,TreePanel如果不设置dropConfig属性,默认appendOnly是false;而TreeGrid如果不设置dropConfig属性,默认appendOnly是true。所以同样的处理到了TreeGrid这里就无效了。

明白了原因,只需要在TreeGrid的配置项里增加:dropConfig: {appendOnly:false}和上面的nodedragover事件处理函数就能实现TreeGrid的叶子节点drop问题,效果如下:

2.TreeGrid中增加选择框(checkBox)效果

TreePanel没有直接提供checkBox的配置项,官方例子中的处理完全可以用在TreeGrid上,见/examples/tree/check-tree.html,主要是在数据中增加”checked: false”字段,然后用treeGrid.getChecked()方法获得当前选中的所有节点。效果如下:

小结:初步尝试了前端开发动作,感觉设计某项功能具体的实现方式、界面的样式特别是交互方式,是很有乐趣的工作。

Published: 09 Nov 2011

浪潮与基因——读《浪潮之巅》

十一期间读了期待已久的《浪潮之巅》,这是一本阅读体验非常好的书。书中回顾百年来辉煌过的科技公司巨头并且梳理了IT行业的发展规律,很容易让人联想到那部回顾大国兴衰的纪录片——《大国崛起》。

这本书的主要观点有两点,一是势,也就是标题中的”浪潮”一词。二是公司基因论,即一家公司的发展命运很大程度上取决于它的基因。

关于浪潮的重要性书中已经充分论证——赶上了一波大潮足以保证一家公司在几十年的时间顺流前进。但我想,把握机遇的能力也很关键:在《硅谷传奇》中,比尔盖茨联系为Altair 8800提供Basic解释器,但当时已经有50家公司参与竞争。而《Facebook效应》中,扎克伯格在做Facebook网站前已经积累了软件开发、社交网站建设的经验,并且总是在思考、讨论可以用网络提供什么样的服务。没有做好准备,机会来临了也只能看着它溜走。

当然,从历史的角度看,强调机遇的重要性是从更高远的角度出发的。对已经同样优秀的参赛者来说,机遇远胜过实力的微小差别。

本书令人印象深刻的一点是作者展现出了非常宽广的视野、丰富的知识背景、深厚的人文素养和对技术的深刻理解,这些都是和作者自身的工作背景分不开的,我想这也是本书之所以优秀的”基因”吧。总体而言,这是一本值得反复读的好书。

Published: 20 Oct 2011

Book note:《浪潮之巅》

近一百多年来,总有一些公司很幸运地、有意识或者无意识地站在技术革命的浪尖之上。一旦处在了那个位置,即使不做任何事,也可以随着波浪顺顺当当地向前漂个十年甚至更长的时间。在这十几年间,它们代表着科技的浪潮,直到下一波浪潮的来临。

对于一个弄潮的年轻人来讲,最幸运的莫过于赶上一波大潮。

第1章 AT&T公司

1877年由电话之父亚历山大·贝尔建立,最初叫贝尔电话公司。电话的发明和AT&T的建立,第一次实现了人类远程实时的交互通信。

1925年建立贝尔实验室——历史上最大最成功的私有实验室。

1984年根据反垄断法的要求,AT&T的市话业务分出去划分成7个小的贝尔公司。贝尔电话公司更名为AT&T公司。

1995年是AT&T公司的顶峰,接下来的10年,它便分崩离析不复存在了。

为了将电话设备卖给竞争对手,公司决定将设备制造部门拆分出去,使股票飞涨获取利益。利令智昏,杀鸡取卵。

1996年,AT&T拆分为AT&T(从事电信服务业务),朗讯(从事设备制造)和NCR。

贝尔实验室失去AT&T这个靠山,经费不足,再也没有搞出轰动世界的发明。AT&T的电信服务与设备制造相辅相成的局面被打破,开始衰落。

由于移动通信业务的兴起,朗讯日渐衰落,竟然在2000年将无线设备分出去单独上市。朗讯最终被阿尔卡特并购。

AT&T在朗讯第二次拆分的同时,决定一分为四,原因只有一个词——贪婪。

2000年前后,正是全球从传统电话到移动电话普及的关键时期。但是分家之后的AT&T,长途电话公司和移动电话公司都是残缺的公司,前者没有发展的潜力,后者没有资金扩张,形成双输局面。

互联网的兴起对电话公司造成冲击。

2004年,AT&T被西南贝尔公司兼并。

在工业史上,新技术代替就技术是不以人的意志为转移的。

当一家公司没有人对他有控制权时,它的发展就会有问题。

第2章 IBM

IBM能成为科技界的常青树,要归功于它的二字秘诀——保守。

1924年,IBM由老托马斯·沃森创建,经营用于管理的机械。从那时起,IBM就锁定了政府部门和企事业单位为它的主要客户。

1954年,小沃森接任总裁,IBM开始领导电子技术革命的浪潮。小沃森对世界最大的贡献是将计算机从政府部门和军方推广到民间,将它的功能由科学计算变成商用。

1976 年可以作为把计算机工业历史的一个分水岭。这一年,没有读完大学的天才史蒂夫·乔布斯(Steve Jobs)在车库里整出了世界上第一台可以商业化的个人电脑Apple-I。

对于个人电脑,IBM 观望了几年。这对 IBM 这样一个大公司来讲是非常有必要的。IBM 成功的秘诀是保守,它基本上是不见兔子不撒鹰。如果苹果公司失败了, IBM 不需要做任何事情。如果前者成功了,IBM 依靠它强大的技术储备完全可以后发制人。

1981年,IBM-PC诞生,在同苹果的竞争中后发制人。

个人电脑时代的最终领导者是微软和英特尔,而不是 IBM。随着 2005 年 IBM 将个人电脑部门卖给了中国的联想公司,IBM 彻底退出了个人电脑的舞台。造成这个结果最主要的原因有三个:IBM 的基因,反垄断的后遗症以及微软的崛起。

1993年,郭士纳上台,危机四伏的IBM开始改革。目的——打造一只 IT 服务业的航空母舰。最终开创了IBM10年黄金时代。

2005年,IBM将PC部门卖给联想,退出PC市场。

第3章 苹果公司

1976年,20的乔布斯和史蒂夫·沃兹尼克及罗恩·韦恩在车库里创办苹果公司。研制出世界上第一台通用的个人电脑——Apple-I,大大降低的成本使老百姓花几百美元就可以买到。

1984年,第二代苹果机麦金托什诞生,这是世界上第一种可以买得到的、拥有交互式图形界面并且使用鼠标的个人电脑。取得商业和技术上的巨大成功。走封闭技术路线的苹果,没有兼容机的帮助无法挑战微软。

1985年,30岁的乔布斯在和斯卡利的斗争中被踢出自己创建的公司。创立NeXT公司,收购卢卡斯的动画工作室,重构成Pixar公司。

斯卡利当政后期,麦金托什的市场占有率越来越小,摊子越铺越大,开始亏损。

1998年,乔布斯被重新请回苹果。imac诞生,苹果重新盈利。

乔布斯的超人之处在于他善于学习,并且能把的准时代的脉搏。

乔布斯在苹果微机中逐渐采用英特尔的通用处理器,采用Free BSD作为新苹果操作系统的内核,使得大量有兴趣的工程师很容易的为苹果开发软件。至关重要的是如何为苹果找到PC以外的增长点。

2001,iPod诞生,颠覆音乐产业,苹果、乔布斯再现辉煌。

2006年,退出Apple TV,但是失败。乔布斯挺过了最艰难的时候。

2007年,iPhone诞生,颠覆手机产业。

2010年,iPad诞生,成为颠覆PC工业产业生态链(WinTel体系)的重要一环。苹果的市值再次超过微软,成为全球最值钱的IT公司。

苹果把每一款产品做到了极致,这很大程序上是因为乔布斯达到了一个将艺术和技术结合的炉火纯青的境界,这就是创新。

第4章 计算机工业的生态链

1.摩尔定律

每18个月,集成电路的集成度会翻一番。

摩尔定理主导着 IT 行业的发展。首先,为了能使摩尔定理成立,IT 公司必须在比较短的时间内完成下一代产品的开发。这就要求,IT 公司在研发上必须投入大量的资金,这使得每个产品的市场不会有太多的竞争者。

其次,由于有了强有力的硬件支持,以前想都不敢想的应用会不断涌现。

第三,各个公司现在的研发必须针对多年后的市场。

2.安迪-比尔定律

比尔要拿走安迪所给的(What Andy gives, Bill takes away)。

在 IT 领域,各个硬件厂商恰恰是靠软件开发商用光自己提供的硬件资源得以生存。

安迪-比尔定理把原本属于耐用消费品的电脑、手机等商品变成了消耗性商品,刺激着整个 IT 领域的发展。

3.反摩尔定律

如果你反过来看摩尔定理,一个 IT 公司如果今天和十八个月前卖掉同样多的、同样的产品,它的营业额就要降一半。IT 界把它称为反摩尔定理。

反摩尔定理逼着所有的硬件设备公司必须赶上摩尔定理规定的更新速度。,一旦不能做到摩尔定理规定的发展速度,它们的盈利情况就会一落千丈。

反摩尔定理积极的一面更为重要,它促成科技领域质的进步,并为新兴公司提供生存和发展的可能。

在科技进步量变的过程中,新的小公司是无法和老的大公司竞争的,因为后者在老的技术方面有无以伦比的优势。在抓住质变机遇上,有些小公司会做得比大公司更好而后来居上,因为它们没有包袱,也比大公司灵活。这也是硅谷出现了众多的新技术公司的原因。

第5章 英特尔公司

三十多年来,英特尔公司成功的关键首先是搭上了个人电脑革命的浪潮,尤其是有微软这个强势的伙伴;第二,它三十年来严格按照它的创始人预言的惊人的高速度在为全世界 PC 机用户提高着处理器的性能,

1968 年,英特尔公司由戈登•摩尔(Gordon E. Moore)和罗伯特.诺伊斯(Robert Noyce)创立于硅谷。

20世纪80年代,英特尔果断地停掉了它的内存业务,将这个市场完全让给了日本人,从此专心做处理器。

1978年,开发出8086微处理器,成为IBM-PC的CPU。

1985,32位80386问世。

1993,推出奔腾处理器,甩掉了低性能处理器的帽子。

英特尔和摩托罗拉之战:

首先,这是两个不同时代的公司。

第二,两个公司的统帅水平相去甚远。

最后,英特尔比摩托罗拉更专注。

英特尔对世界最大的贡献在于,它证明了处理器公司可以独立于计算机整机公司而存在。

第6章 微软公司

盖茨的天才之处在于,它在微机工业刚刚开始的时候,就意识到只要垄断了操作系统,就间接垄断了整个行业。

1975 微软成立。

1980 为IBM-PC提供操作系统。

1990 推出视窗3.0操作系统,微软帝国开始形成。

1993 推出excel。

1995 Word95问世, IE问世,击垮网景公司。

2000 成为全球市值最高的公司。

用两句话形容微软的兴衰。第一,它兴起于个人微机的浪潮,同时随着这次浪潮已接近尾声,而进入发展的中年期。第二,它过强的桌面软件的基因,使得它无法站到互联网时代的浪潮之巅。

第7章 思科公司

1984 思科成立,标准的斯坦福公司。

持续发展的绝招:支持员工内部创业,思科作为投资者而不是管理者,以后优先购买回来新公司。

1990 上市。

2000 达到高潮,市值一度超过微软。

2001 互联网泡沫破裂,思科业绩下滑,股价下跌80%以上。

2003 在VoIP领域快速发展,重会上升轨迹。

第8章 雅虎公司

杨致远和戴维菲洛最大贡献——制定了互联网这个行业的游戏规则——开放、免费和盈利。

一个产业早期领导者选定的商业模式对这个产业几乎是决定性的。

1995 雅虎成立。

1996 上市

1998 成为世界上最大的互联网公司

2006 被google超越,退居互联网行业第二名,从此一蹶不振。

第9章 惠普公司

1939 惠普公司成立

1966 进入计算机市场,成为IBM以外7家小计算机公司之一。

1999 卡莉·菲奥莉娜成为惠普第一位女性CEO;制造仪器部门剥离上市,成为安捷伦公司

2002 收购常年亏损的康柏公司,成为史上最有争议的收购案。

2005 马克赫德接掌惠普,开创5年高速发展期

惠普是硅谷当年以半导体和计算机硬件为核心时代的代表,但今天半导体已不再重要,它可能成为一颗黯淡了的巨星。

第10章 摩托罗拉公司

1928 摩托罗拉成立

1940 退出报话机

1942 退出手提式对讲机

1967 发明晶体管电视

1979 退出68000处理器,是麦金托什电脑的CPU

1983 推出第一台商用移动电话

1991 推出世界上第一台GSM数字移动电话,启动铱星计划。

1998 被诺基亚在移动电话上超越

1999 铱星计划破产

2003 半导体部门剥离上市

2007 加入Android联盟,手机业务回升

2011 分为摩托罗拉移动和摩托罗拉解决方案两个独立上市公司。

P169”我们一致认为一家公司的基因常常决定它今后的命运”。

(comment:过去成功的经验,很可能成为今后成功的障碍。因为战场变了,思路却没有变,或者根本就是拒绝变化发生。)

摩 托罗拉的基因决定了它在数字移动通信中很难维持它在模拟通信上的市场占有率。一、过早放弃模拟手机,等于放弃已经开采出的金矿;二、模拟手机部门最挣钱所 以嗓门最大,数字手机部门发言权小。三、在模拟通信设备市场,技术至关重要;而数字通信技术差异小,非技术因素重要,在这些方面比不过诺基亚和亚洲公司。

摩托罗拉和At&t的衰落相反,因为由高尔文家族控制,但是他心有余力不足,无力迎接挑战。

第11章 硅谷的另一面

一个小公司要想成功,有很多因素必须同时具备。

首先,创始人很重要。任何梦想家都不足以成事,因为所有的成功者都是实干家。

但是光有好的团体和技术又远远不够,他们有商业头脑而且必须找到一个能盈利的商业模型

再接下来是判断力和执行力。

真正具备这些条件已经很不容易了。而一个初创公司的成功很大程度上还要看外部环境好不好

最后,也是最重要的,创业者必须有好运气。

人和是最重要的,它就是在硅谷发展起来的新型的生产关系。这是硅谷在全世界最特殊的地方,并充分保障了创新。具体讲就是利润的分配方式和人与人的关系。

第12章 与机会失之交臂的公司

太阳公司

Novell公司

网景公司

Real Networks

第13章 风险投资

一个好的创业题目最要紧的是具有新颖性,通常是别人没想到的,而不是别人已经做成功的。

除此之外,一个好的题目还必须具备以下几个条件:

  1. 这个项目一旦做成,要有现成的市场,而且容易横向扩展(Leverage)。

  2. 今后的商业发展在较长时间内会以几何级数增长。

  3. 必须具有革命性。创业必须要有革命性的技术或者革命性的商业模式。

我对风险投资家的敬意远远高于对华尔街,因为风险投资对社会有很大的正面影响,而华尔街经常会起负面作用。

第14章 信息产业的规律性

1.70-20-10 律

信息产业一个领域一般在全球容不下三个以上的主要竞争者。老大占百分之六七十的份额,老二占百分之二三十的份额,老三占百分之十的份额。

  1. 诺威格定理

当一个公司的市场占有率超过 50% 后,就无法再使市场占有率翻番了。

诺威格定理决定了在一个市场占有主导地位的公司必须不断开拓新的财源,才能做到长盛不衰。

3.基因 决定定理

一 个在某个领域特别成功的大公司一定已经被优化得非常适应这个市场,它的文化、做事方式、商业模式、市场定位等等已经非常适应,甚至过分适应自己传统的市 场。这使得该公司获得成功的内在因素会渐渐地、深深地植入该公司,可以讲是这个公司的基因。适应现有市场的基因未必适合一个新的市场。

第15章 斯坦福大学

第16章 投资银行

第17章 Google公司

第18章 成功的转基因:诺基亚、3M、GE公司

第19章 最佳的商业模式

最好的商业模式是印钞机式的,它不需要多少人力,一旦运作起来便能自己产生利润,持续发展。下面三种商业模式算不上好的:1.每增加一份营收就必须多雇佣一个人;2,无法横向拓展的业务;3、需要消耗过多的原料和成本。

第20章 互联网2.0

技术上,没有任何创新;从人们使用互联网的方式上,它确实是一次革命;在商业模式上,它是互联网生态链的一次优化,并且可能带来新的商机。

第21章 金融风暴的冲击

第22章 云计算

云计算是彻头彻尾的革命。

第23章 下一个Google

电子商务

在中国和一些亚洲国家,电子商务的潜力却可以造就出Google这样的大型新型公司。

无线业务

从长远看,基于手机的支付和社区(包括游戏)商业前景非常乐观。

关注亚太地区

Google,亚马逊,Facebook,Twitter, 阿里巴巴,腾讯

当人们不再把房市、股市作为最快的挣钱手段时,就是中国可以诞生下一个Google的时候了。

从经济发展来看,中国诞生许多世界品牌和跨国公司是历史的必然,这个任务将落到年轻人身上。但是,目前最大的障碍是全中国非常缺乏各种顶级的技术人员,因为几乎所有的年轻人工作不了几年都去做管理了。

Published: 08 Oct 2011

排序算法思维导图总结

常用的排序算法包括:

  1. 冒泡排序
  2. 插入排序
  3. 合并排序
  4. 堆排序
  5. 快速排序
  6. 计数排序
  7. 基数排序
  8. 桶排序

下面按照稳定性、复杂度、适用特点进行总结。

稳定性:具有相同值的元素在输出数组中的相对次序没有改变。当卫星数据随被排序的元素一起移动时,稳定性比较重要。

复杂度:时间复杂度和空间复杂度。

适用特点:算法需要根据具体条件进行选择。

1.排序算法分类,稳定性和时空复杂度[1]:

2.适用特点[1-4]:

   

特点

插入排序 直接插入排序 数据基本有序时,可以减少数据交换和移动次数,提高效率
希尔排序 简单,适用于小数据量情况
交换排序 冒泡排序 实际使用中效率较低,对数据有序性非常敏感
快速排序 分治,自顶向下。理论上最好的方法,应用广泛; 如果数据量大而且数据全部放在内存中,那么快速排序是首选的排序方法[4]
选择排序 简单选择排序 对有序性不敏感,交换次数少
堆排序 不需要递归,适合大数据量,可用来实现优先队列
其他排序 合并排序 分治,自底向上。对有序性不敏感,需要辅助空间,不适合大数据量;在处理大量数据的排序时,它不要求被排序的数据全部在内存中,所以在数据大于内存的容纳能力时,合并排序能大显身手。合并排序最常用的地方是数据库管理系统(DBMS)[4]
非基于比较 计数排序 数据范围需要不大
基数排序 关键字需要可分解
桶排序 数据分布均匀
在数据量不大时,所有排序算法性能差别不大。有文章指出,高级排序算法在元素个数多于1000 时,性能才出现显著提升。在90%的情况下,我们存储的元素个数只有几十到上百个而已,比如进程数、窗口个数和配置信息等等的数量都不会很大,冒泡排序其实是更好的选择。[4]

3.算法选择[3]

最后推荐一个网站Sorting Algorithm Animations,这里可以看到各种排序算法在不同数据条件下排序过程的动画演示,非常直观。

参考文献

[1]算法之排序算法,董的博客,http://dongxicheng.org/structure/sort/

[2]八种排序算法总结,http://blog.csdn.net/yfqvip/article/details/3344007

[3] 基本排序算法比较与选择,http://blog.csdn.net/ctang/article/details/37914

[4] 《系统程序员成长计划》

Published: 25 Sep 2011

中位数和顺序统计学

在一个由n个元素组成的集合中,第i个顺序统计量是该集合中第i小的元素。

一个中位数是它所在集合的"中点元素"。当n为奇数,中位数出现在i=(n+1)/2处;当n为偶数,存在两个中位数,i=n/2和i=n/2+1。如果不考虑奇偶性,中位数出现在$$\lfloor(n+1)/2\rfloor$$处(下中位数)和$$\lceil(n+1)/2\rceil$$处(上中位数)。

形式化地定义选择问题:

输入:一个包含n个(不同的)数的集合A和一个数i,$$1\le i\le n$$。

输出:元素$$x\in A$$,它恰大于A中其他的i-1个元素。

最小值和最大值

在一个有n个元素的集合中,要通过n-1次比较才能找到最小值或最大值。

如果同时找出最小值和最大值,则可以成对的处理元素,将一对输入元素进行比较,将较小者与当前最小值进行比较,将较大者与当前最大值进行比较,即每两个元素需要3次比较。这种情况下需要的比较次数是$$3\lfloor n/2\rfloor$$处(下中位数)

一般选择问题

一般选择问题和找最小值的运行时间是相同的,都是$$\Theta(n)$$。基于快速排序算法的RANDOMIZED-SELECT算法,对输入数组进行递归划分,然后处理划分的一边。

RANDOMIZED-SELECT Java实现

[code lang=”java”]public class RandomizedSelect{ public static int randomizedPartition(int[] A, int p, int r){ int s = (int)Math.ceil(Math.random() * (r - p)) + p; int temp = A[r]; A[r] = A[s]; A[s] = temp; int x = A[r]; int i = p - 1; for(int j = p; j < r; j++){ if(A[j] <= x){ i++; temp = A[j]; A[j] = A[i]; A[i] = temp; } } i++; A[r] = A[i]; A[i] = x; return i; }

public static int randomizedSelect(int[] A, int p, int r, int i){
	if(p == r){
		return A[p];
	}
	int q = randomizedPartition(A, p, r);
	int k = q - p + 1;
	if(i == k){
		return A[q];
	} else if(i &lt; k){
		return randomizedSelect(A, p, q - 1, i);
	} else{
		return randomizedSelect(A, q + 1, r, i - k);
	}
}

public static void main(String[] args){
	int[] array = {3, 2, 6, 1, 9, 7, 8, 5, 4};
	for(int i : array){
		System.out.print(i + &quot;,&quot;);
	}
	System.out.print(&quot;\n&quot;);
	System.out.println(&quot;The i-th number:&quot; + randomizedSelect(array, 0, array.length - 1, 5));
} } [/code]

算法复杂度

在最坏情况下,每次划分过程中都按照余下的元素中最大的进行划分,则运行时间为$$\Theta(n^2)$$。在平均情况下,运行时间为$$\Theta(n)$$。即平均情况下,任何顺序统计量都可以在线性时间内得到。

   

Published: 17 Sep 2011