优化你的 Perl 代码

  bless $this, "Graph";
}
sub add_edge { # from x to y
  my ($this,$x,$y) = @_;
  $this->{vertices}{$x}++;
  $this->{vertices}{$y}++;
  push @{$this->{in_edges}{$y}}, $x;
  push @{$this->{edges}},[$x=>$y];
}
sub in_edges {
  my ($this,$v) = @_;
  return @{$this->{in_edges}{$v}};
}
add_edge 还是 O(1)—它依然以常量时间执行。 in_edges 现在是 O(1) ; 它的运行时间将不随边缘的数量变化而变化。
这就是我需要的解决方案，它使得四分多钟的计算减少为 6 秒。

良好接口的重要性
这样的优化得益于良好设计的模块接口。该接口隐藏了所有处理细节，这样各种不同的操作就可以方便的和它连接(plug in)。(这正是我用来做测试的方法，我有一个正规的 Graph, 一个 Graph::Cached, 和一个 Graph::Fast. 一旦我认为 Graph::Fast 是最好的，我只需把它改名为 Graph 就可以了。)
我很高兴我能这样来设计 Graph 模块。我在设计的时候力求先简单设计，而后优化。也许你听到过这样一句话： “太早优化是罪恶之源。” 如果我先优化代码，那么后面我就很有可能将要面对无法运行的复杂代码而结束。虽然我的初始设计很慢，但它能够持续不断的运行，到后面优化后依然能保证代码的正确运行。

例子 #2: 重复信息的过滤
你并不需要总是尝试优化代码到最大限度。优化代码费时费力，并非总是值得这样做的。如果你花了两天而只提速两秒的话，就很不值得了。（除非该程序每天都要运行上百次）。如果程序已经足够快了，那就作上标记“没必要更快了”。
我们的第二个例子是电子邮件的重复信息过滤。当你收到一封信，它的 cc 列表同时包含你所在的邮件列表的地址的时候，可以帮助你过滤掉重复信件。

这个过滤器的想法很简单:

  skip $message if seen $message->id;

我们只关心 seen 函数。它搜索缓存中的 id. 我们如何操作才能最有效的加速邮件过滤呢？（更多的关于使用 Perl 作邮件过滤信息，可以参见 Mail::Audit 。）
两个最显然的做法是实现 seen 函数时，使用简单的线性查找 (O(n)) 还是使用持续的数据库/哈希表来查找(O(1))。我将忽略数据库操作带来的消耗以及去除旧的 Message-Id 所消耗的时间。

线性方法输出含有分割符的各个 message id。 有些程序使用空字符（null bytes），有些使用新行符（newlines）。

而数据库/哈希表方法则将 message id 存放在二进制数据库中（如 DBM 或者 Berkeley DB 文件）。只是以消耗磁盘空间的代价换取速度上的提高。

但是，这里有一个因素需要考虑——开销。线性查找少一些，而 DB 文件操作则大一些。（这里的开销指打开文件和初始化数据结构的时间消耗）

表：比较

    纪录数 | 注释
  -----------------
    100   | 线性更快：快 415%
    250   | 线性更快：快 430%
    500   | 哈希更快：快 350%
   1000   | 哈希更快：快 690%

我在我的 P2/400 上做了一些试验，得到了上面的结果。哈希查找的速度基本保持不变，而与此同时，查找少于 250 个元素的缓存时，线性查找很快，但随着缓存中元素变多，查找速度便快速下降。
回到前面的问题。我们需要关注一下我们的 message-id 缓存大小来决定使用什么方法来实现查找操作。在这种情况下，我们通常认为不会有很大数量的数据元素需要缓存，因为一般两到三天才需要作一次这样的过滤。（而且大多情况下甚至只需要一天。）

针对这个问题，一个 O(1) 的解决方案是可行的，但是这个常量时间可能比 O(n) 的方案更多. 这两案例的实现有点不重要，但在某些情况下很难实现 O(1) ——也不值得实现。

总结
Perl 是一个强大的语言，但它仍不能防止编程者的差的设计。一个失误可能是因为选择了错误的数据结构或者算法。通过使用一些简单的复杂度理论，就有可能优化代码而提升速度。
我这里只是接触了 O 符号的表层和复杂度理论。在数学和计算机的更深层次中还有很多对它的研究。但希望这里提到的能够帮助你掌握最基本的工具。

正如第二个例子所示，你不必为优化而耗费过多时间来考虑。过度优化并不值得。

更多的信息
Google http://www.google.com/search?q=big-O+complexity
Introduction to the Theory of Computation Part Three of Sipser, Michael. “Introduction to the Theory of Computation”. PWS Publishing Company. Boston, MA. 1997.
Algorithms and Complexity, Internet Edition http://www.cis.upenn.edu/~wilf/AlgComp2.html
特别感谢
Walt Mankowski
Perl.com Compilation Copyright ?? 1998-2000 O’Reilly & Associates, Inc.