• 丰搜首页
• 文档中心
• 视频中心
• 丰搜贴吧
• 问题集锦
• 更多功能

选择显示字体大小

• 最大
• 较大
• 标准

优化你的 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).

例子 #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 。）

两个最显然的做法是实现 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, inte.net edition http://www.cis.upenn.edu/~wilf/algcomp2.html

特别感谢

walt mankowski

perl.com compilation copyright ?? 1998-2000 o’reilly & associates, inc.

 

关键字 本文所属关键字

相关 与本文相关文章

分类 所有文章关键字导航

标准 网站致力的规范