c# - 基于某些(不是全部)属性值比较列表内容时嵌套 foreach 的替代方法

Question

作为 this 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 类型，Identity 属性可能是其他类型)的方法来减少它的 O(n^2) 性质？

Answer 1

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

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
}