我有两个列表A和B,B = A + C - D。所有元素都是唯一的,没有重复项。我该如何获得以下内容的列表:
(1)添加的新项目C
(2)删除的旧项目D
C和D的元素不超过10000个左右。
(1)添加的新项目C
(2)删除的旧项目D
C和D的元素不超过10000个左右。
$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]
最有效的方法是首先对列表进行排序,尽可能少地访问数组元素。例如:
<?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要快几个数量级。
你说你已经有了两个文件A和B。
假设你正在运行Unix系统,这是最简单、最快的解决方案。
system("comm -13 A B > C");
system("comm -23 A B > D");
//read C and D in PHP
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中删除的项目列表。
array_diff()
更好在哪里?你最终会在这里调用大约600,000次in_array()
。 - Tom Haigh在B中搜索A的每个值(反之亦然)具有O(n^2)的复杂度。
对于大量数据,最好对每个列表进行排序O(n log n),然后通过排序后的列表进行单次遍历,计算添加/删除的元素。(相对容易做到,因为您知道没有重复项。)