根据条件"拆分"泛型列表的最(性能)高效和可读性方法是什么？

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），并且一点也不低效。特别是考虑到您将获得两个结果集的懒惰评估的全部好处。另请参见Rob的回答。

这个算法在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);