应用算法的实际情况——简单就是美

应用算法的实际情况——简单就是美

实际上，高级算法未必是最优解，古典算法有时也不错。进一步说，与知名算法相比，简单算法更好的情况也不罕见。

Hatena Bookmark的Firefox扩展的搜索功能的尝试

介绍一个Hatena中的实际例子。Hatena Bookmark中有Firefox扩展这个工具，通过它可以将Hatena Bookmark与浏览器集成，十分方便。该扩展可以针对用户以前保存过的书签数据进行增量（incremental）搜索（如图7.1所示）。

 

我们团队讨论了该搜索功能的实现方法，最后结果是，由于增量搜索中搜索动作发生频率很高，而且又是在客户端计算，所以计算量必须少。一些人的数据量能达到一万条以上，所以选择了Suffix Array。

Suffix Array这个数据结构主要用于文本数据等的高速查找。查找本身很快，但必须事先花费很长时间创建数据结构。而且，要让Suffix Array在应用程序中达到实用程度，如何缩短这段时间，就成了要解决的课题。当时我们采用了刚刚发现的IS方法^[1]解决。

多次尝试之后，我们用Firefox扩展中唯一可用的JavaScript语言实现了IS方法，但实际结合到应用程序之后并没有达到满意的效果。尽管速度有所提高，但预处理仍然需要花费很长时间，用户添加书签时进行的预处理会给机器造成很大负担。

经过痛苦的选择之后，我们放弃了Suffix Array，而是使用Firefox扩展内部的SQLite功能，用SQL的like进行部分查找（也就是线性查找）。这会让数据量大的人搜索速度降低，但也是没办法的事，只能妥协于这种方法了。

不过，实际完成后发现，使用上完全没有任何问题。曾经担心过的几万条数据量的问题，也由于现代计算机的性能提高，查找上完全没有问题……所以就这样了。

得到的经验

从这个例子中得到的经验就是，评测和估算非常重要，并且偶尔尝试一下简单的实现也很重要。为大规模数据进行优化固然很重要，但从本例中可见，数据较少时优化没有任何意义。而且它也说明，通过人的感觉来推断数据量多少是不可靠的。

等

请不要忘记，大部分常用算法都有已发布的实现，供他人使用。

以前面所说的IS方法为例，当时JavaScript上Suffix Array

并没有好的实现，所以不得不自己编写，但如果是Perl，那么CPAN上有大量各种算法的开源实现函数库，其他语言也一样。

灵活运用这一类实现，可以缩短开发时间。话虽如此，我们不建议在不了解其内容的情况下使用。必须适当了解它做了哪些操作，否则就可能做出错误的选择。

例如，CPAN上有大量压缩算法的实现。压缩也有适合不适合之分，比如对较短文件有效的算法、花费时间很长但压缩比很高的算法、压缩比较低但速度快的算法等，算法的特性各不相同。为了正确选择算法，了解一些算法知识没有坏处。在CPAN上搜索“Algorithm”的结果如图7.2所示。

相反，这些函数库的API有时无法满足我们的规格要求，

 

或者实现的功能过多。这时可以仅实现必要的地方，既能抑制工作量，单位成本获得的效果也更高。重点就是平衡性。

 

本文节选自《大规模WEB服务开发技术》一书

图书详细信息:http://blog.chinaunix.net/space.php?uid=13164110&do=blog&id=2211482