Quelle est la manière la plus efficace et la plus lisible de diviser une liste générique en fonction d'une condition?

Question

(exemple très simplifié) J'ai une liste générique de chaînes:

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

Je suis à la recherche de la façon la plus efficace de diviser cette liste en une liste des éléments qui répondent à une condition et une liste d'éléments qui ne répondent pas à cette même condition. Y a-t-il un moyen de faire cela avec une seule boucle dans la liste d'origine?

Answer 1

Cela le ferait:

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; 
} 

, mais je suis sûr que vous avez déjà pensé à quelque chose de similaire. Pouvez-vous s'il vous plaît mettre à jour votre réponse avec le type d'efficacité que vous recherchez? Notez que deux filtrages avec pred et !pred sur la liste d'origine seraient toujours O (n) et pas du tout inefficaces. Surtout en considérant que vous bénéficieriez pleinement de l'évaluation paresseuse pour les deux ensembles de résultats. Voir aussi la réponse de Rob.

Cet algorithme est dans O (n^2). Au lieu de supprimer chaque élément, vous pouvez également les rassembler dans une nouvelle liste et les copier dans la liste d'entrée avant de les renvoyer. Cela vous donnera aussi O (n).

Une option de plus pour O (n) serait de passer à une liste chaînée.

Answer 2

utiliser certains LINQ:

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

Mise à jour: comme cela a été mentionné dans les commentaires, faites attention muter la liste que les méthodes de LINQ essayer d'être à la demande, ils n'itérer la liste jusqu'à ce que vous commencer à regarder dans le IEnumerable. Cependant, dans mon cas, j'appelle le ToList, ce qui l'oblige à parcourir la liste complète des éléments.

Answer 3

Pourquoi ne pas utiliser

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

Bien sûr, vous finissez par l'application de la condition de chaque élément dans la liste deux fois. Pour éviter cela, vous pourriez écrire une fonction générique qui ne serait pas aussi nette.

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);