Laden...

doppelte Werte einer Liste löschen

Letzter Beitrag vor 13 Jahren 11 Posts 38.425 Views
Information von herbivore vor 13 Jahren

Dies ist ein Thread, auf den aus der FAQ verwiesen wird. Bitte keine weitere Diskussion, sondern nur wichtige Ergänzungen und diese bitte knapp und präzise. Vielen Dank!

doppelte Werte einer Liste löschen

Hallo ich wollte alle Werte einer doppelten Liste lösche, weiß einer von euch, was ich falsch gemacht habe und wie es besser geht ?
Hab schon gegoogelt aber nichts passendes gefunden


        private List<string> doppelte_finden(List<string> Liste_string)
        {
            for (int i = 0; i < Liste_string.Count; i++)
            {
                for (int j = 0; j < Liste_string.Count; j++)
                {
                    if (Liste_string[i] == Liste_string[j]) // Fehler
                    {
                        Liste_string.Remove(Liste_string[j]);
                    }
                }
            }
            return Liste_string;
        }

Gruß impact_1991

Hi,

na was denkste was beim ersten Durchlauf passiert ?

Liste_string[0] == Liste_string[0]

Ich würde, die Elemente in einem Dictionary<string,string> sammeln. Eine foreach Schleife und bei jedem Element nachschauen, ob es schon im Dictionary enthalten ist. Das funktioniert, dann auch wenn ein Element öfter als zweimal vorkommt.

Tschüss

danke für den Vorschlag
das müsste klappen

Hallo!
Zudem sollte die Liste zwingend rückwärts durchlaufen werden, sonst fällt ein Index irgendwann ins Leere, wenn man vorher was gelöscht hat.

Also bei sowas immer


for (int i = Liste_string.Count - 1; i >= 0; i--) ...

Nobody is perfect. I'm sad, i'm not nobody 🙁

Ich hab es jetzt so umgesetzt



 private List<string> doppelte_finden(List<string> Liste_string)
        {
            List<string> ergebnis= new List<string>();
            bool schon_vorhanden = false;
            
            for (int i = 0; i < Liste_string.Count; i++)
            {
                for (int j = 0; j < ergebnis.Count; j++)
                {
                    if (Liste_string[i] == ergebnis[j])
                    {
                        schon_vorhanden = true;
                        break;

                    }
                    
                }
                if (schon_vorhanden == false)
                {
                    ergebnis.Add(Liste_string[i]);
                    
                }
                else
                {
                    schon_vorhanden = false;
                }
            }
            return ergebnis;
        }



fals jemand etwas übersichtlicheres oder schnelleres kennt kann es gern posten

gruß impact

EDIT von herbivore: Ungünstige Lösung wegen der quadratischen Laufzeit. Erklärung und bessere Lösungen (mit linearer Laufzeit) siehe weiter unten.

Hallo impact_1991,
aus diesem:
if(schon_vorhanden == false)
if(!schon_vorhanden)
folgt ganz schnell dies: [Tipp] Anfängerfehler == true / == false

Gruß Michael

Mein Blog
Meine WPF-Druckbibliothek: auf Wordpress, myCSharp

Hi,

Vorschlag 1:

// behält die Reihenfolge bei
private static List<string> ohneDoppelte(List<string> stringList)
{
    // Menge der strings, die bereits in der Ergebnisliste sind
    HashSet<string> strings = new HashSet<string>();
            
    // Mittels LINQ die Werte übernehmen, die vorher noch nicht vorkamen
    return stringList.Where(x => 
        {
            // wenn schon in der ErgebnisListe, dann nicht übernehmen
            if (strings.Contains(x))
            {
                return false;
            }
            // andernfalls der Menge hinzufügen und Element übernehmen
            else
            {
                strings.Add(x);
                return true;
            }
        })
        .ToList();
}

Vorschlag 2:

// ignoriert die Reihenfolge
private static List<string> ohneDoppelte(List<string> stringList)
{
    // Liste in eine Menge und wieder zurück in eine Liste umwandeln
    // (doppelte Einträge gehen verloren)
    return (new HashSet<string>(stringList)).ToList();
}

Vorschlag 3: (Annahme: RemoveAll(...) geht sequentiell in der normalen Iterationsreihenfolge durch)


// behält die Reihenfolge bei
private static List<string> ohneDoppelte(List<string> stringList)
{
    // Dictionary das mitzählt, wie oft ein Element bereits vorkam
    Dictionary<string, int> stringOccurence = new Dictionary<string, int>();
    // Mit 0 initialisieren
    foreach (string s in stringList)
        stringOccurence[s] = 0;

    // Kopie erzeugen
    List<string> result = new List<string>(stringList);
    // Alle Elemente entfernen, die vorher schonmal aufgetreten sind
    // (und dabei mitzählen, dass sie aufgetreten sind)
    result.RemoveAll(x => (stringOccurence[x]++ > 0));
    return result;
}

Ah, hier wäre noch eine vierte LINQ-Variante


// ignoriert die Reihenfolge
private static List<string> ohneDoppelte(List<string> stringList)
{
    return stringList.Distinct().ToList();
}

beste Grüße
zommi

Hy zommi,

könntest du vllt ein paar kurze kommentare dazu schreiben was du da machst?

auf jeden fall ist es sehr übersichtlich und es funktioniert.

Danke

Habe oben noch Kommentare eingefügt.

Die erste beiden und die vierte Variante nutzen die LINQ-Extensions ab .NET 3.5.
Daher hab ich noch eine Variante 3 hinzugefügt, die auch mit .NET 2.0 funktionieren sollte, da sie nur das Dictionary<,> verwendet.

Die Idee ist aber bei allen, dass eine zusätzliche Hash-basierte Collection verwendet wird, der die Eigenschaft doppelte Einträge zu entfernen inhärent ist.
Dadurch, dass die hash-basierten Collections im Idealfall einen Zugriff in O(1) ermöglichen, reduziert sich in allen Fällen die Laufzeit auf O(n), im Vergleich zum O(n^2) deiner verschachtelten Schleife.

beste Grüße
zommi

Hallo impact_1991,

auch wenn das Löschen von Duplikaten ein besonderer Spezialfall von [FAQ] Auflistungs-Elemente suchen und entfernen ist, der nach einem Dictionary/HashSet bzw. nach Linq schreit, sind in der FAQ doch einige Anmerkungen enthalten, die von grundsätzlichem Interesse sind.

herbivore

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"