2010 04月 » 为之漫笔

你是那10%可以实现二分查找算法的程序员吗？

2010年04月20日编程技术, 翻译

——《编程珠玑》引发的编程竞赛

原文链接：http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/
迈克·泰勒（Mike Taylor），2010年4月19日
翻译完成：2010年4月20日

有一些讲编程的图书，我会从头到尾、一字不落地反复研读；还有一些讲编程的图书，我已经看过好几遍了，但每次差不多都是只看其中的一章。乔恩·本特利（Jon Bentley）1986年的经典名著《编程珠玑》（Programming Pearls）则是少数几本能同时归入上述两类的编程图书之一，我手里这本书的封面已经严重磨损，下图可以为证（点击看大图，注意左下角。——译者注）。

（我有这本书的第1版[amazon.com，amazon.co.uk]，上面就是扫描的这一版的封面，好像我该买一本又新又便宜的第2版了[amazon.com，amazon.co.uk]，第2版比第1版多了3章内容。）

我打算最近再专门写一篇关于这本书的文章（我已经为Coders at Work、The Elements of Programming Style、Programming the Commodore 64 和The C Programming Language专门写了几篇书评），但今天我只想就这本书中的几段话谈谈自己的想法。这几段内容有点骇人听闻。

只有10%的程序员可以写出二分查找

每次翻开《编程珠玑》，我都会先看一看下面这几段文字：

二分查找可以解决（预排序数组的查找）问题：只要数组中包含T（即要查找的值），那么通过不断缩小包含T的范围，最终就可以找到它。一开始，范围覆盖整个数组。将数组的中间项与T进行比较，可以排除一半元素，范围缩小一半。就这样反复比较，反复缩小范围，最终就会在数组中找到T，或者确定原以为T所在的范围实际为空。对于包含N个元素的表，整个查找过程大约要经过log(2)N次比较。

多数程序员都觉得只要理解了上面的描述，写出代码就不难了；但事实并非如此。如果你不认同这一点，最好的办法就是放下书本，自己动手写一写。试试吧。

我在贝尔实验室和IBM的时候都出过这道考题。那些专业的程序员有几个小时的时间，可以用他们选择的语言把上面的描述写出来；写出高级伪代码也可以。考试结束后，差不多所有程序员都认为自己写出了正确的程序。于是，我们花了半个钟头来看他们编写的代码经过测试用例验证的结果。几次课，一百多人的结果相差无几：90%的程序员写的程序中有bug（我并不认为没有bug的代码就正确）。

我很惊讶：在足够的时间内，只有大约10%的专业程序员可以把这个小程序写对。但写不对这个小程序的还不止这些人：高德纳在《计算机程序设计的艺术第3卷排序和查找》第6.2.1节的“历史与参考文献”部分指出，虽然早在1946年就有人将二分查找的方法公诸于世，但直到1962年才有人写出没有bug的二分查找程序。

——乔恩·本特利，《编程珠玑（第1版）》第35-36页

几个小时！90%！老兄，严肃点！难道这还不够骇人听闻吗？

之所以想看这本书的第2版，原因之一就是想看看这几段文字有没有修订过，看看从1986年到1999年出第2版，这个数字有没有变化。直觉告诉我，这个数字一定向好的方向变化了，事物都是向好的方向发展的嘛。但理性却告诉我，在一个程序员把更多的时间都花在摆弄库上，而不是编写实际代码的时代，重现核心算法的能力即使有也一定会弱化。别忘了，本特利提到的那些家伙可都不是等闲之辈，他们都是贝尔实验室和IBM的专业人员。所以，我们有理由相信他们的成绩实际上已经是最好的了。

好，下面就做一个二分查找的测验

我跟你一样（如果你是这么想的），想马上就试一试。（好啦，不是马上。先看完这篇文章！）我相信看这篇文章的人都知道什么是二分查找算法，即使你不知道，上面引用的本特利的描述也应该够了。请你打开编辑器，编写一个二分查找例程。什么时候觉得没有任何问题了，保留那个版本。然后测试，然后通过在下面留言的方式告诉我你是不是第一次就做对了。我们肯定能打破本特利10%的纪录吗？

规则如下。

使用你喜欢的任何编程语言。
不要剪切粘贴或以任何方式复制别人的代码。甚至在你写完之前，都不要参考其他的二分查找代码。
甚至于我不得不强调，别调用bsearch()，或使用其他瞒天过海的手法
时间自己来定：5分钟不短——只要你能保证写完写对；8小时不长——只要你愿意（而且有那么多闲工夫）。
可以使用编译器消除一些无意识的错误，如语法错误或变量初始化失败，但……
在确定程序正确之前不要测试。
最后，也是最重要的：如果决定参与这次测验，就必须报告。成功也好，失败也罢，甚至半途而废也要给我个话儿。否则，就无法保证测验结果的准确性了。

