Sorteringsalgoritme?
Nikolaj Hansen
*Ak - jeg ved godt at det her er første års pensum
*på datalogi, men jeg har glemt det:
*Jeg vil gerne indbygge en sorteringsfunktion i mit
*PILS programmeringssprog.
*Emnerne der skal sorteres, ligger som en stribe
*referencer. De skal byttes rundt, til de ligger i
*orden.
*Sorteringsnøglerne er typisk tekststrenge, der
*skal sorteres i "national" orden.
*D.v.s. sammenligning er dyr, ombytning er billig.
*Der skal kunne sorteres lister så lange som
*computerens RAM tillader.
*Generel anvendelighed er vigtigere end marginale
*hastighedsforskelle, altså: en jævnt hurtig
*algoritme skal foretrækkes fremfor en superhurtig
*der er langsom i bestemte tilfælde.
*Alt andet lige må der gerne tage hensyn til paging.
*Jeg kan desværre kun huske algoritmernes navne:
*mergesort, quicksort, shellsort... husker ikke
*hvad de går ud på.
*Er der en venlig sjæl der har noget kode eller
*pseudokode liggende til en passende algoritme og
*gider poste det i en e-mail? Sprog underordnet,
*jeg genskriver det i intel 386 assemblerkode.
*bee illNOsy
-- Sortering maa da vaere den sidste udvej. Kan du ikke
saette nye elementer ind i den rigtige raekkefoelge?
while (Ledig ram){
for (int i=0; i < felt; i++)
felt = nyt element;
}
}
Dvs. at du starter nedefra og koerer opad i din liste
indtil du moeder et felt, der er mindre end dit nye ele-
ment. Hvis du goer det hver gang vil listen vaere sorteret.
Hvis du koder Objekt Orienteret kan dette saettes ind i ob-
jektets indsaetningsrutine.
Hvis du vil have en sorteret fil/Liste må du under alle om-
stændigheder sammenligne. Er der nogen der er uenige i det?
Yours truly:
##****************************************************##
##* E-MAIL : dat9...@mini01.vejlees.dk *##
##* Name : Anders Nikolaj Hansen *##
##* Occupation : Datamatician, Computer science *##
##* "Wandering between two worlds, one dead *##
##* one powerless to be born.." *##
##* - Matthew Arnold *##
##****************************************************##
Kurt Friis Hansen
| -- Sortering maa da vaere den sidste udvej. Kan du ikke
| saette nye elementer ind i den rigtige raekkefoelge?
| while (Ledig ram){
| for (int i=0; i < felt; i++)
| felt = nyt element;
| }
| }
| Dvs. at du starter nedefra og koerer opad i din liste
| indtil du moeder et felt, der er mindre end dit nye ele-
| ment. Hvis du goer det hver gang vil listen vaere sorteret.
Det er altså ikke nogen god løsning, medmindre din liste er konstant fra
dag til dag, og der kun indsættes nogle få elementer.
Yderligere er din specielle lineære søgning/sammenligning ekstremt langsom.
Lad os sige, at du har 1000 elementer i din liste. Og du skal indsætte 1
element. Du kan i værste tilfælde risikere at lave 1000 sammenligninger,
inden du ved, hvor du skal "indsætte".
Brug i stedet binær søgning, der fungerer efter princippet del og hersk.
Lidt firkantet formuleret, virker den sådan: Du sammenligner først med det
midterste element i listen (1000/2 = 500). Hvis dit element er større end
element 500, kan du glemme alt fra element 1 til element 501. Du tager nu
og finder midten af den mulige "halvdel" af elementer (501 til 1000) - dvs.
nu sammenlignes element 750, og du kan igen indsnævre mulige elementer til
f.eks. området 501 til 749. Osv. Rutinen kaldes binary søgning, og klarer
at finde et match (eller indsætningspunkt) på 10 opslag.
| Hvis du koder Objekt Orienteret kan dette saettes ind i ob-
| jektets indsaetningsrutine.
Uanset om det laver det objektorienteret eller ej, er din rutine "mindre
heldig". Den er måske let at overskue, men sorterings- og søgerutiner, der
både virker og er hurtige, er absolut ikke lette at fremstille...
Der er lidet kendte fordele og ulemper ved mange rutiner. F.eks. er den
næsten universelt anvendte "quicksort" rutine virkeligt god til at sortere
ting, der befinder sig i et håbløst rod. Har man derimod noget
pre-sorteret, og skal tilføje et par enkelte elementer, tenderer den mod
det ulideligt langsomme (det er dette, mange overser).
Din metode er derimod velegnet, hvis man har to lister, der er nogenlunde
lige store, og som begge rummer sorterede elementer. Du kan anvende
billedet "riffelblanding" fra kortspil som udgangspunkt.
Det er FORMÅLET og/eller UDGANGSMATERIALET, der afgør, hvilken
fremgangsmåde/sorteringsalgoritme, der er den mest velegnede.
Knuth har lavet et digert værk:
"The art of computer programming" Volume 3
"Sorting and Searching"
Addison Wesley
ISBN 0-201-03803-X
der behandler alle fordele og ulemper i praktisk taget alle afskygninger af
rutiner indenfor sortering og søgning. Den bog er *bibelen* på det felt.
| Hvis du vil have en sorteret fil/Liste må du under alle om-
| stændigheder sammenligne. Er der nogen der er uenige i det?
Nej. Men mængden af sammenligninger har betydning for hastigheden. Det er
der mange, der glemmer. Ved store sorteringer (f.eks. når der skal oprettes
et nyt sæt nøgler efter hidtil ukendte sorteringskriterier i en database
over f.eks. ansatte i AP-Møller, SAS, ØK osv.), er det ret vigtigt at
spare sammenligninger... Eller en sorteret list over beløbsstørrelser og
antal forekomster af enkeltbeløb i det totale antal af daglige
kontobevægelser i den danske bank - ikke fordi, jeg kan forestille mig,
hvad dette sidste eksempel skulle kunne bruges til, men blot som en
"appetitvækker" til en omfangsrig sortering.
I gamle dage - da man havde line-printers - var der faktisk en virksomhed,
der lavede en beslægtet undersøgelse. Man havde opdaget, at visse
"typehjul" eller "typebånd" skulle udskiftes ret hyppigt, selv om det kun
var enkelte tegn, der var "slidt". Det var ret dyrt i længden, så man
lavede en statistik over det materiale, man udskrev, og fik lavet nogle
"rotationsordninger" for "hjulene/båndene" i de enkelte tegnpositioner i en
udskriftslinje, så "sliddet" blev mere ligeligt fordelt på de enkelte
"typehjul/bånd". Der var tale om pæne besparelser. Om de var store nok til
også at betale for "flytteriet", ved jeg ikke - men omkostningerne blev i
hvert fald flyttet til en anden konto. Det er besynderligt nok meget
vigtigere end ægte besparelser - i en række virksomheder! Tro det eller
ej...
Venlig hilsen og smil
Kurt Friis Hansen
Venlig hilsen/Best regards/Viele Gruesse
Kurt Friis Hansen - kfr...@aix1.danadata.dk
Peter Skov Knudsen
>>while (Ledig ram){
>> for (int i=0; i < felt; i++)
>> felt = nyt element;
>> }
>>}
>Lad os se bort fra denne fejl og gå videre til den indre løkke.
>I dette tilfælde er 'Felt' invariant i løkken, så antager vi
>at 'Felt' har værdien n før første gennemløb, opnår du ikke
>andet end at tildele variablen 'felt' værdien 'nyt element'
>n gange.
Ups, vi tager den igen:-)
Lad os se bort fra denne fejl og gå videre til den indre løkke.
I dette tilfælde er 'nyt element' invariant i løkken, så antager vi
at felt>0, 'nyt element' har værdien n før første gennemløb, opnår du ikke
andet end at tildele variablen 'felt' værdien 'nyt element'
n gange.
Peter
Ole Nielsby
->Anders N.H.:
Det du beskriver er vistnok en slags boblesort.
Den er håbløst langsom til store lister.
->Kurt H:
Den binære søgning er god til indsættelse af
enkelte elementer. Det jeg søger er en allround
sortering, der både egner sig til fletning af
lister og sortering af blandede data. Tak for
henvisningen til Knuth, jeg har den ikke men
kommer måske i nærheden af DAIMIs bibliotek...
->Peter K.:
Jeg er helt enig i at Anders ikke ved hvad
han snakker om. Men hva' om du havde brugt
den tid du har brugt på at fortælle ham det
på at fortælle mig hvilken algoritme du ville
vælge og evt. daske den ind??? Den bedste
læremester er vel et godt eksempel, ik'sandt?
(Undskyld den pædagoooooooogiske tone; jeg har
gået på seminarum engang og blev lettere skadet.)
---
Jeg skal bl.a. bruge sorteringen til ordlister
til et engelsk-dansk oversætterprogram - både
til indsætning af nye ord og til administration
af ordlisterne, f.eks. sortering efter hyppighed
eller bøjningsmønstre.
En typisk anvendelse vil være at smide en
supplerende ordbog på et par hundrede eller
tusinde gloser bagi en hovedordbog på 50-100.000
ord og sortere. (Det forudsætter selvfølgelig,
at der er andre end mig der hælder ord i
systemet.)
Jeg tror Mergesort er velegnet - den vil have
rimelige paging-egenskaber da den starter med
at sortere "lokalt". Om de andre er en tak
hurtigere, er underordnet.
Jeg mangler bare en enkelt ting: Hvordan fletter
man to afsnit uden unødige blokflytninger eller
ekstra pladsforbrug? P.T. kopierer jeg det ene
afsnit til en buffer - kan dette undgås?
(Problemet er ikke så grelt da det kun er
pointere jeg kopierer.)
Ole Nielsby
Kim Steen Henriksen
[...]
>Jeg skal bl.a. bruge sorteringen til ordlister
>til et engelsk-dansk oversætterprogram - både
>til indsætning af nye ord og til administration
>af ordlisterne, f.eks. sortering efter hyppighed
>eller bøjningsmønstre.
>En typisk anvendelse vil være at smide en
>supplerende ordbog på et par hundrede eller
>tusinde gloser bagi en hovedordbog på 50-100.000
>ord og sortere. (Det forudsætter selvfølgelig,
>at der er andre end mig der hælder ord i
>systemet.)
Nu har jeg ikke helt fulgt med i diskussionen, men vil det ikke være hurtigere
blot at benytte et træ, hvor roden havde 26 børn (et for hvert bogstav), disse
børn har ligeledes 26 børn osv.
Når et ord indsættes, f.eks. "try" starter man ved roden, vælger "t", derefter
"r" (som barn af "t") og endelig "y". Så mærkes bogstavet "y" som lovlig
endelse på et ord.
Når man så slår et ord op i ordbogen, så starter man igen ved roden, vælger
"t" (hvis det er ordet "try") osv. og finder ud af, at sidste bogstav er
markeret som lovlig endelse. Ordet er altså legalt.
Prøver man med et ord, der ikke eksisterer, vil man ende på et bogstav, der
ikke er markeret som lovligt.
Den metode burde give MEGET hurtig søgning og indsættelse, og bruge næsten
ingen hukommelse.
--
Kim Henriksen, ki...@diku.dk, http://www.diku.dk/students/kimsh/
ASGER ALSTRUP NIELSEN
så han skrev:
>Er der en venlig sjæl der har noget kode eller
Prøv med følgende C-stump, som sorterer heltalene t[1] til t[j] i
stigende rækkefølge:
for (i = j/2; j > 1; t[l] = k) {
if (i) k = t[i--]; else { k = t[j]; t[j--] = t[1]; }
for (l = i + 1; (m = l + l) <= j; t[l] = t[m], l = m) {
if (m < j && t[m] < t[m+1]) m++;
if (t[m] <= k) break;
}
}
Komplet uforståelig kode for mennesker, men det virker.
For andre syge C-programmer, check
http://daisy.uwaterloo.ca/~tromp/pearls.html
Seriøst: Når du skal vurdere, hvilken sortering, du skal bruge, må
man vide lidt mere om forholdene, hvis man vil være helt sikker på
et godt valg.
Uden at kende meget om disse, kan man med god samvittighed vælge en af
de "sikre" sorteringsalgoritmer med værste tidskompleksitet O(log(n) n),
hvilket ikke kan gøres bedre i det generelle tidfælde.
Bemærk at Quicksort ikke hører til her, mens en anden "in-place" metode
som heapsort gør. Så kan det ikke gå helt galt, og forskellen til en
anden algoritme med tilsvarende kompleksitet vil dels udspringe fra
implementationsdetaljer, og dels subtile algoritmistiske egenskaber
som lokalitet, m.v..
I en konkret situation kan gevinsten ved at udnytte træk i inddata
dog være ganske markant, mens strukturelle ændringer i datastrukturene
også kan have enorm betydning. Derfor må man vurdere hele sammenhængen,
hvis man har et krav om optimal performance.
I mange situationer kan man argumentere for højst at kunne få lineær
tid selv med skræddersyede algoritmer, så tabet ved at bruge en generel
O(log(n) n) algoritme er (under antagelse af sammenlignelige tidskoeffi-
cienter) ofte i praksis til at bære.
Mvh
Asger Alstrup
Nikolaj Hansen
*dat9...@mini01.vejlees.dk (Nikolaj Hansen) writes:
*>-- Sortering maa da vaere den sidste udvej. Kan du ikke
*>saette nye elementer ind i den rigtige raekkefoelge?
*>while (Ledig ram){
*> for (int i=0; i < felt; i++)
*> felt = nyt element;
*> }
*>}
*Tja, "Ledig ram" er invariant i din løkke, så enten gennemløbes
*konstruktionen 0 gange, eller også har du lavet en uendelig løkke.
*Lad os se bort fra denne fejl og gå videre til den indre løkke.
*I dette tilfælde er 'Felt' invariant i løkken, så antager vi
*at 'Felt' har værdien n før første gennemløb, opnår du ikke
*andet end at tildele variablen 'felt' værdien 'nyt element'
*n gange.
*Så vidt jeg kan se er din tanke at gennemløbe et array indekseret
*af i, men hvis dette er tilfældet vil du altså, hvis vi antager
*at 'Nyt element' skal indsættes som 10. element, opnå at alle
*elementerne 0 - 10 får tildelt værdien 'Nyt element'.
*Hvis vi yderligere ser bort fra denne fejl og antager, at tildelingen
*først skal ske efter gennemløbet af løkken, idet jeg antager
*at din mening er, at løkken skal finde frem til den korrekte
*placering for værdien 'nyt felt', vil du altså overskrive
*det element, der tilfældigvis befandt sig på denne plads.
*For at det skal virke er du nødt til, at flytte alle de efterfølgende
*elementer en plads mod højre, med mindre du repræsenterer det
*som en hægtet liste, i hvilket tilfælde du skal huske
*at hægte den resterende del af listen bag på det indsatte element.
*Men lad os da endelig se bort fra disse ubetydelige fejl, og antage
*at din algoritme virkede. Oprettelse af en liste med N elementer vil
*da efter din model have kompleksitet O(N^2), mens man kan oprette en
*usorteret liste af længde N på kompleksitet O(N). Den efterfølgende
*sortering kan gøres på O(N log(N)), hvilket giver en samlet
*kompleksitet på O(N log(N)).
*>Dvs. at du starter nedefra og koerer opad i din liste
*>indtil du moeder et felt, der er mindre end dit nye ele-
*>ment. Hvis du goer det hver gang vil listen vaere sorteret.
*Som ovenfor beskrevet, vil man ved anvendelse af din algoritme ved
*indsættelse f.eks. af elementerne 4 2 1 3 5 i bedste, hvis vi ser bort
*fra de helt åbenlyse fejl, fald få en liste indeholdende elementerne 5
*5 5 5 5. Den er godt nok sorteret, meeen...
*>Hvis du koder Objekt Orienteret kan dette saettes ind i ob-
*>jektets indsaetningsrutine.
*Jo, objekter er jo taknemmelige....
*>##****************************************************##
*>##* E-MAIL : dat9...@mini01.vejlees.dk *##
*>##* Name : Anders Nikolaj Hansen *##
*>##* Occupation : Datamatician, Computer science *##
* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
*Snup du et par år mere på skolebænken, før du begynder
-- Har du med din (givetvis) hoeje uddannelse nogensinde
hoert om pseudokode? Det jeg har skrevet kan man givetvis
ikke kompilere ensige bruge. Det kræver en smule tankevirk-
somhed at taste det ind saa det kan bruges.
Du skriver maaske normalt programmer af fra computerblade?
Nikolaj Hansen
*dat9...@mini01.vejlees.dk (Nikolaj Hansen) wrote:
*| -- Sortering maa da vaere den sidste udvej. Kan du ikke
*| saette nye elementer ind i den rigtige raekkefoelge?
*| while (Ledig ram){
*| for (int i=0; i < felt; i++)
*| felt = nyt element;
*| }
*| }
*| Dvs. at du starter nedefra og koerer opad i din liste
*| indtil du moeder et felt, der er mindre end dit nye ele-
*| ment. Hvis du goer det hver gang vil listen vaere sorteret.
*Det er altså ikke nogen god løsning, medmindre din liste er konstant fra
*dag til dag, og der kun indsættes nogle få elementer.
*Yderligere er din specielle lineære søgning/sammenligning ekstremt langsom.
*Lad os sige, at du har 1000 elementer i din liste. Og du skal indsætte 1
*element. Du kan i værste tilfælde risikere at lave 1000 sammenligninger,
*inden du ved, hvor du skal "indsætte".
*Brug i stedet binær søgning, der fungerer efter princippet del og hersk.
*Lidt firkantet formuleret, virker den sådan: Du sammenligner først med det
*midterste element i listen (1000/2 = 500). Hvis dit element er større end
*element 500, kan du glemme alt fra element 1 til element 501. Du tager nu
*og finder midten af den mulige "halvdel" af elementer (501 til 1000) - dvs.
*nu sammenlignes element 750, og du kan igen indsnævre mulige elementer til
*f.eks. området 501 til 749. Osv. Rutinen kaldes binary søgning, og klarer
*at finde et match (eller indsætningspunkt) på 10 opslag.
Selvfølgelig er binær søgning hurtigere, men jeg var ikke klar over, at der
var større mængder data at sortere. Hvis der er så store mængder bør man
nok overveje en anden datastruktur end en flad fil. Det kunne evt. være en
træstruktur af en art, i dette tilfælde måske en B+ træs struktur. Fordelen
er her at træet er inorder, så der vil ikke være nogen sortering. Der er
masser af tilgængelig kode til denne datastruktur.
Jeg mener, at denne datastruktur benyttes i OS/2 til at holde styr på
,hvor de forskellige nodes ligger på disken. Sa det er en aftestet struk-
tur.
*| Hvis du koder Objekt Orienteret kan dette saettes ind i ob-
*| jektets indsaetningsrutine.
--
Ole Nielsby
> ... for (i = j/2; j > 1; t[l] = k) ...
Jubii! Endelig én der forstår mig...
Nuvel, min fedtmule-spaghetti-bitfiddler-merge-sort
klarer 56000 komissærfloskler kollateret på 20 sekunder
(486SX50), hvilket er OK. Men jeg skal nok gemme Asgers
indlæg for en anden gangs skyld.
Takker - og bakker ud af denne tråd.
Ole Nielsby
Nikolaj Hansen
*dat9...@mini01.vejlees.dk (Nikolaj Hansen) writes:
*>-- Har du med din (givetvis) hoeje uddannelse nogensinde
*>hoert om pseudokode? Det jeg har skrevet kan man givetvis
*>ikke kompilere ensige bruge. Det kræver en smule tankevirk-
*>somhed at taste det ind saa det kan bruges.
*>Du skriver maaske normalt programmer af fra computerblade?
*Det var ikke syntaksen, jeg kommenterede, men din algoritme,
*der var forkert paa stort set samtlige punkter. Pseudokode
*bruges til at beskrive en algoritme uden at sloere ideen
*med unoedig syntaks og trivielle detaljer, men den er
*intet vaerd, hvis der er fejl i den algoritme man beskriver.
Selvom algoritmen måske var forkert, forstod du alligevel hvor
jeg ville hen. Du må indse, at der er mange andre mennesker end
EDB-folk på denne linje. Faktisk er vi et mindretal. Det betyder, at
VI må tilpasse os og ikke omvendt. Jeg er klar over, at der er mange
mennesker derude der er trætte af vores fagidioti, derfor gør
Linkede lister, sourcekode til træstrukturer og andet godt fra
posen sig ekstremt dårligt på internettet.
*Jeg var maaske lidt vel hoven i mit indlaeg, men dette var
*udelukkende en reaktion paa tonen i dit eget indlaeg:
*Den nedladende tone ("sortering maa da vaere den sidste udvej!") i dit
*svar paa et reelt spoergsmaal kombineret med:
*1) En komplet haabloes algoritme - O(N^2)
Som sagt: en almindelig tabel er lettere at forstå end diverse kom-
plekse datastrukturer, ligesom man skal holde sig væk fra komplekse
søgerutiner. Det mener jeg nu engang. Du var ikke hoven, men direkte
uhøflig.
*2) En hjaelpeloes "beskrivelse" af algoritmen - Du itererer over en
*variabel 'i' som du ikke bruger til noget som helst og du
*tildeler den samme vaerdi til en variabel for hvert gennemloeb af
*loekken. Det er en lige stor fejl, hvad enten du programmerer i C
*eller pseudokode.
Skal vi se et forslag fra din side eller er du bare til brok? Du er
centimeter fra min threadfile.. Det mindste man kan kræve her er vel
en diskussion mellem voksne mennesker.
*Peter
Benny Amorsen
NH> Peter Skov Knudsen (go...@diku.dk) spread the word:
PSK> 2) En hjaelpeloes "beskrivelse" af algoritmen - Du itererer over
PSK> en variabel 'i' som du ikke bruger til noget som helst og du
PSK> tildeler den samme vaerdi til en variabel for hvert gennemloeb af
PSK> loekken. [..]
NH> Skal vi se et forslag fra din side eller er du bare til brok? Du
NH> er centimeter fra min threadfile.. Det mindste man kan kræve her
NH> er vel en diskussion mellem voksne mennesker.
*plonk*
Benny
--
WWW: <A HREF="http://www.daimi.aau.dk/~amorsen/">Benny's homepage</A>
Michael Zedeler
Nikolaj> Selvflgelig er binr sgning hurtigere, [...]
Nikolaj> Det kunne evt. vre en
Nikolaj> trstruktur af en art, i dette tilflde mske en B+ trs
Nikolaj> struktur. [...]
Nikolaj> Jeg mener, at denne datastruktur benyttes i OS/2 til at
Nikolaj> holde styr p ,hvor de forskellige nodes ligger p disken.
Nikolaj> Sa det er en aftestet struktur.
FNIS :-)
Proev engang at overfoere det princip til Microsoft....
Er det ikke rimeligere at henvise til nogle matematiske beviser for at B+-
traeer er gode, frem for forskellige softwareleverandoerers (i nogle
tilfaelde mislykkede) forsoeg paa at implementere dem?
Jeg mener at det er meget sundt at mistaenke programmel for at kunne bryde
sammen naar som helst, ellers bliver man bare fanget med bukserne nede. Det
fremgaar af flere softwareproducenters politik at de _ikke_ tester deres
software ordentligt, foer det bliver udgivet. Jaevnfoer Winbozo et al.
Mvh. Michael.
Tom Arleth
algorithme i Kunth
er (hvis man koder i c(++)) er at bruge et bibliotek
af allerede
implementerede algorithmer.
Et s=E5dan findes bla. p=E5
ftp://.mpi-sb.mpg.de/pub/LEDA/ !
LEDA st=E5r for Library of Efficient Datastructures and
Algorithms. Der er
implementationer af alle de (sorterings) algorithmer
du kan finde i Knut
mm.
Kurt Friis Hansen
| Et alternativ til selv at skrive programmet efter en
| algorithme i Kunth er (hvis man koder i c(++)) er at
| bruge et bibliotek af allerede implementerede algorithmer.
| Et sådan findes bla. på
| ftp://.mpi-sb.mpg.de/pub/LEDA/ !
Der er noget galt med den adresse. Men:
ftp://ftp.mpi-sb.mpg.de/pub/LEDA/
er i orden (det tog lidt fiddleri)
| LEDA står for Library of Efficient Datastructures and
| Algorithms. Der er implementationer af alle de (sorterings)
| algorithmer du kan finde i Knut mm.
DET lyder interessant. Tak for dit tip. Jeg har været inde og kigge, og
problemet er, at tingene ikke uden videre kan benyttes kommercielt. Så det
sætter en grænse for entusiasmen...
Hvis du har flere - lignende kilder - ved hånden, kan du da overtales til
at smide en melding herom. Der kunne jo eksistere "public domain" eller
"free-ware" hang-outs, som jeg ikke har bemærket.
Jens Lohmann-Hansen
Nikolaj> Peter Skov Knudsen (go...@diku.dk) spread the word:
[Slaaskamp klippet ud]
Peter> En komplet haabloes algoritme - O(N^2)
Nikolaj> Som sagt: en
Nikolaj> almindelig tabel er lettere at forstå end diverse kom-
Nikolaj> plekse datastrukturer, ligesom man skal holde sig væk fra
Nikolaj> komplekse søgerutiner. Det mener jeg nu engang. Du var
Nikolaj> ikke hoven, men direkte uhøflig.
For heulede Nikolaj, den oprindelige poster ville skrive forslaget om
i 386 assembler, saa han har sikkert drivis i bagen om datastrukturen
er kompliceret. Hvis han virkelig vil bruge en masse tid paa at
optimere assemblerkode, vil han sikkert ikke have noget imod at saette
sig ind i en kompleks soegerutine.
Desuden bruger din algoritme (jeg kiggede kun paa den kort) en masse
sammenligninger, og da du aabenbart er ligeglad med kompleksiteten af
algoritmen, burde det faktum, at den oprindelig poster sagde, at
sammenligning er dyr, have sagt dig noget.
Personligt mener jeg, at din (forhaabenligt spontane) optimerings-ide
ligger paa niveau med Jesus' ide med at gaa en tur i Getsemane have!
Arg, jeg har allerede brugt for meget tid paa det her.
--
Signed loh...@nork.auc.dk
----------------------------------------------------------------------------
-Chairman of EDA, department of Public Relations