求高手一个算法

Question

有两个二维数组$a=array(
array('id'=>'1','name'=>'a','url'=>'c'),
array('id'=>'2','name'=>'aa','url'=>'cc'),
        array('id'=>'3','name'=>'aaa','url'=>'ccc')
);$b=array(
array('name'=>'aa','url'=>'cc'),
array('name'=>'a','url'=>'c')
);如何能够得到array('id'=>'3','name'=>'aaa','url'=>'ccc')呢？意思就是说，比较两个数组中除了id的项，如果数组a中的值在数组b中不存在，则筛选出来，不希望使用嵌套foreach，每个数组中都有好几万条记录，所以效率是个问题。请教各位，还望有思路的朋友赐教。

Answer 1

$t=array();
foreach($b as $vl)
        $t[$vl['name'].$vl['url']]=$vl;foreach($a as $k=>$v)
     if(!$t[$v['name'].$v['url']]) unset($a[$k]);
 
print_r($a);

Answer 2

从算法时间度上考量
 if(!$t[$v['name'].$v['url']]) 是查询数组的键，同样也是查询列表，复杂度为 n
放到循环内就是 n*n
加上准备工作（构造工作数组）的 n
是 O(n+n*n)而直接嵌套两层的时间复杂度为 O(n*n)所以：虽然 #1 的算法的实际效率要高于 嵌套两层的两层循环，但这并没有理论依据
结论：理论要与实践相结合。实践是检验真理的唯一标准

Answer 3

有疑问，，这判断相当于isset，O(1)吧？，如果刻意构造 $v[]……$v[] 能否使得hashTable退化为链表

Answer 4

isset 判断一个值是否在列表中
并无所谓是键还是值，也无所谓你的数据是如何组织的
总之，他是在列表中查询，最坏的情况就是检索到列表的最后一个元素其实 isset 与 in_array 是相似的就有人在我的某个类似问题中（使用了 in_array）提出了质疑
很简单，仅就算法而言，并不能因为是php内部实现的，就不计算在内哈希表的性能优于线性表，但在时间复杂度上还是一样的
当然并不排除我的高中学历影响了对理论知识的理解

Answer 5

同意in_array是需要遍历的但isset绝大部分情况下，并不需要检索到最后一个元素，个人理解，这里的isset根据key值，直接定位到数组元素，，下面的代码，执行时间完全不是一个量级的
相差万倍，恰好是$arr的元素规模，in_array遍历缘故
$arr = array();
for($i=1;$i<=1e5;$i++)
{
$arr[md5($i)] = md5($i);//string key==value，
}//构造500个待查找元素，，，大概一半能找到一半不能
$search = array();
for($i=0;$i<500;$i++)
{
$search[] = md5(rand(1, 2e5));
}$time[] = microtime(TRUE);
foreach($search AS $v)
{
in_array($v, $arr);
}
$time[] = microtime(TRUE);
foreach($search AS $v)
{
isset($arr[$v]);
}
$time[] = microtime(TRUE);print_r($time);

Answer 6

你这个例子不错，但不能说明什么问题关联数组的键在内部使用哈希表实现的，而用户数组只能用不排序的线性表存储，除非你再显式的对数组排序
哈希表的查找要远快于二分法，何况php怎么能认定用户数组是有序的呢？

Answer 7

for($i=0;$i<500;$i++)
{
    $search[]    = md5("s".($i+1));//1
}
==========================
for($i=0;$i<500;$i++)
{
    $search[]    = md5(($i+1));//2
}构造不同的被查找元素，isset所费时间基本不受影响，但是in_array在遍历，时间相差很大这就不能解释“是查询数组的键，同样也是查询列表，复杂度为 n”。。如果是n，必定会和下面说的in_array一样，会受影响in_array遍历，将元素构造成找不到的【每次都遍历一遍数组才能判断】，和将元素构造成数组前面几个元素，结果相差就很大数组存储内部确实有双向列表来保存数组前后关系【否则也不能顺序遍历关联数组】，但结构还key=>value的hashTable

Answer 8

你说的一点都不错！但是实现算法的基础也是要考虑的
总所周知，汇编代码与机器语言是1:1.2，C与汇编是1.3:1
到了c++呢？何况 php 还是解释型语言。因此
在所有的算法中都是不计计算机系统内置的查表算法的开销的我以我是在钻牛角尖
所以我们讨论是应该有一个统一的基础的
到目前为止，LZ并未出现，还不知道他在想什么。要钻牛角尖，我有兴趣奉陪

Answer 9

都说哈希的时间复杂度度是 O(1)，但我认为是错误的，按哈希算法的说明
每个键值映射成一个值，访问时直接计算偏移进行定位
当键值相同时将采取循序列表方式保存数据
O(1)只反映了第一种情况，虽然是大部的
却没有反映出第二种情况在时间度算法说明中
for(i=0;i<n；i++)
  if(i==0) break;
依然是要算作 n 的

Answer 10

感谢各位的讨论，学到不少东西。根据我的实际情况，最终采用如下$t=array();
foreach($b as $vl)
        $t[$vl['name'].$vl['url']]=$vl;foreach($a as $k=>$v)
     if(isset($t[$v['name'].$v['url']])) unset($a[$k]);
     
print_r($a);isset检索key速度确实是很快的，以上思路其实是构建了一个二维数组的array_flip，然后isset利用hash检索key，在我的情况中，确实比in_array快了许多。感谢jordan102，amani11，xuzuning的赐教，谢谢。