PureBoard

Das deutsche PureBasic-Forum
https://www.purebasic.fr/german/

Duplikate aus LinkedList entfernen

https://www.purebasic.fr/german/viewtopic.php?t=21173

Seite 2 von 2

Re: Duplikate aus LinkedList entfernen

Verfasst: 27.10.2009 17:40
von dige
Müsste man glatt mal testen. Jedenfalls sind die Sortieralgos von Fred sehr gut optimiert und du musst
dann bei dem Filterdurchlauf die Liste nicht mehrfach durchsuchen..

Re: Duplikate aus LinkedList entfernen

Verfasst: 27.10.2009 21:06
von Kiffi
dige hat geschrieben:Müsste man glatt mal testen.
dige, Du wagst es wirklich, die Aussage von AND51 infrage zu stellen? :shock:

;-)

Re: Duplikate aus LinkedList entfernen

Verfasst: 28.10.2009 01:10
von AND51
Kiffi hat geschrieben:
dige hat geschrieben:Müsste man glatt mal testen.
dige, Du wagst es wirklich, die Aussage von AND51 infrage zu stellen?
Ab jetzt nicht mehr :mrgreen:

Habs getestet und schon bei 10.000 Elementen ist meine Prozedur sofort fertig (0 ms), während seine 47 ms braucht.
Bei 1.000.000 Elementen ist der Unterschied schon gravierender: 109 ms gegen 1031 ms!
//edit :
Bei 10.000.000 Elementen ist der Unterschied noch größer: 1.453 ms gegen 13.344 ms!

Hier der Testcode. Ohne Debugger ausführen, bei aktiviertem Debugger sieht man nur, ob die Prozeduren auch korrekt arbeiten. Da meine Prozedur keine zusätzliche lfn braucht, ist die Liste von mir auch nicht strukturiert.

Code: Alles auswählen

EnableExplicit
Structure nurSo
	lfn.l
	id.i
EndStructure
NewList MyLL1.i()
NewList MyLL2.nurSo()

Define x=0
Repeat
	x+1
	AddElement(MyLL1())
	MyLL1()=Random(5)+1 ; wir würfeln, 1 bis 6
	AddElement(MyLL2())
	With MyLL2()
		\lfn=x
		\id=Random(5)+1 ; wir würfeln, 1 bis 6
	EndWith
Until x = 1e6


Procedure AND51(List Liste())
   ForEach Liste()
      Protected *vergleichsElement=@Liste() ; Pointer und Wert des aktuellen
      Protected vergleichsWert=Liste() ; Elements speichern und...
      While NextElement(Liste()) ; ...mit allen NACHFOLGENDEN Elementen vergleichen
         If Liste() = vergleichsWert
            DeleteElement(Liste(), 1) ; bei Fund Dublette löschen
         EndIf
      Wend ; diese Schleife blättert die LinkedList bis zum Ende durch
      ChangeCurrentElement(Liste(), *vergleichsElement) ; zum Ausgangselement zurückkehren, damit ForEach zum nächsten Vergleichselement springt
   Next
EndProcedure

