CPU of RAM brug på server ????

Hej Asger

Når der er en flaske vin på høj kant, gør jeg gerne en ekstra indsats for at forklarer det. Tror mig det passer så fint med hvad du har lært i algoritmer.

Lad os tage udgangspunkt i Lucas' Python kode, og se på den for at afgøre hvad køretiden er.

1. lines_seen = set()
2. outfile = open("unikt", "w")
3. for line in open("megetstor", "r"):
4.    if line not in lines_seen:
5.        outfile.write(line)
6.        lines_seen.add(line)
7. outfile.close()

I 1. linie initialiserer vi hashtabel, hvis vi vil opnå at hashtabel ikke hele tiden skal lave dyr array-double, så ville det være smart at give den en start størrelse der ligger tæt på antallet af linier. Selve køretiden af linien er konstant O(1)

I 2. linie åbner vi filen heller ikke noget der, O(1).

Så i 3. linie starter loopet, da alle linjer gennemgås, er køretiden for loopet O(n). Det betyder at hvis ingen af linierne indenfor loopet har en køretid på over O(1) så er den samlede køretid O(N).

I linie 4 laves et opslag i hashtabellen, den operation tager O(1) (Check evt. din algoritme bog, det er selvfølgeligt med forudsættelse af en perfekt hashfunktion etc.)

I linie 5 udskrives linien, igen O(1)

I linie 6 tilføjes linien til hashtabellen igen en operation der tager O(1). Herefter afsluttes loopet da, ingen af linierne indenfor loopet har haft en køretid på over O(1), så er den samlede køretid O(N).

Håber du kan følge eksemplet. Der er ikke brugt noget der ikke var indeholdt i det kursus der hed Algoritmer og datastrukturer som jeg tog vel en små 15 år siden. Jeg vil tro det svarer til Algoritmer 1 idag.

Ang. vin/øl så er jeg meget stor fan af Mollydooker's The Boxer :-)

Hej Asger

Det er god stil, jeg sender en pm med det samme.

Hej Lundsby

Læste lige om THE BOXER, har du smagt den og hvordan er smagen med chokolade? Kan ikke lige selv sætte det på mine smagsløg, så en smagsoplevelse på skrift vil jeg da meget gerne have. 

Kunne faktisk godt finde på at prøve en sådan.