我有两个列表A和B，B = A + C - D。所有元素都是唯一的，没有重复项。我该如何获得以下内容的列表：
（1）添加的新项目C
（2）删除的旧项目D
C和D的元素不超过10000个左右。
（1）添加的新项目C
（2）删除的旧项目D
C和D的元素不超过10000个左右。
6个回答
4
我认为数组的大小并不重要，除非你真的想专注于此操作的性能，即你想每单位时间执行特定数量的操作。如果你只是需要完成它，那么使用array_diff()似乎对我来说相当琐碎。
$a = array( 1, 2, 3, 4 );
$b = array( 1, 3, 5, 7 ); // 2 and 4 removed, 5 and 7 added
$c = array_diff( $b, $a ); // [5, 7]
$d = array_diff( $a, $b ); // [2, 4]
- Peter Bailey
5
我认为你对性能的相关性过于快速地进行了排除。如果结果数组每个有大约10k行，正如OP所说，那么输入数组每个至少也会这么大，甚至更大。尝试使用$a = range(1,10000)和$b = range(2,20000,2)创建10k元素输入数组并运行您的方法，对我来说需要大约14秒（对于Web请求而言太长了）。将其增加到20k元素输入数组，$a = range(1,20000)和$b = range(2,40000,2)，需要45秒。对于第一个案例，使用我发布的解决方案只需0.02秒，对于第二个案例则需要0.04秒。 - Kevin Vaughan
@Kevin - 我完全理解你所说的 - 即使在我发帖之前。但是谁说这是用于Web请求的呢？你的解决方案非常棒 - 这并不意味着你不能为一次性任务采用廉价和蛮力的方法。 - Peter Bailey
更不用说我在表现方面非常有资格。我认为说“我对此不屑一顾”是相当不准确的。 - Peter Bailey
@Peter - 说得对，但问题的标题是300k行列表。我等待array_diff在这样大小的输入上完成变得无聊（它仍在运行，已经超过11分钟了，我的CPU被占满），而我发布的解决方案仍然只需要<2秒。我认为array_diff解决方案太快地忽略了数组大小的相关性。即使这不是一个Web请求，谁想要测试每个测试用例都需要运行这么长时间的代码呢？ - Kevin Vaughan
似乎array_diff的速度问题是在5.2.4之后引入的错误(2009年初)：http://bugs.php.net/bug.php?id=47643，因此如果/当该错误被解决时，我的评论可能完全无关紧要。 链接的票证确实有一个解决方法，对于这种情况可以很好地工作，并且比我提供的解决方案更快。 - Kevin Vaughan
3
最有效的方法是首先对列表进行排序，尽可能少地访问数组元素。例如：
<?php
sort($a, SORT_NUMERIC);
sort($b, SORT_NUMERIC);
$c = array();
$d = array();
while (($currA = array_pop($a)) !== null) {
while (($currB = array_pop($b)) !== null) {
if ($currB == $currA) {
// exists in both, skip value
continue 2;
}
if ($currA > $currB) {
// exists in A only, add to D, push B back on to stack
$d[] = $currA;
$b[] = $currB;
continue 2;
}
// exists in B only, add to C
$c[] = $currB;
}
// exists in A only, for values of A < all of B
$d[] = $currA;
}
即使列表只有几百个元素，这个方法的速度比调用两次array_diff要快几个数量级。
- Kevin Vaughan
1
+1 为速度。我只想补充一点，这会破坏原始数组——所以如果这对 OP 很重要，他应该先复制它们。 - Peter Bailey
1
你说你已经有了两个文件A和B。
假设你正在运行Unix系统，这是最简单、最快的解决方案。
system("comm -13 A B > C");
system("comm -23 A B > D");
//read C and D in PHP
- Will Hartung
1
非常漂亮！对我来说运行得很好！！谢谢Will！ - Dave
0
function diffLists($listA,$listB) {
$resultAdded = array();
$resultRemoved = array();
foreach($listB AS $item) {
if (!in_array($item,$listA)) {
$resultAdded[] = $item;
}
}
foreach($listA AS $item) {
if (!in_array($item,$listB)) {
$resultRemoved[] = $item;
}
}
return array($resultAdded,$resultRemoved);
}
$myListA = array('item1','item2','item3');
$myListB = array('item1','item3','item4');
print_r(diffLists($myListA,$myListB));
这应该输出一个包含2个元素的数组。第一个元素是在列表B中添加的项目列表，第二个元素是在列表B中删除的项目列表。
- Dal Hundal
3
我不确定这种方法比仅使用
array_diff()更好在哪里？你最终会在这里调用大约600,000次in_array()。 - Tom Haigh@Tom - 我的第一反应是同意你的观点，因为这个解决方案中的每个foreach块都会重复使用array_diff。但是，我对10k和20k元素数组进行了一些基准测试，令人震惊的是，对于大型输入，foreach循环比array_diff运行得快得多。不过，它仍然比我发布的排序和搜索解决方案慢几个数量级。 - Kevin Vaughan
1啊，array_diff 目前在性能方面存在问题：http://bugs.php.net/bug.php?id=47643 - Kevin Vaughan
0
在B中搜索A的每个值（反之亦然）具有O(n^2)的复杂度。
对于大量数据，最好对每个列表进行排序O(n log n)，然后通过排序后的列表进行单次遍历，计算添加/删除的元素。（相对容易做到，因为您知道没有重复项。）
- David Gelhar
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接