| 

.NET C# Java Javascript Exception

3
Wie kann ich aus einer Liste Duplikate entfernen, ohne die Reihenfolge zu ändern? Meine Liste ist einige 100.000 Einträge lang, also sollte der Algorithmus nicht zu langsam sein.
News:
28.08.2009
Maddinel 145 2 4
Angenommen Deine Liste enthielte.
a,b,c,d,b,f,g,h
Ganz offensichtlich muss b entfernt werden,
aber welches? In beiden Fällen wird aber "Reihenfolge".
Ohne weitere Angaben ist die Frage Unfug
stefan.bachert 11.09.2009
Wenn man es so nimmt ist der Begriff "Reihenfolge" schon Unfug. Mathematisch betrachtet gibt es eine Folge und eine Reihe. Wobei die Reihe aus den Partialsummen der Folgeglieder besteht ;)
gfoidl 11.09.2009
5 Antworten
2
Mit einem HashSet geht das am effizientesten. Siehe dazu Duplikate aus IEnumerable<T> entfernen bzw. unterschiedliche Elemente holen für mehr Infos.
28.08.2009
gfoidl 9,4k 3 5
gfoidl 9,4k 3 5
Wie kann ich damit die Reihenfolge beibehalten?
Maddinel 28.08.2009
Hast du den Link verfolgt? Da wird die Reihenfolge beibehalten.
gfoidl 28.08.2009
Günther, das ist ein "schweins cooler" Ansatz :-)
klaus_b 28.08.2009
Klaus ist das jetzt positiv oder positiv gemeint ;)
gfoidl 28.08.2009
Such dir eins aus, Günther.
Dickes Lob für den Ansatz mit dem HashSet<T>. So einfach wie genial. So muss Code sein.
klaus_b 28.08.2009
Ja sehr gut.
Maddinel 28.08.2009
Danke für die Blumen ;) Es ist besonders schön wenn hoch geschätzte Kollegen so etwas berichten.
gfoidl 28.08.2009
Der Link von gfoidl geht mittlerweile ins Nirwana. Weiß jemand, ob die Seite noch irgendwo zu erreichen ist?
Matthias Hlawatsch 22.03.2011
Da mein Space gelöscht wurde (während ich in Hiatus war) kann der Link nicht mehr gehen ;-)

Dasselbe findet sich unter
http://www.mycsharp.de/wbb2/thread.php?threadid=72891
gfoidl 20.05.2011
Hab oben den Link auch korrigiert.
gfoidl 20.05.2011
2
Die Erweiterungsmethode Enumerable.Distinct kannst Du auf eine beliebige Collection, die IEnumerable implementiert, anwenden. Sie liefert Dir genau das zurück: Die Collection in der gleichen Reihenfolge wie ursprünglich, aber ohne Duplikate.
18.02.2011
Golo Roden 2,7k 3 9
1
"More Effective C#" behandelt diese Frage als Beispiel für den Einsatz von yield. In etwas so:

public static IEnumerable<T> Unique (IEnumerable<T> inp) {
var valset = new HashSet<T>;
foreach (T t in inp) {
if (valset.Add (t)) {
yield return t;
}
}
}
08.09.2009
pjacobi 1,1k 2 7
0
<snip> ohne die Reihenfolge zu ändern?
Das ist der Kackpunkt. Damit ist ein Algorithmus mit einer Vorsortierung ausgeschlossen.
Ein wichtiger Punkt währe zu wissen: sind in der Liste wirklich nur Doubletten, also max. Vorkommen eines Elements == 2, oder kann ein Element auch 3 und 4mal enthalten sein?
Das währe die ungünstigste Voraussetzung, denn dann wird das Entfernen ein O(Log n)-Vorgang.

<snip> also sollte der Algorithmus nicht zu langsam sein.
Je genauer du deine Liste beschreibst umso leichter kann man dir einen Vorschlag unterbreiten.

Servus,
Klaus
28.08.2009
klaus_b 1,6k 3 7
Es können beliebige Anzahlen vorkommen.
Maddinel 28.08.2009
0
So wie ich das sehe muss hier auf jeden Fall sortiert werden.
Was du aber probieren kannst ist folgendes:
Pack die Werte erstmal in ein 2-dimensionales Array. In Dimension 1 kommen deine Werte rein. In Dimension 2 nummerierst Du diese Werte durch (von 1 bis n) anschliessend sortierst Du die erste Dimension (und nimmst dabei natürlich die zweite entsprechend mit). Nun folgt ein einfacher Gruppenwechsel wobei du doppelte Einträge entfernst. Im letzten Schritt sortierst Du nach der zweiten Dimension und hast nun in der ersten jeden Wert nur einmal in der ursprünglichen Reihenfolge.
08.09.2009
Ralf D. 89 2

Stelle deine .net-Frage jetzt!
TOP TECHNOLOGIES CONSULTING GmbH