在基于某些(非全部)属性值比较列表内容时,嵌套foreach的替代方法

Question

作为这个问题的一部分,反复指出我使用类似于此的代码有一个O(n ^ 2)问题...

public class Foo
{
  public string IdentityValue {get;set;}  
  public string Prop1 {get;set;}
  public string Prop2 {get;set;}

}

List<Foo> itemSet1 = GenerateLargeItemSet(); //makes a large list, > 5000 items for example
List<Foo> itemSet2 = GenerateLargeItemSet();

foreach (var itemFromSet1 in itemSet1)
{

  //does a corresponding item exist in itemSet2?
  var itemSet2Item = itemSet2.FirstOrDefault(i => i.IdentityValue == itemFromSet1.IdentityValue);

  if (itemSet2Item != null)
  { 
    //do stuff to create item in the persistent store
  }
  else
  {
    //do stuff to update item in the persistent store
  }
}

原谅字符串比较和并行化的考虑,有没有便宜和通用(对象可以是T型,和身份属性可能是别的东西)的方式,以减少的O这个(N ^ 2)性质是什么？

Answer 1

解决方案之一是使用具有复杂O(n)的Enumerable.Join方法

List<Foo> itemSet1 = GenerateLargeItemSet(); //makes a large list, > 5000 items for example
List<Foo> itemSet2 = GenerateLargeItemSet();

// O(n)
var joinedSet = itemSet1.Join(itemSet2, s1 => s1.IdentityValue, s2 => s2.IdentityValue, (f1, f2) => f1).ToList();

// O(n)
foreach (var joinedItem in joinedSet)
{
    //do stuff to create item in the persistent store
}

// O(n)
var unjoinedSet = itemSet1.Except(joinedSet);

// O(n)
foreach (var unjoinedItem in unjoinedSet)
{
    //do stuff to update item in the persistent store
}