php array_intersect()效率

Question

考虑下面的脚本.两个只有三个值的数组.当我使用array_intersect()比较这两个数组时.结果很快.

    <?php
$arrayOne = array('3', '4', '5');
$arrayTwo = array('4', '5', '6');

$intersect = array_intersect($arrayOne, $arrayTwo);

print_r($intersect );

?>

我的问题是array_intersect()的效率是多少.是否我们比较两个都有1000个值的数组.会产生更好的结果.....我们需要使用一些哈希函数来处理快速找到常用值这将是有效的??? ..我需要你的建议...

我正在做一个应用程序.如果有人来登录并使用facebook login.then应用程序将获取他的朋友列表,并查找是否有任何朋友在我的应用程序之前评论并显示给他.大概一个朋友可能在Facebook有200到300个朋友,db有超过1000条记录.我需要找到有效的我怎么能这样做.......

Answer 1

可以通过在第二阵列中构造一组搜索值来实现交集,并且可以使得在集合中查找以使其平均花费基本恒定的时间.因此,整个算法的运行时间可以在O(n).

或者,可以对第二个数组(in O(n log n))进行排序.由于查找已排序的数组中有运行时O(log n),因此整个算法应该具有运行时O(n log n).

根据我刚刚运行的(简短的,不科学的)测试,这似乎是php的情况array_intersect:

这是我用来测试它的代码.如您所见,对于小至1000的输入大小,您无需担心.

Answer 2

array_intersect并行比较它们的值(见使用前排序阵列zend_qsort中源文件array.c).对于每个阵列,这仅需要O(n ·log n).那么实际的交点只需要线性时间.

根据数组中的值,您可以在线性时间内实现此交集而无需排序,例如:

$index = array_flip($arrayOne);
foreach ($arrayTwo as $value) {
    if (isset($index[$value])) unset($index[$value]);
}
foreach ($index as $value => $key) {
    unset($arrayOne[$key]);
}
var_dump($arrayOne);

Answer 3

我发现的最快的解决方案：

function arrayIntersect($arrayOne, $arrayTwo) {
        $index = array_flip($arrayOne);
        $second = array_flip($arrayTwo);

        $x = array_intersect_key($index, $second);

        return array_flip($x);
}

我所做的测试如下所示：

function intersect($arrayOne, $arrayTwo)
{
    $index = array_flip($arrayOne);
    foreach ($arrayTwo as $value) {
        if (isset($index[$value])) unset($index[$value]);
    }
    foreach ($index as $value => $key) {
        unset($arrayOne[$key]);
    }

    return $arrayOne;
}

function intersect2($arrayOne, $arrayTwo)
{
    $index = array_flip($arrayOne);
    $second = array_flip($arrayTwo);

    $x = array_intersect_key($index, $second);

    return array_flip($x);

}

for($i =0; $i < 1000000; $i++) {
    $one[] = rand(0,1000000);
    $two[] = rand(0,100000);
    $two[] = rand(0,10000);
}

$one = array_unique($one);
$two = array_unique($two);

$time_start = microtime(true);
$res = intersect($one, $two);
$time = microtime(true) - $time_start;

echo "Sort time $time seconds 'intersect' \n";


$time_start = microtime(true);
$res2 = array_intersect($one, $two);
$time = microtime(true) - $time_start;

echo "Sort time $time seconds 'array_intersect' \n";


$time_start = microtime(true);
$res3 = intersect2($one, $two);
$time = microtime(true) - $time_start;

echo "Sort time $time seconds 'intersect2' \n";

php 5.6 的结果：

Sort time 0.77021193504333 seconds 'intersect' 
Sort time 6.9765028953552 seconds 'array_intersect' 
Sort time 0.4631941318512 seconds 'intersect2'