优化你的 Perl 代码

你的 Perl 程序运行的时候是否需要消耗很多时间呢？这也许是你选择了耗时的数据结构或者算法所导致的。重新考虑一下你编写的函数，你可能就会在如何优化速度上取得很大收获。

一些简单的复杂度理论

在我们开始讨论如何加速程序执行之前，我们需要有一种科学方法来描述事物所消耗的时间。因为当我们讨论一个有着大量输入需要处理的算法时，完成处理的确切时间并非是一个确定的值。计算机科学家和数学家使用大写的 O 字母来作为描述时间消耗的量化符号。O 符号表述最坏情况下的时间消耗情况。当然还有其他一些符号用来描述最小和实际运行时间的量化。

不要因为谈论到计算机科学家和数学家而感到敬畏。下面几段将引进一种方法用以描述如秒，分钟，小时，天等数量级的差异。抑或是数字1，10，100和1000之间的差异。你不需要任何其他奇特或可怕的数学知识来理解它。

其实这很简单。如果一个函数的运行时间是一个常量，那么我们描述为 O(1)。（注意是大写字母 O）。常量意味着无论有多少数据需要处理（比如，有多少输入信息需要处理），处理的时间总是不变。

如果运行时间直接与输入信息的数量相关的话（线性关系），那么描述为 O(n)。或者说，如果输入的信息加倍，与此同时处理的时间也需要原来的两倍。另外还有一些函数的描述为 O(n^2) (平方) 或者 O(n^3) (立方) 或者更糟。

因为我们只关心事物的数量级（比如一个操作需要一分钟或者一小时），所以我们可以忽略一些常量因素或者其他一些小的东西。所以，O(2n) 和 O(n) 是一样的。同样，O(n+1) 和 O(n) 或者 O(n^2+n) 和 O(n^2) 也是如此。小的因素和他们的数量级比较起来是无足轻重的。

有一些方法可以分析代码并确定它的数量级（O），但是最简单的方法是看你重复处理数据的次数。如果不重复处理，那么就是 O(1)。如果你重复一次，那就是 O(n)。如果你使用了嵌套循环来处理数据，那可能就应该是 O(n^2).

http://www.perl.com/2002/02/12/graphics/graph-orders.jpg

例子 #1: 作图

为了方便我的日常工作，我开发了一个新的图片模块，因为现存的一个模块过度耗时，同时没有一些我想要的功能。这个模块的使用很方便，工作起来也很有效，但一碰到大的图片时就不行了。我需要一个平面子图来作依赖检查，而这样一个 1000个节点的图片计算在奔三1Ghz的机器上需要超过两分钟的时间。我需要它运行得更快些，否则我的客户一定会发疯的。

我起初的 Graph 模块如下（已经简化，只关心相关部分）：

 package Graph; # for Directed Graphs
 use strict;
 sub new {
  my $this = { edges => [],
               vertices => {} };
  bless $this, "Graph";
 }
 sub add_edge { # from x to y
  my ($this,$x,$y) = @_;
  $this->{vertices}{$x}++;
  $this->{vertices}{$y}++;
  push @{$this->{edges}},[$x=>$y];
 }
 sub in_edges {
  my ($this,$v) = @_;
  grep { $_->[1] eq $v } @{$this->{edges}};
 }

方法 add_edge 的时间复杂度是 O(1) ，因为无论处理的图片有多少点或者边缘，它总是消耗同样的时间。方法 in_edges 的时间复杂度是 O(n) ，因为它不得不重复处理图片的每个边缘数据（重复处理体现在 grep 函数中）。

有问题的代码部分如下：

 sub flat_subgraph {
    my ($graph,$start) = @_;
    my %seen;
    my @worklist = ($start);
    while (@worklist) {
      my $x = shift @worklist;
      $seen{$x}++;
      push @worklist, $graph->in_edges($x) unless $seen{$x};
    }
    return keys %seen;
 }

实际上我需要像下面这样处理多个顶点;

  my %dependencies;
  for (keys %{$graph->{vertices}}) {
   $dependencies{$_} = [ flat_subgraph( $graph, $_ ) ];
  }

这将使整个修平操作（flattening operation）的时间复杂度变为 O(n^3)。（依赖循环的数量级为 O(n)，函数 flat_subgraph 为 O(n)，函数 in_edges 为 O(n)）。这意味着当图片越大，则计算时间也越来越大。（想象一条带有如下值的曲线：1,8,27,64...，那是相对时间的曲线。）

缓存

而我的客户需要程序立即响应，所以我必须做一些事。首先我要缓存 in_edges 的计算。

 sub in_edges {
  my ($this,$v) = @_;
  if (exists $this->{cache}{in_edges}{$v}) {
      return @{$this->{cache}{in_edges}{$v}};
  } else {
    my @t = grep { $_->[1] eq $v } @{$this->{edges}};
    $this->{cache}{in_edges}{$v} = [@t];
    return @t;
   }
 }

这样做已经有所帮助，但还不够。当它还没被缓存时 in_edges 计算依旧很耗时。最坏情况下它的数量级仍为 O(n) ，但只当缓存后变为 O(1) 。平均而言，对于整个修平操作（flattening operation）仍是介于 O(n^2) 和 O(n^3) 之间，所以依旧很慢。

只有当相同的参数被调用时，这个函数的缓存才体现出作用。Mark-Jason Dominus 已经写了一个模块，叫做 Memoize，用它可以方便的实现缓存函数。参见 http://perl.plover.com/MiniMemoize/

改变结构

接下来我尝试着改变图片数据的结构。在我初始设计的时候，只要求简单，而没有考虑速度。但现在速度变得更加重要，所以我不得不改变设计。

我修改了 graph ，使得函数 in_edges 只在新的边缘添加时被调用。

 package Graph; # for Directed Graphs
 use strict;
 sub new {
  my $this = { edges => [],
               vertices => {},
               in_edges => {} };
  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":http://search.cpan.org/search?dist=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 符号的表层和复杂度理论。在数学和计算机的更深层次中还有很多对它的研究。但希望这里提到的能够帮助你掌握最基本的工具。

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

特别感谢

Walt Mankowski

取自"http://wiki.perlchina.org/index.php/%E4%BC%98%E5%8C%96%E4%BD%A0%E7%9A%84_Perl_%E4%BB%A3%E7%A0%81"

1个分类: 性能调试优化

转载自:http://wiki.perlchina.org/index.php/%E4%BC%98%E5%8C%96%E4%BD%A0%E7%9A%84_Perl_%E4%BB%A3%E7%A0%81