从列表中获取优先项并将它们插入到给定位置的同一列表中 - C#

Question

我有一个包含50个已排序项的列表，在其中有几个是优先级较高的（假设它们的标志设置为1）。

默认情况下，我需要按照日期先显示最新的项目，但优先级项目应该在一定数量的记录后出现。如下所示：

索引0：项目
索引1：项目
索引2：优先级项目 （从此位置插入优先级项目）
索引3：优先级项目
索引4：优先级项目
索引5：项目
索引6：项目

预定义了应插入优先级项目的索引“x”。

为了实现这一点，我正在使用以下代码：

这些是我经过排序的50个项目

var list= getMyTop50SortedItems();

获取所有优先级项目并将其存储在另一个列表中。

var priorityItems = list.Where(x => x.flag == 1).ToList();

从主列表中筛选出优先事项

list.RemoveAll(x => z.flag == 1);

在给定位置向主列表中插入优先项。

list.InsertRange(1, priorityRecords);

这个过程正在正确地完成工作并给我期望的结果。但是我不确定这是否是正确的方法，或者是否有更好的方法（考虑性能）？请提供你的建议。

另外，当我进行许多操作（过滤、删除、插入）时，随着记录数从50增加到100000（任意数字），性能会受到影响吗？

更新：如何使用IQueryable减少对列表的操作次数？

- Ranadheer Reddy

---

10万还不算太多。你有没有测试过并且了解需要什么样的性能？我敢打赌输入和输出所需的时间远远大于实际排序所需的时间。你可以通过按照那个顺序对单个列表/数组进行排序来完成它。如果前50个已经排好序并且你不能改变它，你可以在原地完成所有操作，但差别会非常小。 - Fire Lancer

Answer 1

根据InsertRange的文档：

该方法是一个O(n * m)操作，其中n是要添加的元素数，m是Count。

n*m不太好，因此我会使用LINQ的Concat方法从三个较小的列表创建一个全新的列表，而不是修改现有的列表。

var allItems = getMyTop50();
var topPriorityItems = list.Where(x => x.flag == 1).ToList();
var topNonPriorityItems = list.Where(x => x.flag != 1).ToList();

var result = topNonPriorityItems
    .Take(constant)
    .Concat(topPriorityItems)
    .Concat(topNonPriorityItems.Skip(constant));

我不确定List<T>的Concat、Skip和Take方法有多快，但我敢打赌它们不会比O(n)更慢。

- dmngrsk

---

你应该进行测量，因为有很多情况下 O(n) 或 O(1) 比其他解决方案慢，而此时的 n 并不是非常大。 - Fire Lancer

是的，特别是在使用 HashSet<T> 的解决方案上。不过我认为 List<T> 上的常数时间不应该那么高。 - dmngrsk

有相当多的额外对象，Concat 和 Take 也正在创建迭代器和其他东西。 - Fire Lancer

Answer 2

看起来你实际上要解决的问题只是对项目列表进行排序。如果是这种情况，你不需要担心删除优先项目并将它们重新插入到正确的索引位置，你只需要找出你的排序函数即可。像这样的东西应该可以工作：

// Set "x" to be whatever you want based on your requirements --
// this is the number of items that will precede the "priority" items in the
// sorted list
var x = 3;

var sortedList = list
   .Select((item, index) => Tuple.Create(item, index))
   .OrderBy(item => {
       // If the original position of the item is below whatever you've 
       // defined "x" to be, then keep the original position
       if (item.Item2 < x) {
          return item.Item2;
       } 

       // Otherwise, ensure that "priority" items appear first
       return item.Item1.flag == 1 ? x + item.Item2 : list.Count + x + item.Item2;
}).Select(item => item.Item1);

你可能需要根据你想要做的事情稍微调整一下，但这似乎比从多个列表中删除/插入要简单得多。

编辑：忘记了OrderBy不提供一个重载，该重载提供项目的原始索引；更新答案以将项目包装在包含原始索引的元组中。虽然不像原始答案那样干净，但它仍然应该有效。

- Donut

---

感谢您提供的解决方案。但是，我将这段代码与原始代码（在问题中提到）进行了比较，发现原始代码执行时间更短。尽管差异只有几毫秒，但这段代码需要2倍的时间来执行。 - Ranadheer Reddy

Answer 3

可以使用linq-to-objects对原始集合进行单个枚举来完成此操作。在我看来，这也基于您定义的原始要求非常清晰易读。

首先，定义我们将进行排序的“桶”：我喜欢在此处使用枚举以获得清晰度，但您也可以只使用int。

enum SortBucket
{
  RecentItems = 0,
  PriorityItems = 1,
  Rest = 2,
}

然后我们将定义逻辑，确定特定项目将被分类到哪个“桶”中：

private static SortBucket GetBucket(Item item, int position, int recentItemCount)
{
  if (position <= recentItemCount)
  {
    return SortBucket.RecentItems;
  }
  return item.IsPriority ? SortBucket.PriorityItems : SortBucket.Rest;
}

然后是一个非常简单的linq-to-objects语句，将首先按照我们定义的桶进行排序，然后再按原始位置排序。写成一个扩展方法：

static IEnumerable<Item> PrioritySort(this IEnumerable<Item> items, int recentItemCount)
{
  return items
    .Select((item, originalPosition) => new { item, originalPosition }) 
    .OrderBy(o => GetBucket(o.item, o.originalPosition, recentItemCount))
    .ThenBy(o => o.originalPosition)
    .Select(o => o.item);
}

- Eric Damtoft