（考虑到这只是一次测验，可以忽略计算索引时导致的数值溢出。这里描述了相应的情形，但打算参加这次测验的人在编完程序之前不要看，因为那篇文章里包含一个正确的二分查找的实现，想洁身自好的朋友一定是不屑为之的。）

如果你的代码经验证确实正确，那么如果你愿意的话，欢迎你在留言里贴出自己的代码。不过，假如你这样做了，而后来的留言给你挑出了bug，请你一定想好怎样为维护自己的形象而自圆其说

更酷的玩法：对于那些信心十足的人，如果你真敢肯定自己的程序没有问题，可以先把代码贴在留言里，然后再测试。当然，你必须要在留言里说明这一点，以便大家发现你的bug时，会考虑多少给你留些情面。

我会在某个时间总结一下这次测试的结果——比如说，一周以后。

行动吧！

第一次更新（一个半小时后）

感谢朋友们的积极响应，这么快就有那么多留言！我得提醒大家，WordPress的留言系统会解释HTML，因此会吞掉类似下面的代码段

if a[mid] < value

最好的办法就是把源代码放在{source}…{source}标签之间，注意用方括号代替这里的花括号。（我第一次想告诉大家这一点时，使用的是方括号，结果我写的规避标记的说明，反而被当成了标记——悲哀呀！）这样做还可以保留缩进，否则我还不知道有什么办法可以做到这一点。

替WordPress向大家致歉：我真的希望这个平台允许留言者预览留言和/或在发表后还能编辑留言，这样就可以避免出现乱七八糟的代码了。我也想了办法自己动手解决这个问题，但WordPress不仅会错误地显示带有<符号的代码，它实际上会丢弃该符号后面的所有内容，唉，我想我是没折了。

第二次更新（在原文章发表4个小时后）

哈哈，你们这些家伙太出人意料了。仅仅4个小时，这篇文章的留言数就超过了以前的一篇文章保持的纪录（Whatever Happened to Programming此时的留言有206条）。

如果想看到相关的更多讨论，Hacker News中有不少不错的留言，另外Reddit的留言质量虽然差一点，但也值得一看。这些讨论把实际地编写代码看成只有精英程序员才会干的事。

译后记：看了几眼，能认出来的加上认不出来的：C、PHP、Ruby、Python、Common Lisp、VB.NET 、C#、Java、Javascript、Delphi、Haskell、Scheme、Clojure、Perl、Smalltalk、FORTRAN、Lua、Objective-C、ColdFusion……各种各样语言的实现齐聚一堂。

有心人乔尔·甘勒（Joe Ganley）对前100个留言作了统计，结果如下：

Python 40
C/C++ 36
Unknown/pseudocode 6
Lisp/Clojure/Scheme 5
PHP 4
Three each: Java, Perl, C#, JavaScript
Haskell 2
One each: VB, Delphi, Smalltalk, FORTRAN, Lua, Objective-C, ColdFusion

Conclusion: Almost everyone (who cares about implementing binary search, anyway) uses C/C++ or Python.

PS：专注前端开发的程序员们，可以参考《JavaScript高级程序设计》的作者Nicholas C. Zakas使用JavaScript实现的一些基本算法，链接地址如下http://www.nczonline.net/blog/tag/computer-science/。其中，对本文提到的二分查找算法的实现如下：

//Copyright 2009 Nicholas C. Zakas. All rights reserved.
//MIT-Licensed, see source file
function binarySearch(items, value){

var startIndex = 0,
stopIndex = items.length – 1,
middle = Math.floor((stopIndex + startIndex)/2);

while(items[middle] != value && startIndex < stopIndex){

//adjust search area（调整查找范围）
if (value < items[middle]){
stopIndex = middle - 1;
} else if (value > items[middle]){
startIndex = middle + 1;
}

//recalculate middle（重新计算中项索引）
middle = Math.floor((stopIndex + startIndex)/2);
}

//make sure it’s the right value（确保返回正确的值）
return (items[middle] != value) ? -1 : middle;
}

有 24 条评论

Android开发问题二则

2010年04月18日原创, 移动开发

配置完Android开发环境后，遇到两个问题，一个属于非技术问题，另一个属于技术问题。

先说非技术问题。

很简单，启动Android模拟器（需要先创建AVD）时，先看到的是一个文本界面，我一开始以为自己的配置出了什么问题。迷惑了大半天，晚上从外面吃饭回来，突然想起来《Android基础教程》（人民邮电出版社，2009年11月）中有一段提示：“启动模拟器需要花较长时间。可以这样想象一下——首次开机时，手机也需要启动，就像任何计算机系统一样。关闭模拟器就像是关闭手机或取出手机电池一样。”会不会是我太着急了？应该有点耐心才好。于是，我重新启动模拟器，耐心等待……大约3分钟后，终于看到Android的图形用户界面，OK。