Procedure dige(List Liste.nurSo())
	SortStructuredList(Liste(), #PB_Sort_Ascending, OffsetOf(nurSo\id), #PB_Sort_Integer)
	ResetList(Liste())
	While NextElement(Liste())
		Protected vergleichsWert=Liste()\id
		Protected *vergleichsElement=@Liste()
		While NextElement(Liste())
			If Liste()\id = vergleichsWert
				DeleteElement(Liste())
			Else
				Break
			EndIf
		Wend
		ChangeCurrentElement(Liste(), *vergleichsElement)
	Wend
	SortStructuredList(Liste(), #PB_Sort_Ascending, OffsetOf(nurSo\lfn), #PB_Sort_Long)
EndProcedure


Define zeit1=ElapsedMilliseconds()
AND51(MyLL1())
zeit1=ElapsedMilliseconds()-zeit1

Define zeit2=ElapsedMilliseconds()
dige(MyLL2())
zeit2=ElapsedMilliseconds()-zeit2

MessageRequester("Dubletten Filtern", "AND51: "+Str(zeit1)+" ms"+#CRLF$+"dige: "+Str(zeit2)+" ms", #MB_ICONINFORMATION)

CompilerIf #PB_Compiler_Debugger
	Debug "Kontrolle AND51"
	ForEach MyLL1()
	   Debug MyLL1()
	Next
	Debug "Kontrolle dige"
	ForEach MyLL2()
	   Debug Str(MyLL2()\id)+"........"+Str(MyLL2()\lfn)
	Next
CompilerEndIf

Re: Duplikate aus LinkedList entfernen

Verfasst: 28.10.2009 01:14
von Kaeru Gaman
aussagekräftig sind nur der zweite und dritte test, und der Unterschied ist identisch: Faktor 10

Re: Duplikate aus LinkedList entfernen

Verfasst: 28.10.2009 02:31
von freak
AND51 hat geschrieben:
Kiffi hat geschrieben:
dige hat geschrieben:Müsste man glatt mal testen.
dige, Du wagst es wirklich, die Aussage von AND51 infrage zu stellen?
Ab jetzt nicht mehr :mrgreen:
Na, da ist aber einer mächtig überzeugt von sich. Da tut es mir schon fast leid dir die Illusionen zerstören zu müssen :)

Dein Test ist ziemlich nutzlos weil er den absoluten best-case Input für deinen Code testet. Bei 100.000 Elementen und 6 Werten sind ja 99.994% der Elemente Duplikate. Das ist dann doch sehr unrealistisch für eine reale Anwendung. Teste mal den absoluten worst-case Fall (alle Elemente verschieden), da kann dein Code total einpacken während die Methode von dige immernoch akzeptable Ergebnisse liefert. Auch bei eher realistischen Eingaben (zum Beispiel jedes 2. Element ein Duplikat) hat dein Code keine Chance mehr.

Sowas braucht man aber auch nicht testen, das beweist man... ;)
  • AND51's Code muss bei n Elementen den inneren Loop bis zu n-mal laufen lassen und immer von der aktuellen Position bis zum Ende gehen. Das ergibt eine Laufzeit von O(n^2).
  • dige's Methode sortiert 2x (Das Listensortieren hat eine worst-case Laufzeit von O(n*log n)) und macht einen linearen Durchlauf für die Eliminierung der Duplikate, das ergibt eine Gesammtlaufzeit von O(n*log n). Das ist erheblich besser.
Fazit:
Das 2x Sortieren fällt bei großen Listen nicht mehr wirklich ins Gewicht weil das nur ein konstanter Faktor ist. Der verschachtelte Loop von AND51 dagegen wird schnell zum Killer wenn es sich nicht gerade um eine Liste mit nur Duplikaten handelt. Wenn man aber eh nur 500 Elemente in der Liste hat dann ist die Methode auch wieder egal, da Langweilt sich ein moderner Prozessor trotzdem noch zu Tode.

Vielleicht war das mit dem in Frage stellen doch nicht so eine schlechte Idee... :lol:

Re: Duplikate aus LinkedList entfernen

Verfasst: 28.10.2009 09:59
von Froggerprogger
Um freaks 2W20+10 Attacke fortzuführen:

Kiffis Map-Methode benötigt lediglich Laufzeit O(n), denn eine (Hash)Map benötigt (wachsen nicht mitgerechnet) Zeit O(1) zum Einfügen und Testen. Allerdings sind die Konstanten bei der Map relativ groß (müsste man ebenfalls mal zum Vergleich heranziehen).

Die schnellstmögliche mir erdenkbare Version kann man verwenden, wenn in der jeweiligen Anwendung die Werte der Liste nicht zu groß werden können, so dass man sie als Array-Index (a la Counting-Sort) nutzen kann: Dann benötigt Markieren und Testen ebenfalls nur O(1), ist aber wesentlich schneller, als in einer Map, und man erhält somit wieder Laufzeit O(n).

Ergo: Hier die schnellstmögliche Variante, falls die Werte der Liste durch #MaxValue beschränkt sind (ließe sich auch noch etwas verallgemein, wenn die Werte in einem Bereich zwischen einem #MinValue und #MaxValue liegen mit (#MaxValue - #MinValue) nicht zu groß.)

Code: Alles auswählen

NewList MyLL()

AddElement(MyLL()) : MyLL() = 1
AddElement(MyLL()) : MyLL() = 4
AddElement(MyLL()) : MyLL() = 2
AddElement(MyLL()) : MyLL() = 3
AddElement(MyLL()) : MyLL() = 4
AddElement(MyLL()) : MyLL() = 1
AddElement(MyLL()) : MyLL() = 6

#MaxValue = 100000 ; maximaler Wert eines Eintrags in der Liste
Dim Buckets(#MaxValue)

ForEach MyLL()
 
  If Buckets(MyLL())
    DeleteElement(MyLL())
  Else
    Buckets(MyLL()) = #True
  EndIf
Next

ForEach MyLL()
  Debug MyLL()
Next
:D

Re: Duplikate aus LinkedList entfernen

Verfasst: 28.10.2009 15:35
von Little John
freak hat geschrieben:Sowas braucht man aber auch nicht testen, das beweist man... ;)
  • AND51's Code muss bei n Elementen den inneren Loop bis zu n-mal laufen lassen und immer von der aktuellen Position bis zum Ende gehen. Das ergibt eine Laufzeit von O(n^2).
  • dige's Methode sortiert 2x (Das Listensortieren hat eine worst-case Laufzeit von O(n*log n)) und macht einen linearen Durchlauf für die Eliminierung der Duplikate, das ergibt eine Gesammtlaufzeit von O(n*log n). Das ist erheblich besser.
So ist es.
Erfreulich zu sehen, dass bei dieser Geschwindigkeitsdiskussion doch noch Überlegungen aus der Komplexitätstheorie zur Sprache kommen. :twisted:

Gruß, Little John

Re: Duplikate aus LinkedList entfernen

Verfasst: 28.10.2009 18:32
von freak
> Um freaks 2W20+10 Attacke fortzuführen:

Was ist das denn?

> Kiffis Map-Methode benötigt lediglich Laufzeit O(n)

Stimmt, die Map-Methode habe ich gar nicht beachtet. Damit hat Kiffi gewonnen :)

