2015-11-24 36 views
5

Ho difficoltà a trovare le risposte a una domanda relativa a un codice specifico per ciò a cui sto lavorando e non riesco a trovare alcuna documentazione su come funziona l'Unione al suo meccanica di base in C#. Quindi il problema è questo.C# Union vs Contiene per gli elenchi di dati continui

Ho una serie di dati che funziona in modo simile a questo esempio:

 object[] someMainTypeArray = new object [n]; 
    List<object> objList2 = new List<object>(); 
    foreach (object obj in someMainTypeArray) { 
     List<object> objList1 = new List<object>() { "1","2","3" }; 
     //each obj has a property that will generate a list of data 
     //objList1 is the result of the data specific to obj 
     //some of this data could be duplicates 
     //Which is better, this: 
     foreach (object test in objList1) { 
      if (!objList2.Contains(test)) { 
       objList2.Add(test); 
      } 
     } 
     //or this: 
     objList2 = objList2.Union(objList1).ToList(); 
     //Also, assume this has to happen anywhere from 0 to 60 times per second 
    } 

È più efficace lasciare dell'Unione fare tutto il lavoro? O è meglio confrontare ogni elemento usando Contains?

Se No per entrambi, qual è il modo migliore per compilare elenchi univoci utilizzando il minor tempo di elaborazione possibile?

L'efficienza è la chiave per questo. Inoltre, questo non è compito a casa, o qualcosa di relativo al lavoro, solo imparando collegato.

Gli elenchi sono continui in fase di esecuzione nel modo in cui vengono infine cancellati e ripopolati. Le modifiche negli elenchi vengono utilizzate per prendere decisioni in base al fatto che gli elenchi dei risultati finali che sono tutti simili a questo esempio vengano utilizzati per creare un elenco finale e se tale elenco è vuoto, è una condizione di errore e quella lista non è vuota, è una condizione di successo.

Ecco un frammento del codice in questione per una delle liste create:

 Player.ClearMoves(); 
    List<Pair<BoardLocation, BoardLocation>> attacking = new List<Pair<BoardLocation, BoardLocation>>(); 
    foreach (ChessPiece p in Board[this.Player.Opponent]) { 
     if (p.TheoryMove(this.Location)) { 
      foreach (Pair<BoardLocation , BoardLocation> l in Utility.GetLocations(p.Location , this.Location)) { 
       if (!attacking.Contains(l)) { 
       attacking.Add(l); 
       } 
      } 
     } 
    } 
    if (attacking.Count < 1) { 
     return false; 
    } 
+0

Se si utilizza la Lista invece di Hashset , allora Union() ** maggio ** (probabilmente) sarà più efficiente. Se lo fai _by yourself_ usando un hashset, guadagnerai un po 'di efficienza (rispetto a Union) ma ... lo farei solo quando si tratta di un problema ** misurato **. –

risposta

9

È possibile trovare il Enumerable.Union implementazione nel reference source.

Questo è come funziona:

public static IEnumerable<TSource> Union<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second) { 
    if (first == null) throw Error.ArgumentNull("first"); 
    if (second == null) throw Error.ArgumentNull("second"); 
    return UnionIterator<TSource>(first, second, null); 
} 

static IEnumerable<TSource> UnionIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer) 
{ 
    Set<TSource> set = new Set<TSource>(comparer); 
    foreach (TSource element in first) 
     if (set.Add(element)) yield return element; 
    foreach (TSource element in second) 
     if (set.Add(element)) yield return element; 
} 

Come si può vedere, Union sarà scorrere entrambi enumerables e oggetti di rendimento da tali fonti. Come tutti i metodi Linq, non crea una lista ma funziona come una funzione di generatore. L'elenco verrà creato solo quando si chiama .ToList().

Al fine di evitare duplicati, utilizzerà un Set e tenterà di aggiungere un elemento prima di cederlo. Se l'aggiunta al set ha successo, allora l'elemento non era già lì, quindi può essere restituito.

Si noti che i set sono molto efficienti per cercare se un elemento esiste in esso. Forniscono una ricerca degli articoli in tempo costante ammortizzato. Quindi questo è decisamente più efficiente del tuo objList2.Contains che dovrà scorrere ripetutamente l'elenco per capire se ciascun elemento esiste al suo interno.

Si noti inoltre che Union è stato creato per mantenere l'ordine degli enumerabili di input. Se non ne hai bisogno, puoi saltarlo completamente e usare solo uno Set in primo luogo. Ciò è particolarmente utile se si ha intenzione di aggiungere nuovi elementi per lo stesso obiettivo fissato per tutto il tempo dal momento che riutilizza la struttura:

HashSet<object> set = new HashSet<object>(); 

foreach (…) 
{ 
    List<object> objList1 = … 

    // expand the set with the items from `objList1` 
    set.UnionWith(objList1); 
} 

Sarebbe ancora meglio se si eviti di creare objList1 in primo luogo, e appena aggiunto il tuo elementi direttamente sul set, se possibile per il tuo caso d'uso.

+0

Vedo, ho visto questo codice ma, non ero sicuro di cosa significasse specificamente. Ma, anche così è efficiente fare più sindacati e poi restituire una lista alla fine? o c'è un modo per combinare liste più efficienti? – G1xb17

+0

L'unica ragione per cui non ho mostrato il mio codice è perché potrebbero esserci 120 righe di codice relative all'attività. – G1xb17

+1

se si vogliono fare più sindacati, è probabilmente meglio fare un metodo personalizzato che usa un singolo set per tutti i sindacati e loop su alla lista per aggiungere elementi al set. –

3

Se si guarda alla reference source for the LINQ extensions (ricerca di UnionIterator) si vedrà che Union funziona internamente utilizzando un Set<T> per monitorare quali voci sono state enumerate sopra.Sfortunatamente, Set<T> è una classe interna della libreria, quindi non è possibile utilizzarla direttamente. Ma esiste una raccolta simile denominata HashSet<T> che potresti utilizzare.

Probabilmente una delle principali inefficienze della vostra implementazione è la creazione di un nuovo elenco per objList2 in ogni iterazione del ciclo esterno. Ciò attiverà le iterazioni e allocazioni di memoria ogni volta. Dal momento che si sta costruendo la lista attraverso cicli annidati Suggerirei di fare una delle seguenti cose:

  1. Aggiungi tutto a una List<T> e utilizzare .Distinct quando hai finito di filtrare i duplicati. Questo approccio utilizza anche la classe interna Set<T>, ma a differenza della concatenazione di più chiamate a Union, verrà utilizzato un solo Set per creare l'elenco univoco.
  2. Utilizzare uno HashSet<T> per creare una raccolta che abbia sempre un elenco univoco di elementi in essa contenuti.
+0

Questa implementazione manca di molti dettagli. La cosa che viene creata completamente è la funzione usata per generare ogni nuova lista, la lista che viene popolata è già istanziata in questo momento, così è il "mainobject" che governa tutto. – G1xb17

+0

È difficile per me commentare qualsiasi cosa diversa dal codice che è nella domanda. Sto osservando la riga 'objList2 = objList2.Union (objList1) .ToList();'. Questo crea una nuova lista ogni iterazione. – Erik

+0

Ecco come è specificamente per l'elenco che è all'interno del ciclo. Le liste che iniziano all'esterno sono per lo più immutabili, possono perdere elementi o guadagnare elementi ma non essere mai reinizializzate. – G1xb17