Какой самый (эффективный) эффективный и читаемый способ «разделить» общий список на основе условия?

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

Почему бы просто не использовать

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

Конечно, вы применяете условие к каждому элементу в списке дважды. Чтобы избежать этого, вы можете написать обобщенную функцию расщепления, которая не была бы такой аккуратной.

Answer 3

Это будет сделано:

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 4

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