優化你的 Perl 代碼

你的 Perl 程序運行的時候是否需要消耗很多時間呢？這也許是你選擇了耗時的數據結構或者算法所導致的。重新考慮一下你編寫的函數，你可能就會在如何優化速度上取得很大收獲。

一些簡單的復雜度理論

在我們開始討論如何加速程序執行之前，我們需要有一種科學方法來描述事物所消耗的時間。因為當我們討論一個有著大量輸入需要處理的算法時，完成處理的確切時間并非是一個確定的值。計算機科學家和數學家使用大寫的 O 字母來作為描述時間消耗的量化符號。O 符號表述最壞情況下的時間消耗情況。當然還有其他一些符號用來描述最小和實際運行時間的量化。

不要因為談論到計算機科學家和數學家而感到敬畏。下面幾段將引進一種方法用以描述如秒，分鐘，小時，天等數量級的差異。抑或是數字1，10，100和1000之間的差異。你不需要任何其他奇特或可怕的數學知識來理解它。

其實這很簡單。如果一個函數的運行時間是一個常量，那么我們描述為 O(1)。（注意是大寫字母 O）。常量意味著無論有多少數據需要處理（比如，有多少輸入信息需要處理），處理的時間總是不變。

如果運行時間直接與輸入信息的數量相關的話（線性關系），那么描述為 O(n)?；蛘哒f，如果輸入的信息加倍，與此同時處理的時間也需要原來的兩倍。另外還有一些函數的描述為 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, Internet Edition http://www.cis.upenn.edu/~wilf/AlgComp2.html

特別感謝

Walt Mankowski

Perl.com Compilation Copyright ?? 1998-2000 O’Reilly & Associates, Inc.