> Erfreulich zu sehen, dass bei dieser Geschwindigkeitsdiskussion doch noch Überlegungen aus der Komplexitätstheorie zur Sprache kommen.

Das ist doch der lustigste Teil an dem Ganzen. Wie Donald Knuth schon sagte "Beware of bugs in the above code; I have only proved it correct, not tried it." :mrgreen:

Re: Duplikate aus LinkedList entfernen

Verfasst: 28.10.2009 18:41
von Kiffi
freak hat geschrieben:Damit hat Kiffi gewonnen :)
Bild

Was habe ich gewonnen? Eine PB-Mobile-Edition? :allright:

Grüße ... Kiffi

Re: Duplikate aus LinkedList entfernen

Verfasst: 28.10.2009 20:42
von Little John
freak hat geschrieben:Das ist doch der lustigste Teil an dem Ganzen. Wie Donald Knuth schon sagte "Beware of bugs in the above code; I have only proved it correct, not tried it." :mrgreen:
Na klar, ihn als Prof. interessiert vor allem der Beweis. Die langweiligen Details lässt er als Übung für die Studenten. :D
Kiffi hat geschrieben:Was habe ich gewonnen?
Ein Wochenende wahlweise mit Zensursula oder Guido. Der Gewinn kann nicht abgelehnt werden! :mrgreen:

Gruß, Little John
Alle Zeiten sind UTC+02:00
Seite 2 von 2

Powered by phpBB® Forum Software © phpBB Limited

Deutsche Übersetzung durch phpBB.de