什么是最（性能）高效且可读的“拆分”方式？基于条件的通用列表？

Question

（高度简化的示例） 我有一个通用的字符串列表：

var strings = new List<string> { "abc", "owla", "paula", "lala", "hop" };

我正在寻找最有效的方法来将此列表拆分为包含满足条件的元素的列表和不满足相同条件的元素的列表。

Func<string, bool> condition = s => s.IndexOf("o") > -1;
Predicate<string> kickOut = s => s.IndexOf("o") > -1;
var stringsThatMeetCondition = strings.Where(condition);
strings.RemoveAll(kickOut);
var stringsThatDontMeetCondition = strings;

有没有办法只循环原始列表一次来做到这一点？

Answer 1

使用一些 linq：

var matches = list.Select(s => s.IndexOf("o") > -1).ToList();
var notMatches = list.Except(matches).ToList();
list.Clear();
list.AddRange(matches);

更新： 正如评论中提到的，请小心改变列表，因为 linq 方法尝试按需，它们不会迭代列表，直到您开始查看 IEnumerable。但就我而言，我调用 ToList，这实际上导致它遍历整个项目列表。

Answer 2

这样就可以了：

IEnumerable<T> FilterAndRemove(this List<T> list, Func<T, bool> pred)
{
  List<T> filtered = new List<T>();
  int i = 0;
  while(i < list.Count)
  {
     if (pred(list[i]))
     {
        filtered.Add(list[i]);
        list.RemoveAt(i);
     }
     else
     { 
        ++i;
     }
  }
  return list;
}

但我相信你已经想到了类似的事情。您能否以您寻求的效率更新您的答案？

请注意，在原始列表上使用 pred 和 !pred 进行两次过滤仍然是 O(n)，而且效率一点也不低。特别是考虑到您将获得两个结果集的惰性求值的全部好处。另请参阅罗布的回答。

该算法的时间复杂度为 O(n^2)。

您还可以将它们收集到一个新列表中，并在返回之前将它们复制到输入列表中，而不是删除每个元素。这也将为您带来 O(n)。

O(n) 的另一种选择是切换到链表。

Answer 3

为什么不直接使用

var stringsThatMeetCondition = strings.Where(condition);
var stringsThatDontMeetCondition = strings.Where(x => !condition(x));

当然，您最终会将条件应用于列表中的每个元素两次。为了避免这种情况，您可能需要编写一个通用的拆分函数，但这不会那么简洁。

Answer 4

Func<string, bool> condition = ...;
var groupedStrings = strings.GroupBy(condition)
var stringsMeetingCondition = groupedStrings.FirstOrDefault(g => g.Key);
var stringsNotMeetingCondition = groupedStrings.FirstOrDefault(g => !g.Key);