Doppelte Einträge in einer LinkedList entfernen

[AND51]

Hallo!

Wollte der Community mal nen Code stiften, da dachte ich an einen, der doppelte Einträge aus einer LinkedList entfernt.

Es gibt drei verschiedene Prozeduren für Long.l, Quad.q und String.s; wenn ihr andere Typen braucht (.c, .w oder so, dann ändert die vorhanden Prozeduren einfach ab).
Sie sind schon so gut wie nicht mehr optimierbar, da der Algorithmus so arbeitet:

Es wird nicht jedes mit jedem Element verglichen, sondern nur jedes Element mit jedem nachfolgenden. Das macht die Sache so schnell.

Code: Alles auswählen

EnableExplicit

Procedure FilterListL(LiLi.l())
	ForEach LiLi()
		Protected *element=@LiLi(), element.l=LiLi()
		While NextElement(LiLi())
			If LiLi() = element
				DeleteElement(LiLi())
			EndIf
		Wend
		ChangeCurrentElement(LiLi(), *element)
	Next
EndProcedure

Procedure FilterListQ(LiLi.q())
	ForEach LiLi()
		Protected *element=@LiLi(), element.q=LiLi()
		While NextElement(LiLi())
			If LiLi() = element
				DeleteElement(LiLi())
			EndIf
		Wend
		ChangeCurrentElement(LiLi(), *element)
	Next
EndProcedure

Procedure FilterListS(LiLi.s())
	ForEach LiLi()
		Protected *element=@LiLi(), element.s=LiLi()
		While NextElement(LiLi())
			If LiLi() = element
				DeleteElement(LiLi())
			EndIf
		Wend
		ChangeCurrentElement(LiLi(), *element)
	Next
EndProcedure

NewList myList.l()
Repeat ; Filling List with 999 random numbers from 1 - 6
	AddElement(myList()) : myList()=Random(5)+1
Until CountList(myList()) = 999
FilterListL(myList())

; Debugging list. There should be all numbers from 1 - 6 but only once
ForEach myList()
	Debug myList()
Next

Verbesserte Versionen sind immer herzlich willkommen! Viel Spaß damit!

[ts-soft]

>> Verbesserte Versionen sind immer herzlich willkommen!
Naja, eine Version mit Typ als Parameter, wobei long default ist.
Aber die meisten LL sind strukturiert, dafür eine Lösung wäre interessanter

[AND51]

> Naja, eine Version mit Typ als Parameter, wobei long default ist.
Ich habe mir auch schon überlegt, wie man das in eine Prozedur packen könnte, aber wenn ich in der Parameter-Zeile das .l weglasse, wird es ja per default dahingesetzt.
Mir ist leider nichts besseres eingefallen...

> Aber die meisten LL sind strukturiert, dafür eine Lösung wäre interessanter
Richtig, finde ich auch. Auch daran habe ich schon gedacht, aber: Ich kann zwar mit Strukturen an sich umgehen, aber ich wüsste nicht, wie ich eine LinkedList mit unbekannter Struktur annehmen sollte (so wie die Funktion SortStructureList()).
Wenn ich das könnte, dann wäre Idee 1 auch kein Problem, denke ich.


Mit diesem Beitrag wollte ich jedoch vor allem die Idee abliefern, wie man eine LinkedList optimal von Dubletten befreit! Nämlich, dass man nicht jedes Element mit jedem vergleicht, sondern nur jedes Element mit den nachfolgenden.

[Froggerprogger]

Ein paar Anmerkungen und Optimierungsvorschläge zu deinem Verfahren:
Asymptotisch ist deine Laufzeit noch genausoschnell, wie wenn trivialerweise jedes mit jedem Element verglichen wird. Das heißt es ist vielleicht doppelt so schnell, wie das triviale Verfahren, aber auch bei riesigen Listen bleibt es nur doppelt so schnell. Andere Verfahren könnten bei immer größeren Listen im Verhältnis immer noch schneller sein, z.B. bei doppelter Listengröße viermal so schnell.

Hier weitere Möglichkeiten:

Die Liste habe n Elemente:
1) Vergleicht man jedes Element mit jedem, braucht man n*n = n^2 Vergleiche. Die Laufzeit ist also asymptotisch n^2.

2) Vergleicht man jedes Element mit allen nachfolgenden, braucht man n + (n-1) + (n-2) + ... + 2 + 1 = (n^2 + n) / 2 Vergleiche, also asymptotisch immernoch n^2.

3) Ist die Liste garantiert bereits sortiert, so genügt es, einfach die Liste von Anfang bis Ende durchzuschreiten und Mehrfachvorkommen direkt zu Entfernen, damit hat man eine Laufzeit von nur noch n Vergleichen, also asymptotisch n, und ist damit wesentlich schneller als 1) und 2).

4) Darf die Liste nach dem Entfernen von Dubletten eine andere Sortierung als zuvor aufweisen, so kann man zunächst die beliebig sortierte Liste sortieren, dafür braucht man bei gängigen Verfahren n*log(n) Schritte und kann danach Schritt 3) anwenden, also braucht man insgesamt n + n*log(n) Schritte, also asymptotisch n*log(n), was immernoch wesentlich schneller als 1) und 2) ist.

5) Muss die Liste nach dem Entfernen der Dubletten dieselbe Sortierung von zuvor aufweisen (wie in 1) und 2) sichergestellt), so kann man mit einem Trick trotzdem dieselbe asymptotische Laufzeit wie bei 4) erreichen.
* Erzeuge eine Hilfsliste, die in einer Struktur jeden Wert und dessen Position der Originalliste speichert (Laufzeit n)
* Sortiere Hilfsliste anhand der Werte (Laufzeit n*log(n))
* Entferne (Wert-)Dubletten in der Hilfsliste wie in 3) (Laufzeit n)
* Sortiere Hilfsliste anhand der Positionen (Laufzeit n*log(n))
* Lösche die Originalliste und schiebe die Werte aus der Hilfsliste in die Originalliste (Laufzeit n)
Insgesamt ist damit das Ergebnis dasselbe wie in 1) und 2), man kann also Dubletten aus beliebigen Listen entfernen, ohne die Reihenfolge zu verändern, und erhält dabei eine Laufzeit von: 3*n + 2*n*log(n), also asymptotisch immernoch n*log(n), was wesentlich schneller als 1) und 2) ist.

Es kann zwar sein, dass für Listen bis zu einer gewissen Größe, z.B. bis zu 50 Elementen die Version 2) die schnellste ist, aber ab einer gewissen Größe wird Version 5) garantiert die schnellste (für den allgemeinen Fall) sein.
Version 3) ist immer garantiert mit Abstand das schnellste Verfahren bei bereits sortierten Listen.

[edit]
Es kann allerdings durchaus vorkommen, dass sich eine asymptotisch 'bessere' Version erst ab z.B. 10000000000000 Elementen lohnt und damit für die Praxis wieder 'schlechter' ist. Hierfür muss man die Laufzeit genauer untersuchen, oder einfach Testimplementationen vergleichen.
[/edot]

[AND51]

> Ist die Liste garantiert bereits sortiert, so genügt es, einfach die Liste von Anfang bis Ende durchzuschreiten und Mehrfachvorkommen direkt zu Entfernen
Richtig, kann man auch so machen. Ich wollte hier lediglich eine Funktion reinstellen, die universell einsetzbar ist, also für sortierte als eben auch unsortiere Listen.

Freue mich, dass du dir hier so viel Mühe gibst und einen guten Beitrag reiinschreibst, hoffentlich wird aufgrunddessen noch eine andere Filter-Methode hier reingestellt