The Art of Readable Code && High Performance Comments

昨天在 stackoverflow 上看到一個有趣的問題:如何交換陣列中的 key,順手寫了幾段程式測試效能。原先在社群媒體上發表了 (原文連結):

在 stackoverflow 上看到一個有趣的問題,要交換 PHP assoc. array 的 key;我覺得重建陣列很醜(內建陣列順序只能透過 push/pop shift/unshift splice 操控),就弄了個 serialize 的版本。想不到比重建慢十倍 T_T

但被 gy 抱怨看不懂,只好回 blog 寫份比較完整的解釋,順便紀錄 2013 年的開始。

PHP 的陣列相當強大,其實作接近有序的 hash table,能以 stack (array_push, array_pop), queue (array_shift, array_unshift), 或 iterator 介面 (foreach) 去操作,並以 $array[‘key’] = ‘value’ 的方法賦值。

陣列內元素的先後順序,預設依照鍵入次序安排;因此若執行 $a[1] = ‘b’; $a[0] = ‘a’,則在列舉時, 1 => ‘b’ 會先出現,然後才是 0 => ‘a’。在 PHP 裡,有幾類函數能變動這個順序:

  1. 排序:依照特定原則重新排序整個陣列 / hash table
  2. 反序與亂序:array_reverse, shuffle
  3. 部份替代:array_splice (若為 numeric key 則不保存,亦即會被設為該鍵值組的實際序數)
  4. 重建:array_unique, …

然而要透過上述函式,在保留所有「值」序數的前提下,調換兩組「鍵」的位置,稍微比想像中的複雜。最直觀,也是由首位回應者提出的方式,是列舉原陣列並建立新陣列,並替換其中「鍵」的值。我擔憂這樣的寫法效能可能較低,牽涉到列舉並重建陣列,因此想了另一種作法。

PHP 提供 serialize / unserialize (序列化/去序列化)函數,可將任何物件(class 要先能載入定義)與文字間做轉換;而陣列對文字的轉換規則相當單純。因此我認為,將原陣列經過 serialize、替換、unserialize 之後,除了能得出正確答案之外,速度應該會比較快。

然而這中間又卡到 PHP 內的字串替換函式的問題:PHP 的 *_replace 函式都是依次進行替換,而非同時替換完畢。str_replace(array(‘a’,’b’), array(‘b’,’c’), ‘ab’) 會變成 ‘cc’,而非 ‘bc’,因而無法用於字串交換。

最後只好使用邪惡招數:先以 $str1 對 serialized array 進行 explode (內建的 explode 也不能這麼用,所以只好用 strpos 迭代),將 exploded array 內的 $str2 轉換為 $str1,以 $str1 將陣列 join 回字串,最後再將這字串 unserialize 回陣列。

實測結果:重建 0.13 秒,序列化 1.5 秒。
結果?進行一萬次替換,重建陣列法耗時 0.13 秒,序列化法 1.5 秒,完敗。看來 PHP 對於陣列動態增減值的效能還是不錯的嘛 ˇˇ (註:跑在一台很慢的虛擬機器上)

* 同場加映:

學長 +Ming Ling 提問 array_splice 會不會比較快,既然如此就多跑一種狀態吧 XD
在寫作過程中發現 PHP 的 array_splice 不保留第四參數的 $key,因此不如用 array_slice (兩者差異見下表)。

array_splice array_slice
功能 將陣列中的特定範圍移除並取代 取出陣列中的特定範圍
回傳值 被取代的範圍內容 被取出的範圍內容
傳入陣列形式 passing by reference, 且會被更動 passing by value, 不影響呼叫端的值

實測結果:序列化 0.94 秒,重建 0.25 秒,Slice 0.60 秒。

再次證明 PHP 對於重建/動態變動陣列的最佳化!
註:兩次測試使用不同主機,並且程式有稍做調整。

測試程式碼:

發表迴響

分類

%d 位部落客按了讚: