基于某些（不是全部）属性值比较列表内容时嵌套 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 类型，Identity 属性可能是其他类型）的方法来减少 O(n^2) 的性质这个？

Answer 1

您可能会发现使用 HashSet 可以提高性能。

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

        foreach (var itemFromSet1 in itemSet1)
        {
            //does a corresponding item exist in itemSet2?
            if (itemSet2.Contains(itemFromSet1))
            {
                //do stuff to update item in the persistent store
            }

            //do stuff to create item in the persistent store
        }

Answer 2

其中一个解决方案是使用 Enumerable.Join method which have complextiy 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
}

Answer 3

一种众所周知的提高数据库查询速度的方法是创建索引。同样的原则也适用于此。但什么是索引？它只是一种允许快速搜索的数据结构。在 BCL 中，这种结构称为 Dictionary。所以你可以使用这样的东西，它的时间复杂度为 O(N)

如果值在集合中是唯一的

var item2Index = itemSet2.ToDictionary(item => item.IdentityValue);

如果没有

var item2Index = itemSet2.GroupBy(e => e.IdentityValue)
    .ToDictionary(g => g.Key, g => g.First());

然后

foreach (var itemFromSet1 in itemSet1)
{
    //does a corresponding item exist in itemSet2?
    Foo itemSet2Item;
    if (!item2Index.TryGetValue(itemFromSet1.IdentityValue, out itemSet2Item))
    { 
        //do stuff to create item in the persistent store
    }
    else
    {
        //do stuff to update item in the persistent store
    }
}

如果您只想检查第二组中的重复项，但实际上不需要重复项，那么您可以使用简单的 HashSet（另一种用于快速查找的 BCL 数据结构）

var item2Keys = new HashSet<string>(itemSet2.Select(e => e.IdentityValue));
foreach (var itemFromSet1 in itemSet1)
{
    //does a corresponding item exist in itemSet2?
    if (!item2Keys.Contains(itemFromSet1.IdentityValue))
    { 
        //do stuff to create item in the persistent store
    }
    else
    {
        //do stuff to update item in the persistent store
    }
}

Answer 4

您可以先创建 Dictionary<TKey, TValue>，然后使用它几乎提供的快速查找 O(1) :

 List<Foo> itemSet1 = GenerateLargeItemSet(); //makes a large list, > 5000 items for example
Dictionary<string, Foo> itemSet2 = GenerateLargeItemSet().ToDictionary(i => i.IdentityValue);

//O(N)
foreach (var itemFromSet1 in itemSet1)
{
  //O(1)   
  if (!itemSet2.ContainsKey(itemFromSet1.IdentityValue))
  { 
     //do stuff to create item in the persistent store
  }
  else
  {
    //do stuff to update item in the persistent store
  }
}

基于某些（不是全部）属性值比较列表内容时嵌套 foreach 的替代方法

Alternatives to nested foreach when comparing list contents based on some (not all) property values

c#

big-o

foreach

基于某些（不是全部）属性 值比较列表内容时嵌套 foreach 的替代方法

Alternatives to nested foreach when comparing list contents based on some (not all) property values

c#

big-o

foreach

基于某些（不是全部）属性值比较列表内容时嵌套 foreach 的替代方法