Rimozione della stringa duplicata da List (.NET 2.0!)

Question

Sto riscontrando problemi nel trovare il modo più efficiente per rimuovere i duplicati da un elenco di stringhe (Elenco).

La mia implementazione corrente è un doppio ciclo foreach che controlla il conteggio delle istanze di ciascun oggetto che è solo 1, altrimenti rimuove il secondo.

So che ci sono MOLTE altre domande là fuori, ma tutte le migliori soluzioni richiedono sopra .net 2.0, che è l'ambiente di costruzione corrente in cui sto lavorando. (GM e Chrysler sono molto resistenti ai cambiamenti ... :))

Ciò limita i risultati possibili non consentendo alcun LINQ o HashSet.

Il codice che sto usando è Visual C++, ma una soluzione C# funzionerà altrettanto bene.

Grazie!

Answer 1

Questo probabilmente non è quello che stai cercando, ma se si ha il controllo su questo, il modo più efficace sarebbe non li aggiungere, in primo luogo ...

Hai il controllo su Questo? Se è così, tutto quello che devi fare è una chiamata myList.Contains(currentItem) prima di aggiungere l'elemento e sei impostato

Answer 2

Si potrebbe fare quanto segue.

List<string> list = GetTheList(); 
Dictionary<string,object> map = new Dictionary<string,object>(); 
int i = 0; 
while (i < list.Count) { 
    string current = list[i]; 
    if (map.ContainsKey(current)) { 
    list.RemoveAt(i); 
    } else { 
    i++; 
    map.Add(current,null); 
    } 
} 

Questo ha l'overhead di costruire un oggetto Dictionary<TKey,TValue> che duplicare l'elenco di valori univoci nella lista. Ma è abbastanza efficiente in termini di velocità.

Answer 3

Non sono un dottore in scienze, ma immagino di usare un dizionario, con gli elementi nella lista come le chiavi sarebbero veloci.

Poiché un dizionario non consente chiavi duplicate, alla fine dell'iterazione si avranno solo stringhe univoche.

Answer 4

Basta ricordare quando si fornisce una classe personalizzata per sovrascrivere il metodo Equals() in modo che Contains() funzioni come richiesto.

Esempio

List<CustomClass> clz = new List<CustomClass>() 

public class CustomClass{ 

    public bool Equals(Object param){ 
     //Put equal code here... 
    } 
} 

Answer 5

Se stai andando il percorso di "basta non aggiungere duplicati", quindi il controllo "List.Contains" prima di aggiungere un elemento funziona, ma la sua O (n^2) dove n è il numero di stringhe che si desidera aggiungere. Non è diverso dalla tua attuale soluzione usando due loop annidati.

Avrete più fortuna con un hashset per memorizzare gli oggetti che hai già aggiunto, ma dal momento che si sta utilizzando .NET 2.0, un dizionario può sostituire per un set hash:

static List<T> RemoveDuplicates<T>(List<T> input) 
{ 
    List<T> result = new List<T>(input.Count); 
    Dictionary<T, object> hashSet = new Dictionary<T, object>(); 
    foreach (T s in input) 
    { 
     if (!hashSet.ContainsKey(s)) 
     { 
      result.Add(s); 
      hashSet.Add(s, null); 
     } 
    } 
    return result; 
} 

Questo viene eseguito in O (n) e utilizza lo spazio O (2n), generalmente funzionerà molto bene per un massimo di 100K elementi. Le prestazioni effettive dipendono dalla lunghezza media delle stringhe: se hai davvero bisogno di prestazioni massime, puoi sfruttare alcune strutture dati più potenti come i tentativi di rendere gli inserti ancora più veloci.