logo标签列表

php array_intersect() 效率

php
10

考虑下面的脚本。两个数组仅有三个值。使用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登录，则该应用程序将获取他的朋友列表，并查找是否有任何朋友在我的应用程序中进行了评论，并向他显示。大致上一个朋友在Facebook上可能有200到300个朋友，而数据库中有超过1000个记录。我需要找到一种有效的方式来高效地做到这一点……

@learnfromothers：你尝试过在包含1000个以上数值的数组上尝试相同的操作吗？ - Sujit Agarwal
2
为什么不自己找出答案呢？进行基准测试。通常情况下，除非您对应用程序进行了分析并发现 array_intersect 的调用显着减慢了应用程序的速度，否则效率并不重要。显著减慢的程度取决于您的要求。 - Gordon
@Coding Freak，我还没有尝试过那个方法。我正在开发一个应用程序。如果有人使用Facebook登录来登录，应用程序将获取他的好友列表，并查找是否有任何朋友在我的应用程序中发表过评论，并向他展示出来。大致上，一个朋友在Facebook上可能有200到300个好友，而数据库中有超过1000条记录。我需要高效地找到这些信息，你有什么建议吗？ - learnfromothers
@Gordan，有什么解决方案吗？我正在开发一个应用程序。如果一个人使用Facebook登录，则该应用程序将获取他的好友列表，并查找是否有任何朋友在我的应用程序中发表过评论，并向他展示。大致上，一个朋友在Facebook上可能有200到300个好友，而数据库中有1000多条记录。我需要高效地找到这个问题的解决方法...... - learnfromothers
但是你怎么能确定你会遇到只有200到300个朋友的人呢？我在Facebook上看到过拥有超过5K+朋友的个人资料。 - Sujit Agarwal
@Coding Freak，上面有很多人超过5K。我接受这个事实。但是有没有解决方案呢？如果我们采用5K，那么我们需要更高的效率。在这种最坏情况下，有什么可以做来提高效率呢？ - learnfromothers
5个回答
24

可以通过构建第二个数组中搜索值的集合来实现交集，并且在集合中查找可以非常快速，平均时间基本上是恒定的。因此，整个算法的运行时间可以为O(n)。

另一种方法是对第二个数组进行排序（O(n log n)）。由于在排序后的数组中查找的运行时间为O(log n)，因此整个算法的运行时间应该为O(n log n)。

根据我刚刚运行的（简短、不科学）测试，在php的array_intersect函数中似乎是这样的：

Performance of array_intersect

这是我用来测试的代码。正如您所看到的，对于输入大小只有1000的情况，您无需担心。

@phinag 是的，你说得对...有没有什么解决方案...我正在开发一个应用程序。如果一个人使用Facebook登录，那么应用程序将获取他的好友列表，并查找是否有任何朋友在我的应用程序中发表评论，并向他展示。大致上，一个朋友在Facebook上可能有200到300个朋友，而数据库中有1000多条记录。我需要高效地找到如何做到这一点。 - learnfromothers
@learnfromothers 对于少于一千个元素，array_intersect 不会成为性能问题。 - phihag
非常感谢您的努力，我对您的回答非常满意。再次感谢。 - learnfromothers
@phihag 如果你还记得的话，你用的是什么工具得到那个图形的？ - vicch
@vicch，非常抱歉，我不记得并且找不到生成图表的代码（另一方面，获取数据的代码已经在答案中链接了）。这可能是gnuplot或matplotlib。但我不能排除LibreOffice甚至手写脚本的可能性。 - phihag
@phihag 谢谢。我以为它是一种可以直接生成图形的 PHP 基准库 / 扩展。 - vicch
18

array_intersect函数在比较数组的值之前会并行排序它们的值（请参见在源文件array.c中使用zend_qsort）。仅进行排序就需要每个数组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);
5
我找到的最快解决方案是：
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'
2
来自评论区：嗨，请不要只回答源代码。请尝试提供有关您解决方案如何工作的良好描述。请参阅：如何撰写好答案？。谢谢。 - sɐunıɔןɐqɐp
2

根据您上述的陈述，我建议您实现缓存机制。这样可以减轻数据库负担并加快应用程序的速度。我还建议您随着数据量的增加来分析array_intersect的速度表现。您可以通过简单地在系统时间调用中包装该调用并计算差异来完成此操作。但是我建议您使用真正的分析器以获得良好的数据。

2
@learnfromothers：分析器是一种帮助您测量应用程序性能的应用程序。例如，可以查看Xdebug：http://www.xdebug.org/docs/profiler，或者如果您使用Zend Studio，则可以使用内置的分析器：http://files.zend.com/help/Beta/Zend_Studio_8_0/working_with_the_profiler.htm。 - inquam
谢谢你，@inquam。我能否使用一些哈希函数将值存储在数据库中，以便搜索可以有所限制。这是正确的方法吗？ - learnfromothers
@learnfromothers：访问数据的最佳方式取决于多种因素。数据的布局、读写频率等等。但是，如果有一个分析器，您可以快速查看不同方法和特定更改如何影响性能。 - inquam
@inquam 再次感谢...但是您是否知道当前最佳的数据高效存储和检索方法，以及像Facebook等主要网站使用的方法？ - learnfromothers
@laernfromothers：我知道，例如Facebook非常依赖数据缓存。我认为他们使用了修改版的memcache。它将数据存储在内存中，速度非常快，相比每次从数据库获取数据要快得多。此外，我认为他们会预先计算一些关键信息，这样你就不必每次都进行计算。比如你的朋友列表，你可以将其编译一次并存储在缓存中。然后每次需要时都可以从缓存中检索它。只有在添加或删除好友时才需要重新构建。 - inquam
@inquam 非常感谢你，今天从你这里学到了很多东西......再次感谢你提供的精彩答案.......... - learnfromothers
1

我正在实现这个简单的代码，比较array_intersect和array_intersect_key函数。

$array = array();
    for( $i=0; $i<130000; $i++)
        $array[$i] = $i;
    for( $i=200000; $i<230000; $i++)
        $array[$i] = $i;
    for( $i=300000; $i<340000; $i++)
        $array[$i] = $i;

    $array2 = array();
    for( $i=100000; $i<110000; $i++)
        $array2[$i] = $i;
    for( $i=90000; $i<100000; $i++)
        $array2[$i] = $i;
    for( $i=110000; $i<290000; $i++)
        $array2[$i] = $i;

    echo 'Intersect to arrays -> array1[' . count($array) . '] : array2[' . count($array2) . '] ' . '<br>';
    echo date('Y-m-d H:i:s') . '<br>';
    $time = time();
    $array_r2 = array_intersect_key($array,$array2);
    echo 'Intercept key: ' . (time()-$time) . ' segs<br>';
    $time = time();
    $array_r = array_intersect($array,$array2);
    echo 'Intercept: ' . (time()-$time) . ' segs<br>';

结果...

Intersect to arrays -> array1[200000] : array2[200000] 
2014-10-30 08:52:52
Intercept key: 0 segs
Intercept: 4 segs

在比较array_intersect和array_intersect_key的效率时，我们可以看到带有键的拦截速度更快。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接