|
你的 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/
[1] [2] 下一页 |
