Moderationshinweis von herbivore
(11.08.2010 - 10:15)
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!
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;
}
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.
// 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;
}
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
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von zommi am .
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.
