昨天在 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 對於重建/動態變動陣列的最佳化!
註:兩次測試使用不同主機,並且程式有稍做調整。

測試程式碼:

 $value) {
		if ($key === $key1) {
			$ret[$key2] = $array[$key1];
		} else if ($key === $key2) {
			$ret[$key1] = $array[$key2];
		} else {
			$ret[$key] = $value;
		}
	}
	return $ret;
}

// ===================================
// Array_Splice
// ===================================

function skn_slice($array, $k1, $k2) {
	$keys = array_keys($array);

	$k1p = array_search($k1, $keys);
	$k2p = array_search($k2, $keys);

    $is_k1_larger = $k1p > $k2p ;

    $kminp = $is_k1_larger ? $k2p : $k1p;
    $kmaxp = $is_k1_larger ? $k1p : $k2p;
	
	$kmin = $keys[$kminp];
	$kmax = $keys[$kmaxp];

	$vmin = $array[$kmin];
	$vmax = $array[$kmax];

	$array_s1 = array_slice($array, 0, $kminp);
	$array_s2 = array_slice($array, $kminp + 1, $kmaxp);
	$array_s3 = array_slice($array, $kmaxp + 1);

    $array = $array_s1 + array($kmax => $vmin) + $array_s2 + array($kmin => $vmax) + $array_s3;

    // 使用 array_merge 會多花約 20% 的執行時間,猜想與 $array[] 效能高過 array_push($array, ...)
    // 原因相同:函式調用的成本。
    // 同理,若改成呼叫 array_splice 兩次(而非 array_slice 三次)可能可以降低執行時間。

    // $array = array_merge(
    //     $array_s1, array($kmax => $vmin), 
    //     $array_s2, array($kmin => $vmax), 
    //     $array_s3);
    
    return $array;
}

// ===================================
// Main
// ===================================

$their_name = array(
		//       Key   =>  Value
		'Jim'   => 'dad',
		'Josh'  => 'son',
		'Jamie' => 'mom',
		'Jane'  => 'daughter',
		'Jill'  => 'daughter'
		);
$k1 = 'Jim';
$k2 = 'Jill';

$times = 10000;
$cnds = array(
	'Serialize',
	'Rebuild',
	'Slice',
);

foreach($cnds as $cnd) {
	$fp_main = "skn_".strtolower($cnd);

	if (!function_exists($fp_main))
		continue;

	$ts = microtime(true);
	for($i=0;$i<$times;$i++)
		$output = $fp_main($their_name, $k1, $k2);

	echo "$cnd: ". (microtime(true) - $ts) . "s\n";
	print_r($output);
}
?>