Ole Laursen <[EMAIL PROTECTED]> writes:
> > Jeg har lavet en sorteringsalgoritme som bruger et bin�rt tr�, i
> > stedet for en QuickSort. Jeg startede jo med quicksort, men efter
> > at have brugt adskillige timer p� at debugge de forbandede
> > pointere (i Delphi, da gdb ikke var s�rlig informativ) besluttede
> > jeg at pr�ve med et tr� i stedet for.
>
> Problemet med tr�sorteringen er bare at metoden bliver faktisk det
> samme som sammens�tningssorteringen.
Rent faktisk, s� laver en tr�sortering liges� mange sammenligninger
som en Quicksort, i f�lge papirerne.
> Det bliver jo s� ogs� n�sten umuligt at sammenligne metoderne
> eftersom det smarte med et tr� jo f�rst kommer n�r man forts�tter
> med at opbevare dataene p� den form.
Ja, det er jeg godt klar over. Men normalt sorterer man jo netop ogs�
data for at kunne finde noget hurtigt igen. Der er jo fordelen ved et
tr�: har man 1024 elementer (og tr�et er balanceret nogenlunde
ordentligt) s� skal man kun lave h�jst 10 sammenligninger for at finde
det, mens man skal lave cirka 512 sammenligninger med en k�ded liste.
Det er da smart, samtidig med at koden der skal til for at
vedligeholde et bin�rt tr� er simpel.
> Har du det andet kode du fremstillede? Algoritmen er jo ikke s�
> lang, det m� v�re muligt at finde fejlen.
Problemet var, at jeg �ndrede p� listen da jeg skulle smide elementer
over p� h�jre eller venstre side af min pivot. Koden er faktisk med i
pakken - pivotsortering.pas.
Til sidst blev jeg s� tr�t af at sidde og rode rundt, at jeg lavede et
tr� i stedet for.
> > Da et tr� er bedst til at s�ge i, skulle vi m�ske lave lidt
> > s�geri, bare for at demonstrere at det g�r hurtigt? Vi kunne ogs�
> > bruge den danske ordliste med over 300.000 ord... Programmet g�r
> > dog s� ned hos mig, da det sluger over 200 MB ram :-)
>
> Det m� alts� v�re et eller andet galt her. Har du for�vrigt tjekket
> at ordene bliver sorteret rigtigt? Grundet til at jeg tog den
> engelske liste, var netop at s� undg�r vi alle potentielle problemer
> mht. danske bogstaver osv.
Ordene bliver sorteret s�dan som man kunne forvente: efter tegnenes
ASCII-v�rdier. Grunden til at jeg pr�vede med den danske liste, var
for at se hvordan det virkede n�r vi havde *rigtig* mange ord.
> > Med 300.000 ord, fylder de k�dede lister vist omkring 20MB
> > stykket, og tr�et fylder endnu mere... Det ser ikke ud til at
> > hukommelsen bliver frigivet lige med det samme (n�r man kalder
> > slet_liste eller TreeDelete)
>
> Hukommelsen plejer vist ikke at blive frigivet til systemet med det
> samme, men burde blive genbrugt internt i programmet. Mystifistisk.
Det var ogs� det jeg forventede.
> > Jeg har ogs� pr�vet at lave noget sjov statistik med mit tr�,
> > f.eks. hvor dybt det bliver og s� videre. Det viste sig, at dybden
> > l� p� omkring 20 n�r filen er rodet rigtigt godt sammen (1000% :-)
> > mens den steg til over 15.000 n�r filen kun var rodet 5% sammen.
> > S� kan man jo t�nke lidt over det :-)
>
> Klart nok - n�r de er sorterede, f�r du en n�sten almindelig k�de.
> Det er derfor at hvis vi skulle have kigget p� tr�er, s� skulle vi
> have kigget p� en smart (men ret indviklet) metode til at undg�
> dette f�nomen.
Det er ikke s� indviklet endda - koden fylder dog lidt mere (2 sider).
Som du nok ved, s� drejer det sig om at man roterer visse dele af
tr�et n�r man inds�tter og fjerner elementer. If�lge min bog, skal man
cirka igang med at /balancere/ tr�et hver anden gang man inds�tter et
element.
> > Sidste ting: Selv om jeg har pr�vet at rette Makefilen til, s�
> > bliver det nye unit ikke kompileret med... Kan du se hvorfor, Ole?
>
> Du skulle have brugt sm� bogstaver i stedet for store (ligesom jeg
> havde gjort). Da jeg skrev makefilen, fandt jeg ud at
> Pascal-overs�tteren faktisk selv automatisk kan finde ud at lave det
> meste af det som make g�r. Men den oms�tter �benbart de store
> bogstaver til sm� (der er jo ikke nogen der ved deres fulde fem har
> filer med store bogstaver under Unix :-) n�r den skal have fat i
> filnavnet.
Aha...
> Lige lidt kritik af den m�de du har skrevet koden p�: det er alts�
> noget rod med den m�de du sammenblander dansk og engelsk, samt det
> med de store og sm� bogstaver.
Jeg blander da ikke dansk og engelsk sammen. Jeg skriver koden p�
engelsk, og t�nkte s� at jeg hellere m�tte skrive kommentarerne p�
dansk, da I ellers sikkert ville g� helt amok.
> Det kommer alts� ikke til at se s�rligt k�nt ud hvis vi ikke skriver
> koden i den samme stil, med nogenlunde samme indrykning osv. Grunden
> til at jeg skyndte mig at f� lavet sammens�tningsalgoritmen, var
> netop at jeg h�bede at folk s� kunne efterligne den s� vi fik noget
> der s� ensartet ud.
Personligt har jeg det rigtig skidt med alle de ���'er der er blevet
"escaped" til ae oe aa. Det ser i mine �jne mystisk ud n�r man har en
funktion der hedder 'sammensaetningssortering' - ordene flyder sammen
og indeholder 'tegn' der ikke findes i normal dansk (ae).
M�ske vi skulle bruge nogle underscores (_) til at dele ordene med?
Eller ogs� kunne vi g�re ligesom i Delphi og mange andre steder: bruge
store og sm� bogstaver til at adskille ordene.
> Men pr�v at send det andet kode du n�ede frem til: jo flere
> �jen�bler, jo mere lavvandet bliver det jo, som man siger. :-)
Det skulle gerne v�re med i den sidste mail.
--
Best regards,
Martin Geisler
Checkout http://www.gimpster.com for:
PHP Weather => Shows the current weather on your webpages.
PHP Shell => A telnet-connection (almost :-) in a PHP page.
