分类排序优化

本文关键字：优化 排序 分类 | 更新日期: 2023-09-27 18:28:14

问题：将项（T）排序到bucket（ConcurrentBag）中的最佳方式是什么？

好吧，所以我还没有上算法课，所以我不确定我遇到的问题的最佳方法。

前提条件：

  • 每个bucket都有一个唯一的标识符（在每个sBucket中）
  • 每个sBucket都有一个唯一的标识符
  • 每个项目都有一个唯一的标识符
  • 每个项目都有一个与它所在的bucket相对应的属性（bucketId）属于
  • 每个项目都有一个属性（sBucketId），对应于它属于superBucket
  • Bucket和sBucket id是唯一的
  • 我有一个ConcurrentBag，里面有我想分类的项目水桶
  • 有几百件物品
  • 有几十个水桶
  • 有3个超级铲斗，其中包含铲斗
  • 每个超级bucket包含相同的bucket，但有不同的bucket桶中的项目

我目前正在通过对项目集合的Parallel.foreach循环使用暴力，使用linq将项目的bucketId与每个单独的bucket进行比较。这是难以置信的缓慢和繁琐，所以我想找到一个更好的方法。

我考虑过根据它们的超级Bucket然后Bucket对项目进行排序，然后遍历每个超级Bucket->Bucket来插入项目。这应该是我走的路吗？

感谢您提供的任何帮助。

当前代码示例

ConcurrentBag<Item> items ...
List<SuperBuckets> ListOfSuperBuckets ...

Parallel.ForEach(items, item =>
{
   ListOfSuperBuckets
       .Where(sBucket => sBucket.id == item.sBucketId)
       .First()
       .buckets
       .Where(bucket => bucket.id == item.bucketId)
       .First()
       .items
       .Add(item);
});

分类排序优化

我不会对此使用并行性，但有很多选项。

var groupedBySBucket = ListOfSuperBuckets
    .GroupJoin(items, a => a.id, b => b.sBucketId, (a,b) => new
        {
            sBucket = a,
            buckets = a.buckets
                .GroupJoin(b, c => c.id, x => x.bucketId, (c, x) => new
                    {
                        bucket = c,
                        items = x
                    });
        });
foreach (var g in groupedBySBucket)
{
    // We benefit here from that the collection types are passed by reference.
    foreach (var b in g.buckets)
    {
        b.bucket.AddRange(b.items);
    }
}

或者，如果这对你来说太多的代码，这是可以比较的。

var groupedByBucket = ListOfSuperBuckets
    .SelectMany(c => c.buckets, (a,b) => new { sBucketId = a.id, bucket = b })
    .GroupJoin(items, a => new { a.sBucketId, bucketId = a.bucket.id }, b => new { b.sBucketId, b.bucketId }, (a, b) => new
            {
                bucket = a.bucket,
                items = b
            }));
foreach (var g in groupedByBucket)
{
    // We benefit here from that the collection types are passed by reference.
    g.bucket.AddRange(b.items);
}

这也是假设CCD_ 1是给定的。如果这只是实现的一个工件，那么还有一种更简单的方法。这将生成列表。

当然，要小心，因为这些是不同的——这一个不会有任何空的存储桶，但第一个实现可以。我们还在创建新的bucket，而第一个实现没有；如果我们需要的话是好的，如果你已经在其他地方创建了它们，那就不好了。当然，第一个可以很容易地修改来创建它们。

var ListOfSuperBuckets = items
    .GroupBy(c => new { c.bucketId, c.sBucketId })
    .GroupBy(c => c.Key.sBucketId)
    .Select(c => new SuperBucket
        {
            id = c.Key,
            buckets = c.Select(b => new Bucket
                {
                    id = b.Key.bucketId,
                    items = b.ToList()
                }).ToList()
        })
    .ToList();

值得一提的是，所有这些ToList调用都是为了保留我认为您拥有的合同。如果你不需要它们，你可以通过关闭它们来从LINQ的延迟执行中受益。这实际上是一个如何使用代码的问题，但这值得考虑。

您应该使用Dictionary，这样您就可以按ID查找bucket和SuperBuckets，而不是搜索它们。

SuperBucket应该有一个Dictionary<id_type,Bucket>，可以用来按ID查找bucket，并且应该将SuperBuckets保留在Dictionary<id_type,SuperBucket>中。（id_type是您的ID类型——可能是字符串或int，但我无法从您的代码中分辨出来）

如果您不想修改现有的类，那么构建一个Dictionary<id_type, Dictionary<id_type, Bucket>>并使用它。

相关文章：