最近公司在做一个项目，需要对爬取到的数据进行去重，方法就是根据数据的id，去除掉id重复的数据。

下面是这个方法的演化过程。

1. // 去重 
2. $arr_id = array(); 
3. $LeTVFeedList = array(); 
4. for ($i = 0; $i < count($arrFeedList); $i++){ 
5.     if(!in_array($arrFeedList[i]['id'], $arr_id)){ 
6.         $LeTVFeedList[] = $arrFeedList[i]; 
7.         $arr_id[] = $arrFeedList[i]['id']; 
8.     } 
9. } 

从上面的算法中可以看到，上面的算法用了两个数组，两个循环，所以它的时间复杂度为O(n^2)，空间复杂度为O(2n)。上面的算法，我们可以从in_array()入手，考虑下面的因素。

用数组的id作数组下标，来存储爬取到的数据值。

1. // 去重 
2. $tmp_arr = array(); 
3. for ($i = 0; $i < min(count($arrFeedList),10); $i++){ 
4.     $tmp_arr[$arrFeedList[$i]['id']] = $arrFeedList[$i]; 
5. } 
6. $arrLeTVFeedList = array(); 
7. foreach ($tmp_arr as $key => $value){ 
8.     $arrLeTVFeedList[] = $value; 
9. } 

这里用了两个循环，两个数组，时间复杂度是O(2n),空间复杂度是O(2n).后来又对循环进行了优化，变成如下代码：

1. // 去重 
2. $tmp_arr = array(); 
3. $arrLeTVFeedList = array(); 
4. foreach ($arrFeedList as $key => $value){ 
5.     if(!isset($tmp_arr[$key['id']])){ 
6.         $tmp_arr[$key['id']] = $value; 
7.         $arrLeTVFeedList[] = $value; 
8.     } 
9. } 

isset是速度要快于for循环，以上代码是最终版本。

Tags: 算法 过程

分享到：