正好《Beginning Android 2》这本书中也有一段相关的话：NOTE: The first time you use an AVD with the emulator, it will take substantially longer to start than it will subsequent times.（注意：第一次使用AVD来启动模拟器的时间会比较长，后续的启动速度会有所提升。）

再说技术问题。

前面只是解决了启动模拟器的问题，接下来就是要在模拟器中实际地加载新应用程序并进行测试。但是，我新创建了FirstApp应用程序，在通过Eclipse运行该项目时（也可以在命令行中使用ant构建项目，然后运行android命令，再启动模拟器；不过，这需要再下载其他软件包），提示出错，错误信息如下：

1. Project “FirstApp” is missing required source folder: ‘gen’
2. The project could not be built until buid path errors are resolved.

在网上搜索到几个解决方案（列在下面，供朋友们参考）。但奇怪的是，在刚搜索到第一个方案时，还没等到采取任何措施，Eclipse中的错误居然自动消失了（FirstApp项目下方的红叉也不见了），再Run as Android Application，一切正常了。我想，也许正如第三个方案中某人所说的，Eclipse并不能实时检测到OS文件系统的变化（编译项目时，会生成新文件），这也许就是导致这个技术问题的原因——至于是不是这个原因，还有待于进一步求证。

一、右击项目，选择preferences->builder，在右边的configure一栏中将Android Packege Builder一项提到Java Builer之前
出处：http://www.androidin.net/bbs/thread-708-11-1.html

二、将Eclipse自动生成的R.java删掉，刷新项目，R.java便会重新生成
出处：http://www.blogjava.net/crazycoding/archive/2010/03/27/316701.html

三、在项目文件夹中新创建一个Java类或者直接修改自动生成的类文件
出处：http://www.coderanch.com/t/466092/Android/Mobile/android-eclipse

以下是几个人的回复，感觉这种讨论的技术氛围很不错。今天太晚了，明天天亮还要去平谷，回来再翻译。

James Dixon的回复
Hi Divya
I’ve had the same problem as well. I think the issue is that the project creation does not initiate a build when it finishes, so you need to make a change, and save for it to generate the gen folder.
For me creating a new java class seemed to do the trick, but I’d imagine just making a change to a file and saving should work too.

Robert F. Howard的回复
I just ran into this, too. I am following the example in Hello Android, which I assume is what the others in this thread were doing. James’s solution (editing the source file) worked for me, so thank you for that.
So your solution is good, but I don’t think I totally believe the diagnosis. The thing is, the directory actually did exist before I edited the file and rebuilt. This is my first time using Eclipse, and it’s very disappointing. The error message should specify the full path of the directory it wants, and then it should be possible to create the directory and re-build, but it doesn’t work until the source file is edited. It makes me wonder what is really going on inside Eclipse.

Tim Holloway的回复
This seems to be a small glitch courtesy of Eclipse’s distancing itself from the OS filesystem (which is why Eclipse has an explicit Refresh command).
The gen folder and the “R.java” file are built by one of the Android utilities. The Eclipse Android plugin invokes this app, but it doesn’t always know when it needs to. I have similar problems when I want to define a new resource ID. Since I can’t seem to get the GUI resource ID definer to enable itself, I just create new IDs in the resource files themselves. But unless I trigger the android resource generator, they don’t get inserted into “R.java”.
And you don’t want to manually insert into “R.java”, because when the resource compiler does fire off, your code mods will be overwritten.
One way to force the issue is to select the Project/Clean menu command. If you have the automatic build switched off, you’ll then have to initiate a build. Otherwise the clean will fire off the auto-build process.

有 4 条评论

构建Android开发环境

2010年04月18日原创, 移动开发

在本文写作时，Android SDK的最新版本是2.1。现在，我们来看一看如何在Windows平台下构建Android 2.1开发环境。

先期需要下载的软件包如下：

1、JDK 1.6+
2、Android SDK 1.6
3、Android SDK Setup
4、Eclipse IDE for Java Developers

看到这些，可能心急的朋友会禁不住问：“不是要构建Android 2.1开发环境吗？怎么还要下载Android SDK 1.6而不是2.1呢？”

