Modo più rapido per fare una lista <T> .Contains()

Question

Sto provando a fare quello che penso sia un "de-intersect" (non sono sicuro di quale sia il nome corretto, ma è quello che chiamava Tim Sweeney di EpicGames nel vecchio UnrealEd)

// foo and bar have some identical elements (given a case-insensitive match) 
List‹string› foo = GetFoo(); 
List‹string› bar = GetBar(); 

// remove non matches 
foo = foo.Where(x => bar.Contains(x, StringComparer.InvariantCultureIgnoreCase)).ToList(); 
bar = bar.Where(x => foo.Contains(x, StringComparer.InvariantCultureIgnoreCase)).ToList(); 

poi in seguito, faccio un'altra cosa in cui mi sottraggo il risultato dall'originale, per vedere quali elementi ho rimosso. È super veloce usando. Eccetto(), quindi non ci sono problemi.

Ci deve essere un modo più veloce per fare questo, perché questo è piuttosto male performante con ~ 30.000 elementi (di stringa) in entrambi gli elenchi. Preferibilmente, un metodo per fare questo passo e quello successivo in un colpo solo sarebbe bello. Ho provato a usare .Exists() invece di .Contains(), ma è leggermente più lento. Mi sento un po 'spessa, ma penso che dovrebbe essere possibile con alcune combinazioni di .Except() e .Intersect() e/o .Union().

Answer 1

Con intersecano sarebbe stato fatto in questo modo:

var matches = ((from f in foo 
       select f) 
       .Intersect(
        from b in bar 
        select b, StringComparer.InvariantCultureIgnoreCase)) 

Answer 2

Questa operazione può essere definita una differenza simmetrica.

È necessaria una struttura dati diversa, ad esempio una tabella hash. Aggiungi l'intersezione di entrambi i set su di esso, quindi cambia l'intersezione da ciascun set.

UPDATE:

ho avuto un po 'di tempo per provare questo nel codice. Ho usato HashSet<T> con una serie di 50.000 stringhe, da 2 a 10 caratteri con i seguenti risultati:

originali: 79499 ms

HashSet: 33 ms

BTW , c'è un metodo su HashSet chiamato SymmetricExceptWith che pensavo avrebbe fatto il lavoro per me, ma in realtà aggiunge i diversi elementi da entrambi gli insiemi al set sul quale viene richiamato il metodo. Forse questo è quello che vuoi, piuttosto che lasciare le due serie iniziali non modificate, e il codice sarebbe più elegante.

Ecco il codice:

using System; 
using System.Collections.Generic; 
using System.Diagnostics; 
using System.Linq; 

class Program 
{ 
    static void Main(string[] args) 
    { 
     // foo and bar have some identical elements (given a case-insensitive match) 
     var foo = getRandomStrings(); 
     var bar = getRandomStrings(); 

     var timer = new Stopwatch(); 

     timer.Start(); 
     // remove non matches 
     var f = foo.Where(x => !bar.Contains(x)).ToList(); 
     var b = bar.Where(x => !foo.Contains(x)).ToList(); 
     timer.Stop(); 

     Debug.WriteLine(String.Format("Original: {0} ms", timer.ElapsedMilliseconds)); 

     timer.Reset(); 

     timer.Start(); 
     var intersect = new HashSet<String>(foo); 
     intersect.IntersectWith(bar); 

     var fSet = new HashSet<String>(foo); 
     var bSet = new HashSet<String>(bar); 

     fSet.ExceptWith(intersect); 
     bSet.ExceptWith(intersect); 
     timer.Stop(); 

     var fCheck = new HashSet<String>(f); 
     var bCheck = new HashSet<String>(b); 

     Debug.WriteLine(String.Format("Hashset: {0} ms", timer.ElapsedMilliseconds)); 

     Console.WriteLine("Sets equal? {0} {1}", fSet.SetEquals(fCheck), bSet.SetEquals(bCheck)); //bSet.SetEquals(set)); 
     Console.ReadKey(); 
    } 

    static Random _rnd = new Random(); 

    private const int Count = 50000; 

    private static List<string> getRandomStrings() 
    { 
     var strings = new List<String>(Count); 

     var chars = new Char[10]; 

     for (var i = 0; i < Count; i++) 
     { 
      var len = _rnd.Next(2, 10); 

      for (var j = 0; j < len; j++) 
      { 
       var c = (Char)_rnd.Next('a', 'z'); 
       chars[j] = c; 
      } 

      strings.Add(new String(chars, 0, len)); 
     } 

     return strings; 
    } 
} 

Answer 3

Contiene in un elenco è un'operazione O (N). Se avessi una struttura dati diversa, come un elenco ordinato o un dizionario, ridurrai drasticamente il tuo tempo. L'accesso a una chiave in una lista ordinata è di solito O (log N) tempo, e in un hash è di solito O (1) volta.

Answer 4

Se gli elementi sono univoci all'interno di ogni lista è consigliabile utilizzare una classe HashSet

Il HashSet (T) offre elevati operazioni di set prestazioni. Un set è una raccolta che non contiene elementi duplicati e i cui elementi non sono in ordine particolare.

Answer 5

Con lista ordinata, è possibile utilizzare la ricerca binaria.