需要更快的解决方案.查询大型对象列表

Question

我正在寻找一个更快的解决以下问题的方法。

我有三个不同商店的商品清单。我想创建一个包含三个商店中所有可用产品的唯一列表，以及一个出现在多个商店中的唯一产品列表。

class Product{
    public int Id;
    // 
    public Product(int id)
    {
        this.Id = id;
    }
}
List<Product> store1 = new List<Product>();
List<Product> store2 = new List<Product>();
List<Product> store3 = new List<Product>();
List<Product> allUniqueProducts = new List<Product>();
List<Product> moreThanOneStore= new List<Product>();

用任意值填充列表

for(int i=0;i<10000;i++){
    store1.Add(new Product(i));
    store2.Add(new Product(i+2000));
    store3.Add(new Product(i+5000));
}

这是我的解决方案，但是当列表很大(在10,000左右)时，这段代码运行得很慢。

processStoreList(store1);
processStoreList(store2);
processStoreList(store3);
void processStoreList( List<Product> storeList ){
    foreach ( Product pd in storeList ){
        if ( !( allUniqueProducts.Count( x => x.Id == pd.Id ) > 0 ))
            allUniqueProducts.Add(pd);
        else if ( !( moreThanOneStore.Count( x => x.Id == pd.Id ) > 0 ))
            moreThanOneStore.Add(pd);
     }
}

有什么建议吗?

Answer 1

您应该使用Dictionary<int, Product>而不是List<Product>。

这样，ContainsKey将是O(1)而不是O(n)

Answer 2

考虑使用HashSet而不是List。需要使用IEqualityComparer来确保具有相同id的两个Product被认为是相同的。

        public class ProductEqualityComparer : IEqualityComparer<Product>
        {
            public bool Equals(Product x, Product y)
            {
                return x.Id == y.Id;
            }
            public int GetHashCode(Product obj)
            {
               return obj.Id.GetHashCode();
            }
        }
        static void Main(string[] args)
        {
            HashSet<Product> allUniqueProducts = 
                new HashSet<Product>(new ProductEqualityComparer());

Answer 3

您可以将所有项添加到HashSetHashSet。如果条目已经存在，则Add Method返回false，这允许您检测条目是否出现了不止一次。你需要一个eququalitycomparerproduct#;Id .

var allUniqueProducts = new HashSet<Product>(byIdComparer);
var moreThanOneStore = new HashSet<Product>(byIdComparer);
foreach (var product in store1.Concat(store2).Concat(store3))
{
    if (!allUniqueProducts.Add(product))
    {
        moreThanOneStore.Add(product);
    }
}

Answer 4

System.Collections.Generic.Dictionary是。net 2.0 -用Linq代替。

Enumerable.GroupBy使用哈希集合执行分组。

IEnumerable<IGrouping<int, Product>> groups = store1
   .Concat(store2)
   .Concat(store3)
   .GroupBy(prod => prod.Id);
List<Product> allProducts = groups
  .Select(g => g.First())
  .ToList();
List<Product> moreThanOneStoreProducts = groups
  .Where(g => g.Skip(1).Any())
  .Select(g => g.First())
  .ToList();

如果你想(以后)使用这些id在组列表中查找组，请使用Enumerable.ToLookup而不是Enumerable.GroupBy。

ILookup<int, Product>> lookup = store1
   .Concat(store2)
   .Concat(store3)
   .ToLookup(prod => prod.Id)
List<Product> someGroup = lookup[3].ToList();

Answer 5

通过在列表上使用Count()方法，您将使它循环遍历集合中的所有项。这是非常耗时的。使用Dictionary<TKey,TItem>将使用键进行查找，这将更快。

void Run3() {
  var stores = new List<List<Product>>() { store1, store2, store3 };
  var all = new Dictionary<int, Product>();
  var multi = new Dictionary<int, Product>();
  foreach (var store in stores) {
    foreach(var product in store) {
      if (all.ContainsKey(product.Id))
        multi[product.Id] = product;
      else
        all[product.Id] = product;
    }
  }
}