Trova e rimuovi elementi dalla raccolta

Question

Qual è il modo migliore per rimuovere un set da una raccolta, mantenendo comunque gli elementi rimossi in una raccolta separata?

Ho scritto un metodo di estensione che lo fa, ma penso che ci sia un modo migliore. Ecco la mia funzione:

public static List<T> FindAndRemove<T>(this List<T> lst, Predicate<T> match) 
{ 
    List<T> ret = lst.FindAll(match); 
    lst.RemoveAll(match); 
    return ret; 
} 

E si usa in questo modo:

List<String> myList = new List<String>(); 
myList.Add("ABC"); 
myList.Add("DEF"); 
myList.Add("ABC"); 
List<String> removed = myList.FindAndRemove(x => x == "ABC"); 
// myList now contains 1 item (DEF) 
// removed now contains 2 items (ABC, ABC) 

Io non sono sicuro al 100% cosa succede dietro le quinte nei metodi FindAll e RemoveAll, ma immagino un modo migliore sarebbe in qualche modo "trasferire" elementi da una lista all'altra.

Answer 1

Non sono d'accordo sul fatto che sia il più efficiente - si sta chiamando il predicato match due volte su ogni elemento dell'elenco.

lo farei in questo modo:

var ret = new List<T>(); 
    var remaining = new List<T>(); 
    foreach (T t in lst) { 
     if (match(t)) 
     { 
      ret.Add(t); 
     } 
     else 
     { 
      remaining.Add(t); 
     } 
    } 
    lst.Clear(); 
    lst.AddRange(remaining); 
    return ret; 

Answer 2

A seconda delle dimensioni della vostra collezione, si potrebbe desiderare per la sua attuazione come un HashSet piuttosto che un elenco. In raccolte sufficientemente grandi (quanto grande è "sufficiente" è stato in qualche modo dipendente da ciò che è nella collezione, nella mia esperienza), HashSets può essere molto, molto più veloce nel trovare gli oggetti dentro di sé rispetto a Liste.

Answer 3

La risposta di Op è il meglio delle soluzioni proposte e suggerite finora. Ecco i tempi sulla mia macchina:

public static class Class1 
{ 
    // 21ms on my machine 
    public static List<T> FindAndRemove<T>(this List<T> lst, Predicate<T> match) 
    { 
     List<T> ret = lst.FindAll(match); 
     lst.RemoveAll(match); 
     return ret; 
    } 

    // 538ms on my machine 
    public static List<T> MimoAnswer<T>(this List<T> lst, Predicate<T> match) 
    { 
     var ret = new List<T>(); 
     int i = 0; 
     while (i < lst.Count) 
     { 
      T t = lst[i]; 
      if (!match(t)) 
      { 
       i++; 
      } 
      else 
      { 
       lst.RemoveAt(i); 
       ret.Add(t); 
      } 
     } 
     return ret; 
    } 

    // 40ms on my machine 
    public static IEnumerable<T> GuvanteSuggestion<T>(this IList<T> list, Func<T, bool> predicate) 
    { 
     var removals = new List<Action>(); 

     foreach (T item in list.Where(predicate)) 
     { 
      T copy = item; 
      yield return copy; 
      removals.Add(() => list.Remove(copy)); 
     } 

     // this hides the cost of processing though the work is still expensive 
     Task.Factory.StartNew(() => Parallel.ForEach(removals, remove => remove())); 
    } 
} 

[TestFixture] 
public class Tester : PerformanceTester 
{ 
    [Test] 
    public void Test() 
    { 
     List<int> ints = Enumerable.Range(1, 100000).ToList(); 
     IEnumerable<int> enumerable = ints.GuvanteSuggestion(i => i % 2 == 0); 
     Assert.That(enumerable.Count(), Is.EqualTo(50000)); 
    } 
} 

Answer 4

Quello che dovresti provare a fare è dividere la tua lista originale in due nuovi elenchi. L'implementazione dovrebbe funzionare su qualsiasi IEnumerable, non solo sugli elenchi, e dovrebbe presupporre che l'origine sia immutabile. Vedere questo post sul partizionamento: LINQ Partition List into Lists of 8 members. Penso che MoreLinq abbia già coperto.