优化你的 Perl 代码

作者： 来源： 点击： 日期：2007-4-9 16:52:07

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

Perl.com/2002/02/12/graphics/graph-orders.jpg');} }" src="http://www.Perl.com/2002/02/12/graphics/graph-orders.jpg" onload="function anonymous() { if(this.width>screen.width*0.7) {this.resized=true; this.width=screen.width*0.7; this.alt='Click here to open new window\nCTRL+Mouse wheel to zoom in/out';} }" border=0>

例子 #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，用它可以方便的实现缓存函数。参见 Perl.plover.com/MiniMemoize/" target=_blank>http://Perl.plover.com/MiniMemoize/

改变结构
接下来我尝试着改变图片数据的结构。在我初始设计的时候，只要求简单，而没有考虑速度。但现在速度变得更加重要，所以我不得不改变设计。
我修改了 graph ，使得函数 in_edges 只在新的边缘添加时被调用。

package Graph; # for Directed Graphs
use strict;
sub new {
  my $this = { edges => [],
            vertices => {},
            in_edges => {} };

共2页首页上一页 [1] [2] 下一页尾页>

上一篇: 用 Perl 进行 GNOME 编程
下一篇: Perl 语言的重要价值体现

如您对此有意见或有疑问，请您到中国代码论坛参与讨论！