Linq选择匹配列表从其他列表性能

本文关键字：列表 性能 其他 选择 Linq | 更新日期: 2023-09-27 18:08:09

我有一个这样的类

public class Category 
{
   CategoryID
   List<Product> ProductList
}
public class Product 
{
   CategoryID
}

List<Category>约为15k行，List <Product>约为40k行。我正在用LINQ做这样的操作

CategoryList.ForEach(i =>
{
    i.ProductList = ProductList.Where(x => x.CategoryID == i.CategoryID).ToList();
});

我想知道是否有更好的实现性能。其他情况下数据可能会增加或减少

Linq选择匹配列表从其他列表性能

我认为使用并行是愚蠢的，当对算法进行简单的更改可以将其速度提高数千倍时。假设CategoryID具有GetHashCode()的体面实现，字典/查找的查找时间接近O(1)，而扫描列表的时间为O(n)。

两种可能的方法:

将类别转换为字典

假设类别有唯一的id，您可以使用:

var categoryById = categories.ToDictionary(c => c.CategoryID);
foreach(var product in products)
{
    var category = categoryById[product.CategoryID];
    category.Products.Add(product);
}

运行时为O(products.Count + categories.Count)，使用O(categories.Count)内存。

如果类别不是以空列表开始的，您可能需要创建它。

将产品转换为查找

var productsByCategory = products.ToLookup(product => product.CategoryID);
foreach(var category in categories)
{
    category.Products = products[category.CategoryID].ToList();
}

运行时为O(products.Count + categories.Count)，使用O(products.Count)内存。

由于通常有更多的产品比类别，这种方法将需要更多的内存。另一方面，查找可能不需要在类别对象中嵌入产品列表。

可以使用LINQ - PLINQ并行实现。通常PLINQ提高了LINQ的速度，因为它更有效地利用了所有可用的内核。

CategoryList.AsParallel().ForAll(i =>
     {
         i.ProductList = ProductList.AsParallel.Where(x => x.CategoryID == i.CategoryID).ToList();
     });

你也可以使用一个GroupJoin代替多个where:https://msdn.microsoft.com/en-us/library/bb397905.aspx

Parallel将为您提供高达nb的核心增强，而使用GroupJoin可以获得线性复杂度。

从@CodesInChaos

如果类别和产品的数量处于相同的规模，您将获得从二次型到线性运行时间的加速

在组织按类别分组的产品列表(如Dictionary<int, List<Product>>)时，您可能会获得性能。然后，您只需根据其键选择类别的产品列表，而不是对整个产品列表执行LINQ查询并生成新的子列表。

CategoryList.ForEach(i =>
{
    i.ProductList = ProductDict[i.CategoryID];
});

实际上在这种情况下最有效的解决方案是从ProductList中创建CategoryList。像这样:

CategoryList = ProductList
  .GroupBy(p=>p.CategoryID)
  .Select(
    g=>
      new Category{
        CategoryID=g.Key,
        ProductList = g.ToList()
      }
  );

如果CategoryList已经存在，您可以首先按CategoryID对产品进行分组，然后将分组后的产品与类别相关联。

var query =
    from p in ProductList
    group p by p.CategoryID
        into grouped        
    join c in CategoryList
        on grouped.Key equals c.CategoryID
    select new { c, grouped };

然后使用循环设置Category对象的ProductList字段。

foreach (var item in query)
    item.c.ProductList = item.grouped.ToList();

在测试性能后，我发现比我之前发布的更好的解决方案是:

    static List<Category> FilterList(List<Category> list, List<Product> ProductList)
    {
        Parallel.For(0, list.Count, i =>
        {
            list[i].ProductList = new List<Product>();
            for (int i2 = 0; i2 < ProductList.Count; i2++)
                if (ProductList[i2].CategoryID == list[i].CategoryID) list[i].ProductList.Add(ProductList[i2]);
        });            
        return list;
    }

然后是list = FilterList(list, products);

对于3,500,000操作，只需要200ms

相关文章：