没错，是要讲怎么构建Android 2.1开发环境。但是，经过几次尝试，我发现直接下载安装Android SDK 2.0和2.1有问题。什么问题？简单地说，就是这两个最新版本的SDK包中都不包含adb.exe文件，无法在Eclipse中指定Android SDK的位置（也就意味着没法使用Eclipse来开发）。因此，这才走了一条曲线救国的道路；也许，正如我自己的尝试所证实的：Android SDK 2.0和2.1实际上都是升级包，而不是完整的开发包。我比较了一下，Android SDK 2.0和2.1的大小分别是76.6MB和77.3MB，而Android SDK 1.6的大小则是248MB，相差还是很悬殊的，这一点似乎也佐证了我的判断。但是，不管怎样，先下载Android SDK 1.6，然后再通过ADT（Android Developer Tools，Android开发人员工具）和Android SDK Setup程序来下载和更新Android SDK 2.0和2.1，是成功了。

闲话少说，言归正传。

首先，访问http://java.sun.com/javase/downloads/widget/jdk6.jsp
下载Java SE Development Kit 6u20（jdk-6u20-windows-i586.exe）
文件大小76.67 MB。

其次，访问http://dl.google.com/android/archives/android-sdk-windows-1.6_r1.zip
下载Android SDK 1.6（android-sdk-windows-1.6_r1.zip）
文件大小248M。

然后，访问http://dl.google.com/android/android-sdk_r04-windows.zip
下载Android SDK Setup（android-sdk_r04-windows.zip）
文件大小22MB。

最后，访问http://www.eclipse.org/downloads/
下载Eclipse IDE for Java Developers（eclipse-java-galileo-SR2-win32.zip）
文件大小92.7MB。

下载完成后，开始安装和配置。

第一步，安装和配置JDK。

下载后，双击运行jdk-6u20-windows-i586.exe，假设选择安装到C:\Java\jdk1.6.0_20目录下（当然，安装到默认路径下也没有问题）。安装完毕后，就是配置环境变量。步骤如下：

(1)设置JAVA路径

在“我的电脑”上点右键，选“属性”，打开“系统属性”对话框，点“高级”选项卡，再点“环境变量”按钮，在打开的对话框中的“系统变量”下方，点“新建”，然后在对话框中的“变量名”中填JAVA_HOME，在“变量值”中填C:\Java\jdk1.6.0_20，点“确定”。

(2)设置CLASS路径

再“新建”一个系统变量，在“变量名”中填CLASSPATH，在“变量值”中填.;%JAVA_HOME%\lib;%JAVA_HOME%\lib\tools.jar。
说明：最开始的.;中的.（点）表示当前路径，;（分号）是路径分隔符。接下来的%JAVA_HOME%引用的是前面刚创建的JAVA安装路径。

(3)设置PATH路径

PATH变量一般都有了，因此选中点“编辑”，然后在“变量值”后面加上;%JAVA_HOME%\bin;%JAVA_HOME%\jre\bin，注意前面的分号。

这样，JDK就安装好。“开始->运行”，输入cmd，然后在命令行提示符中输入：java -version，应该能够看到java version “1.6.0_20″信息；JDK安装成功。

第二步，解压和配置Android SDK 1.6

将下载到的android-sdk-windows-1.6_r1.zip解压缩到C:\android-sdk-windows-1.6_r1目录中（解压到哪个目录都没有问题）。然后，配置环境变量。步骤如下：

(1)设置Android路径

重复第一步的(1)，新建一个“系统变量”，在“变量名”中填Android_Home（大小写没有问题），在“变量值”加填C:\android-sdk-windows-1.6_r1。

(2)设置PATH路径

“编辑”PATH变量，在“变量值”后面加上;%Android_Home%\tools，注意前面的分号。

这样，Android SDK 1.6就安装好了。“开始->运行”，输入cmd，然后在命令行提示符中输入：android -help，应该能够看到帮助信息；Android SDK 1.6安装成功。

第三步，解压Eclipse，关联Android SDK，安装ADT

将下载到的eclipse-java-galileo-SR2-win32.zip解压缩到C:\eclipse，然后进入这个文件夹，双击eclipse.exe，启动Eclipse。

安装ADT：菜单“Help -> Install New Software…”，打开Install对话框，点击Add…按钮，添加站点（Add Site），在Name中填ADT，在Location中填https://dl-ssl.google.com/android/eclipse/。然后，下载安装ADT。

关联Adnroid SDK：菜单“Windows->Preferences”，打开Preferences对话框，点击Android，在右侧的Android Reference中，点SDK Location文本框右侧的Browse…按钮，找到C:\android-sdk-windows-1.6_r1，“确定”。

第四步，解压Android SDK Setup，下载更新Android SDK 2.0和2.1

将下载到的android-sdk_r04-windows.zip解压缩到C:\android-sdk-windows，然后进入这个文件夹，双击SDK Setup.exe，启动Android SDK and AVD Manager，选中左侧Settings项，然后在右侧面板选中Force https://… sources to be fetched using http://，然后选择Save & Apply。然后，参见这里的图解：

如何使用Android SDK Setup? http://www.android123.com.cn/zhongwensdk/366.html

我选择了所有需要更新的内容，包括：