如何获得不同类型集合之间的匹配？

我认为这需要O(A x B)时间来执行。如何获得不同类型集合之间的匹配？

（其中A是collectionA和B的大小是collectionB的大小）

对吗？

IEnumerable<A> GetMatches(IEnumerable<A> collectionA, IEnumerable<B> collectionB) 
{ 
    foreach (A a in collectionA) 
     foreach (B b in collectionB) 
      if (a.Value == b.Value) 
       yield return a; 
}

是否有更快的方式来执行此查询？（可能使用LINQ？）

来源

2011-08-19 asmo

Enumerable.Intersect不幸的是，不幸的是，你不会像两种不同的类型（A和B）进行比较一样工作。

这将需要一点点处理，以获得可行的相交呼叫。

您可以分阶段做到这一点：

IEnumerable<A> GetMatches(IEnumerable<A> collectionA, IEnumerable<B> collectionB) 
    where A : ISomeConstraintWithValueProperty 
    where B : ISomeOtherConstraintWithSameValueProperty 
{ 
    // Get distinct values in A 
    var values = new HashSet<TypeOfValue>(collectionB.Select(b => b.Value)); 

    return collectionA.Where(a => values.Contains(a.Value)); 
}

注意，这将返回重复，如果collectionB包含重复（但不collectionA），所以它会比你的循环代码稍有不同的结果。

如果你想要独一无二的比赛（只有一个返回），你可以改变最后一行：如果你的数据是

return collectionA.Where(a => values.Contains(a.Value)).Distinct();

来源

2011-08-19 16:22:14

我建议你倒车时用，即消耗'collectionB'急切地工作，其中集合，然后流'collectionA' - 只是因为在更好地满足与LINQ到Objects的其他部分所做的一样。 –

@Jon：好点 - 也注意到了我在那里的一个bug（为了这个工作，HashSet需要是对值的散列，而不是对象本身......）那更多的是你在想什么？ –

该解决方案的复杂性如何？ – asmo

你可以试试它具有复杂度为O（M + N）以下的交集算法排序，或O（nlogn），否则，无需消耗额外的内存：

private static IEnumerable<A> Intersect(A[] alist, B[] blist) 
    { 
     Array.Sort(alist); 
     Array.Sort(blist); 

     for (int i = 0, j = 0; i < alist.Length && j < blist.Length;) 
     { 
      if (alist[i].Value == blist[j].Value) 
      { 
       yield return alist[i]; 
       i++; 
       j++; 
      } 
      else 
      { 
       if (alist[i].Value < blist[j].Value) 
       { 
        i++; 
       } 
       else 
       { 
        j++; 
       } 
      } 
     } 
    }

来源

2011-08-19 17:01:37 andriys

如何获得不同类型集合之间的匹配？

回答

相关问题