在程式設計中,總是會需要處理一些數據,例如給定2個陣列取出它們的差集。雖然實現的方法很多,但是哪一種方法用來求差集的表現比較好呢?今天我們就分享一個求差集的實例,以及如何去優化我們的程式碼效能。
題目如下: 給你兩個分別有 5000 個元素的數組,計算他們的差集 -- 說白了也就是用 PHP 和你認為最好的演算法實現 array_diff 的演算法。初次接到這個題目,我發現這非常的簡單,於是按照以往的經驗「隨便」寫了一個:
function array_diff($array_1, $array_2) { $diff = array(); foreach ($array_1 as $k => $v1) { $flag = false; foreach ($array_2 as $v2) { if ($flag = ($v1 == $v2)) { break; } } if (!$flag) { $diff[$k] = $v1; } } return $diff; }
雖然實作是可以的,但是發現這個函數的效率是慘不忍睹。於是我又重新考慮了下,並優化了演算法,第二個函數看起來是這個樣子的:
function array_diff($array_1, $array_2) { foreach ($array_1 as $key => $item) { if (in_array($item, $array_2, true)) { unset($array_1[$key]); } } return $array_1; }
嗯,這次幾乎可以和原 array_diff 函數的速度媲美了。但是還有沒有更優化的方法呢?由 ChinaUnix 上的一篇文章(不好意思,作弊了),我發現 PHP 竟然可以這樣寫:
function array_diff($array_1, $array_2) { $array_2 = array_flip($array_2); foreach ($array_1 as $key => $item) { if (isset($array_2[$item])) { unset($array_1[$key]); } } return $array_1; }
這個函數的效率非常的驚人,甚至比原 array_diff 函數的速度都要快。究其原因,我找到了解釋:
因為鍵是進行HASH 組織的,查找很快;
而Value 只是由Key 組織存放,本身沒有索引,每次查找都是遍歷。總結
這雖然是PHP 語言的一個小竅門,但在遍歷和對比數組的值上,如果需要對比值將其與鍵反轉的確比通常的值對值的比較效率要高得多。
例如,上面的函數二需要呼叫in_array 函數需要循環判斷是否在函數內;而函數三則僅僅判斷這個數組是否存在該鍵就可以了。加上數組鍵和值不同的組織索引方式,效率比想像的還高那就非常可以理解了。
<?php function microtime_float() { list($usec, $sec) = explode(" ", microtime()); return ((float)$usec + (float)$sec); } function array_diff2($array_1, $array_2) { $diff = array(); foreach ($array_1 as $k => $v1) { $flag = false; foreach ($array_2 as $v2) { if ($flag = ($v1 == $v2)) { break; } } if (!$flag) { $diff[$k] = $v1; } } return $diff; } function array_diff3($array_1, $array_2) { foreach ($array_1 as $key => $item) { if (in_array($item, $array_2, true)) { unset($array_1[$key]); } } return $array_1; } function array_diff4($array_1, $array_2) { $array_2 = array_flip($array_2); foreach ($array_1 as $key => $item) { if (isset($array_2[$item])) { unset($array_1[$key]); } } return $array_1; } ////////////////////////////// for($i = 0, $ary_1 = array(); $i < 5000; $i++) { $ary_1[] = rand(100, 999); } for($i = 0, $ary_2 = array(); $i < 5000; $i++) { $ary_2[] = rand(100, 999); } header("Content-type: text/plain;charset=utf-8"); $time_start = microtime_float(); array_diff($ary_1, $ary_2); echo "函数 array_diff 运行" . (microtime_float() - $time_start) . " 秒\n"; $time_start = microtime_float(); array_diff2($ary_1, $ary_2); echo "函数 array_diff2 运行" . (microtime_float() - $time_start) . " 秒\n"; $time_start = microtime_float(); array_diff3($ary_1, $ary_2); echo "函数 array_diff3 运行" . (microtime_float() - $time_start) . " 秒\n"; $time_start = microtime_float(); array_diff4($ary_1, $ary_2); echo "函数 array_diff4 运行" . (microtime_float() - $time_start) . " 秒\n"; ?>
相關推薦:
php 演算法之分割數組,不用array_chunk()_PHP教程
####################################### ####PHP 陣列排序方法總結#########以上是php的一些求差集方法與效能比較的詳細內容。更多資訊請關注PHP中文網其他相關文章!