• 尝试下自己设计求差集的函数?

    从求差集发现点东西
    服务器君一共花费 694.033 ms 进行了 4 次数据库查询,努力地为您提供了这个页面。
    广告很萌的

    前面我们了解了什么是数组的差集,并且试用了PHP自带的求差集函数 array_diff()。我们当然不会就此止步,我们需要更深入地探讨,才能挖掘到宝石。接下来,如果不用PHP自带的函数,让你自己实现一个求差集函数,你会怎么设计呢?

    • 一般思路嘛,就是用两重循环……外层循环遍历 array1,内层循环遍历 array2,如果发现相等的,循环跳出;如果不相等的,就保存到数组里面。最后返回差集数组,我写下来吧……

    设计的函数如下:

    function array_different($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;
    }
    
    • 那我来写个测试程序吧,来对比一下你写的函数与PHP自带的函数的效率。假设两个数组分别有 5000 个元素,那么两个函数的效率有多大差异呢?
    $array_1 = array();
    $array_2 = array();
    
    for($i = 0; $i <= 5000; $i++)
    {
    	$array_1[$i] = mt_rand(0, 100);
    	$array_2[$i] = mt_rand(0, 100);
    }
    /*
    foreach( $array_1 as $key => $val )
    {
    	echo $val.',';
    }
    echo '<br />';
    foreach( $array_2 as $key => $val )
    {
    	echo $val.',';
    }
    echo '<br />';
    */
    runtime(); //计时开始 
    $arr_diff = array_diff($array_1, $array_2);
    echo runtime(1); //计时结束并输出计时结果
    echo '<br />';
    foreach( $arr_diff as $key => $val )
    {
    	echo $val.',';
    }
    runtime(); //计时开始 
    $arr_diff2 = array_different($array_1, $array_2);
    echo runtime(2); //计时结束并输出计时结果  
    foreach( $arr_diff2 as $key => $val )
    {
    	echo $val.',';
    }
    
    function array_different($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 runtime($mode = 0) { 
    	static $t; 
        if(!$mode) { 
    		$t = microtime(); 
    		return; 
        } 
        $t1 = microtime(); 
        list($m0,$s0) = explode(" ",$t);
        list($m1,$s1) = explode(" ",$t1);
        return sprintf("%.3f ms",($s1+$m1-$s0-$m0)*1000); 
    } 
    

    程序运行结果:

    56.119 ms		// PHP自带的 array_diff($array_1, $array_2);
    2345.672 ms		// 自定义函数 array_different($array_1, $array_2)
    
    • 竟然差了50倍左右的效率啊……我写的这个函数效率真是惨不忍睹。等等我改下函数,应该有更好的方法……比如遍历array1,然后判断array1里的每个元素是否在array2中,如果在,就把这个元素在array1中删除:
    function array_different($array_1, $array_2)
    {
    	foreach ($array_1 as $key => $val) {
    		if (in_array($val, $array_2, true)) {
    			unset($array_1[$key]);
    		}
    	}
    	return $array_1;
    }
    

    运行测试程序:

    46.165 ms		// PHP自带的 array_diff($array_1, $array_2);
    149.485 ms		// 自定义函数 array_different($array_1, $array_2)
    
    • 这次效率就高很多了,就比原生的慢3倍左右,从50倍进步到3倍了。其实还有一种方法,甚至还能超越原生的效率。我们用 array_flip() 函数将 array2 的数组键值调换,那么思路就简单了:如果键值调换后的$array2[$k]存在,那么把这个 array1 中第 key 个元素直接删掉即可。
    function array_different($array_1, $array_2)
    {
    	$array_2 = array_flip($array_2);//将数组键值调换
    	foreach ($array_1 as $key => $val) {
    		if (isset($array_2[$val])) {
    			unset($array_1[$key]);
    		}
    	}
    	return $array_1;
    }
    

    运行测试程序:

    48.881 ms		// PHP自带的 array_diff($array_1, $array_2);
    3.443 ms		// 自定义函数 array_different($array_1, $array_2)
    

    看,比原生的还快 10 多倍呢。为什么能那么神奇?

    • 我明白了,因为数组的键是用 HASH 组织的,查找是相当的快,效率达O(1)。而前面我写的函数里,value 只是由 key 组织存放,本身没有索引,每次查找都是遍历。没好好利用数组是哈希表的特性,效率就差异那么大了。后面我们再挖据点东西。
更多 推荐条目

Welcome to NowaMagic Academy!

现代魔法 推荐于 2013-02-27 10:23   

本章最新发布
随机专题
  1. [移动开发] Android加载器Loaders 5 个条目
  2. [移动开发] Android Studio的使用技巧 4 个条目
  3. [数据结构] 图的定义 1 个条目
  4. [PHP程序设计] PHP数组探索 4 个条目
  5. [PHP程序设计] PHP与函数式编程 1 个条目
  6. [移动开发] Android 开发调试工具 ADB 3 个条目
  7. [Python程序设计] Django 入门知识浅介 10 个条目
  8. [移动开发] 简单了解Android Fragment 3 个条目
  9. [移动开发] Activity 初步知识 2 个条目
  10. [JavaScript程序设计] 关于HTTP Keep-Alive 6 个条目
  11. [移动开发] 从代码角度去认识 Activity 4 个条目
  12. [数据库技术] SQL基础语法 1 个条目
窗口 -- [博客]