Entfernen von doppelten string aus der Liste (.NET 2.0!)

Habe ich Probleme, das finden der effizienteste Weg, um entfernen Sie Duplikate aus einer Liste von strings (Listen).

Meine aktuelle Implementierung ist eine doppelte foreach-Schleife prüfen die Anzahl der Instanzen für jedes Objekt nur auf 1, andernfalls entfernen Sie den zweiten.

Ich weiß, es gibt VIELE andere Fragen gibt, aber Sie alle die besten Lösungen müssen vor .net 2.0, das ist die aktuelle build-Umgebung arbeite ich in. (GM und Chrysler sind sehr resistent gegen Veränderungen ... 🙂 )

Diese Grenzen der möglichen Ergebnisse, indem nicht alle LINQ, oder HashSets.

Den code, den ich verwende, ist Visual C++, sondern C# - Lösung gut funktionieren wird, wie gut.

Dank!

InformationsquelleAutor greggorob64 | 2009-08-26
  1. 15

    Dies ist wahrscheinlich nicht, was Sie suchen, aber wenn Sie haben die Kontrolle über dieses der effizienteste Weg wäre, um nicht fügen Sie Sie in den ersten Platz...

    Haben Sie die Kontrolle über diese? Wenn dem so ist, alles, was Sie würde tun müssen, ist ein myList.Contains(currentItem) rufen, bevor Sie das Element hinzufügen und Sie sind

    • Hah, habe ich nie nachgedacht, ich habe die Kontrolle über die Liste generation!
    • LOL. das ist WIN!
    • Sich bewusst sein, dieser Ansatz nicht sehr gut skalieren, wenn die Größe der Liste steigt...
    • Wenn Größe ist ein Anliegen, ich würde denken, dass Sie in Ordnung sein würde, tun die gleiche Methode, die oben, aber mit einer SortedList Gegensatz zu einer standard-Liste
    • Es ist O(n^2) da List<T>.Enthält ist O(n). Sie brauchen, um zu leihen, Jared Wörterbuch, um zu verfolgen die Elemente, die Sie Hinzugefügt haben, geben O(1) überprüft, und O(n) insgesamt.
    • Zum Glück skalieren ist kein Problem, in dieser besonderen situation
    • steve, würde nicht die Prüfung logn und nicht 1? das wäre das gleiche wie mit einer sortedlist über eine Liste
    • Wörterbücher sind Konstante Zeit-lookup. Log(n) einfügen Zeit.
    • Oops; aussieht, war ich ein wenig verwirrt, wie hashtables funktionieren
    • 8 Jahre später, und Sie verwalten zu machen noch jemandem das Gefühl dümmer als ein Feld von Steinen. Danke @John, du hast mich gerettet, eine enorme Menge Arbeit.

    InformationsquelleAutor John
  2. 9

    Können Sie das folgende tun. 

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

    Dies hat den Aufwand des Aufbaus einer Dictionary<TKey,TValue> Objekt, das dupliziert die Liste der eindeutigen Werte in der Liste. Es ist aber ziemlich effiziente Geschwindigkeit klug.

    • +1 Erste Sache, die aufgetaucht in den Sinn, war zu vergleichen, jeder Wert zu jeder anderen, während das entfernen von Duplikaten, wie Sie gefunden werden aber der Komplexität N^2. Jared ' s Lösung ist viel schöner, da mit Hilfe von einem Dicitonary Daten-Struktur wird mithilfe von hashing und daher sehr schnell ausgeführt. Komplexität = N(log N) ?
    • Wenn es auf Geschwindigkeit ankommt, Sie wäre besser, eine neue Liste zu erstellen von der einzigartigen Werte, die eher als entfernen der Duplikate aus der ursprünglichen Liste, da RemoveAt ist O(n), aber Add O(1) wenn Sie die maximale Länge im Voraus.
    InformationsquelleAutor JaredPar
  3. 1

    Ich bin kein Comp Sci PhD, aber ich würde stellen Sie sich vor, ein Wörterbuch, mit dem die Elemente in Ihrer Liste der Schlüssel wäre schnell.

    Da ein Wörterbuch gestattet keine doppelten Schlüssel, würde man nur einzigartige Zeichenfolgen, die am Ende der iteration.

    InformationsquelleAutor Alan
  4. 1

    Denken Sie nur daran, wenn die Bereitstellung einer benutzerdefinierten Klasse zum überschreiben der Equals () - Methode, um für die Contains () - Funktion erforderlich.

    Beispiel

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

public class CustomClass{

    public bool Equals(Object param){
        //Put equal code here...
    }
}
    InformationsquelleAutor Koekiebox
  5. 1

    Wenn du gehst, die route, die "nur" nicht hinzufügen "dupliziert", dann überprüfen " - Liste.Enthält" vor dem hinzufügen eines Elements funktioniert, aber seine O(n^2), wobei n die Anzahl Zeichenfolgen, die Sie hinzufügen möchten. Seine nicht anders als deine aktuelle Lösung mit zwei verschachtelten Schleifen.

    Haben Sie mehr Glück mit einem hashset speichern Artikel, die Sie bereits Hinzugefügt, aber da Sie verwenden .NET 2.0, ein Wörterbuch ersetzen kann, ein hash-set:

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

    Dieser läuft in O(n) und benutzt O(2n) Platz, es wird in der Regel die Arbeit sehr gut für bis zu 100K Artikel. Die tatsächliche Leistung hängt von der durchschnittlichen Länge des strings -- wenn Sie wirklich brauchen, um die maximale Leistung, die Sie ausnutzen können einige mehr leistungsfähige Daten-Strukturen, wie versucht, machen die Einsätze noch schneller.

    • HashSet sind .net 3.5+, das ist aus dem Anwendungsbereich dieser Frage.
    • Meine codes nicht verwenden, HashSet, es verwendet ein Wörterbuch, das ersetzt so ein HashSet.
    • Sollte ich gelesen haben, deinen code genauer, ich sah nur das Wort HashSet, und überging es.
    • Was über NULL-Werte? Wörterbuch löst eine ArgumentNullException-Ausnahme für den Schlüssel.
    InformationsquelleAutor Juliet
Schreibe einen Kommentar