Hjælp til salg (Ikke internet)

Svar: CPU of RAM brug på server ????

Juul — Mon, 04 Nov 2013 08:47:33 GMT

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.

Svar: CPU of RAM brug på server ????

Lundsby — Sun, 03 Nov 2013 20:15:11 GMT

Hej Asger

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

Svar: CPU of RAM brug på server ????

Asger Jon Frounberg — Sun, 03 Nov 2013 20:04:02 GMT

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

Jeg tror ikke jeg har noget argument godt modargument mod din forklaring. Kan se at wikipedia har samme køretider som dig. Hvis du smidder en pm til mig med en leveringsaddresse så sender jeg en flaske din vej i løbet af ugen. Tror også jeg må kigge lidt ekstra på de hashfunktioner... Tak for at udvide min horisont :)

Svar: CPU of RAM brug på server ????

Lundsby — Sun, 03 Nov 2013 17:56:07 GMT

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 :-)

Svar: CPU of RAM brug på server ????

Asger Jon Frounberg — Sun, 03 Nov 2013 11:24:11 GMT

Lundsby:
Hej Asger
Men jeg tror heller ikke at der er nogle derude som ville blive overrasket over at det ikke kræver en sortering at indsætte i en hashtabel. Hvor har du det fra ?

Det ville give mening. I øvrigt kan jeg ikke se hvordan den skulle have en køretid på n hvis ikke den er sorteret. Hvis de ligger tilfældigt kan jeg ikke se hvordan du får en køretid der er bedre end n^2 ved mindre du bruger n*log(n) på at sortere dem. Hvis nogen kan forklare mig det så giver jeg sku en god øl eller en flaske vin. Pt strider det mod alt jeg (tror jeg) har lært i DTU's ellers gode kursus algoritmer 1.

Svar: CPU of RAM brug på server ????

Lundsby — Sat, 02 Nov 2013 13:57:07 GMT

Hej Asger
Jeg syntes jeg har snakket nok med DTU da jeg tog min kandidat grad derude :-)
Men jeg tror heller ikke at der er nogle derude som ville blive overrasket over at det ikke kræver en sortering at indsætte i en hashtabel. Hvor har du det fra ?

(Iøvrigt er Pythons Set implementeret via en Hashtabel)

Svar: CPU of RAM brug på server ????

Lucas - PerfGrid — Sat, 02 Nov 2013 12:42:20 GMT

samuelsen:

1000 tak til jer alle sammen for fantastisk feedback.

Lucas jeg syntes det er fantastisk at du har taget dig tiden til rent faktisk at teste.

Hvis pyhton kører 30 millioner linjer på 34.3 sekunder, med så lidt ram, kan man så lave en løsning hvor koden læser fra flere forskellige punkter på samme tid ?

Ekesmpeltvis at filen læses fra hver 5million linje. I dette tilfælde fra 6 forskellige steder på samme tid.

Vil det kunne presse tiden ned på omkring 1-2 sek for den samme fil ???

Du kan bruge noget map reduce, men er lidt mere kompliceret end koden ovenfor :)

Svar: CPU of RAM brug på server ????

samuelsen — Sat, 02 Nov 2013 12:37:41 GMT

1000 tak til jer alle sammen for fantastisk feedback.

Lucas jeg syntes det er fantastisk at du har taget dig tiden til rent faktisk at teste.

Hvis pyhton kører 30 millioner linjer på 34.3 sekunder, med så lidt ram, kan man så lave en løsning hvor koden læser fra flere forskellige punkter på samme tid ?

Ekesmpeltvis at filen læses fra hver 5million linje. I dette tilfælde fra 6 forskellige steder på samme tid.

Vil det kunne presse tiden ned på omkring 1-2 sek for den samme fil ???

Svar: CPU of RAM brug på server ????

Lucas - PerfGrid — Sat, 02 Nov 2013 11:35:16 GMT

Nu brugte jeg tiden på at lave en fil, med duplicate lines, i alt 30 millioner linjer, og en fil størrelse på 3 gigabyte.

ved brug af en helt normalt 'sort tmpfile | uniq' i linux resultere i et ram forbrug af 90.4 megabyte, tiden var 2 minutter og 54 sekunder.

Ved brug af Python, tager det 2.5 megabyte ram, med følgende kode:

lines_seen = set()
outfile = open("unikt", "w")
for line in open("megetstor", "r"):
if line not in lines_seen:
outfile.write(line)
lines_seen.add(line)
outfile.close()

Dette tager 34.3 sekunder for samme fil.

Ved brug af følgende kode:

from collections import OrderedDict

with open('megetstor') as fin:
lines = (line.rstrip() for line in fin)
unique_lines = OrderedDict.fromkeys( (line for line in lines if line) )

print unique_lines.keys()

Denne tager 3.8 megabyte ram, og tager 1 min 40.313 sekunder.

Så kan skam gøres relativt hurtigt, og ved lavt forbrug ;)

Svar: CPU of RAM brug på server ????

Asger Jon Frounberg — Sat, 02 Nov 2013 10:37:42 GMT

Lundsby:
Der er meget rigtigt i det Asger siger, men det kan laves lidt smartere. Ved at bruge en Hash funktion (http://da.wikipedia.org/wiki/Hashfunktion) og kun gemme hashen og lokationen af linien, så vil det gå markant hurtigere og fylde mindre.

God pointe. Du skal dog være opmærksom på at det kan give falske positive selvom det i praksis er usandsynligt. Det er også meget let at fjerne efterfølgende da det bare kræver at du køre sammeligningerne igen med den rigtige data.

Lundsby:
Hvis vi f.eks. hash'er ned til ti tegn, så vil det samlede ram forbrug være en femogtyvende-del, altså ca. 100 mb. I forhold til køretiden, kan vi ved at putte gemme linierne i en hashtabel opnå en kørertid på N. Altså omkring en 10.000.000 gennemløb.

Nej ikke helt korekt. Du glemmer at når du lægger den ind i hashtabellen skal de sorteres. Det sker automatisk men påvirker stadig din køretid. Sorteringer kan mig bekendt ikke ske hurtigere end n*log(n). Hvis du kan lave en sortering hurtigere end det så er jeg sikker på at der ligger 1 billet til stockholm og venter sammen med en lille medalje ;) Derudover tror jeg meget gerne DTU vil tale med dig for så har du lige modbevist en masse jeg har lært gennem min studietid.

Svar: CPU of RAM brug på server ????

Lundsby — Sat, 02 Nov 2013 09:04:57 GMT

Der er meget rigtigt i det Asger siger, men det kan laves lidt smartere. Ved at bruge en Hash funktion (http://da.wikipedia.org/wiki/Hashfunktion) og kun gemme hashen og lokationen af linien, så vil det gå markant hurtigere og fylde mindre.

Hvis vi f.eks. hash'er ned til ti tegn, så vil det samlede ram forbrug være en femogtyvende-del, altså ca. 100 mb. I forhold til køretiden, kan vi ved at putte gemme linierne i en hashtabel opnå en kørertid på N. Altså omkring en 10.000.000 gennemløb.

Rent CPU og Ram mæssigt vil jeg ikke tro at det kræver noget særligt, de fleste maskiner der er indkøbt indenfor de sidste par år, ville jeg tro kunne klare det rimeligt hurtigt, den bedste måde at finde ud af det på er at lave et lille program der laver noget test data og udfører opgaven. Jeg ville tro at det kunne gøres på en halv til en hel time.

Svar: CPU of RAM brug på server ????

Asger Jon Frounberg — Sat, 02 Nov 2013 07:31:06 GMT

Det er umuligt at give et konkret svar på. Det kommer 100% an på hvordan den bliver implementeret.

Jeg kan prøve at give dig en ide om hvor mange recurser der skal bruges som minimum med en god implementation. Bemærk jeg bruger runde tal ved godt det ikke er 100% præsist.

Du har 10 millioner linjer tekst. Jeg vil vælge at antage at der er gennemsnitlig 250 tegn i en linje. Det giver i alt cirka 2.500.000.000 eller 2,5 mia tegn. Nu er vi så heldige at langt de fleste normale engelske tegn (a-z,0-9 osv) bruger 1 byte i ASCII som er standarten. Det giver os igen 2.5 mia bytes eller omkring 2,5 GB. Det vil sige at hvis vi bare smidder alt meneingsløst ind på ramne bruger vi rundt regnet 2,5 GB. Det behøver vi nu ikke men desto størrer del af dataen ligger op harddisken desto længere tid skal vi bruge på at flytte data fra haddisk til ram hvilket er et problem da man læser langsommere fra haddisken end fra ram. Hvis vi skal optimere i forhold til cpu skal vi altså have 2,5 GB ram til rådighed som minimum men du kan i pricippet bruge meget mindre så køre programmet bare langsommere. Det skal dog siges at hvis vi laver en dårlig implementation vil det dog kræve flere ram.

Hvor lang tid tager koden så at køre? Det kommer an på en masse ting så som CPU, styresystem mm. Det er dog realistisk at finde ud af hvor mange gange vi skal sammenligne 2 rækker og hvis vi ved hvor lang tid det tager så har vi et godt estimat. Den lette løsning ville være at sammenligne alle de forskellige rækker med hinanden og så fjerne dem der er ens. Worst case er der ingen der er ens og vi ender derfor med at lave 10.000.000^2 sammenligninger eller 100.000.000.000.000 eller 100.000 mia gange. Vi kan dog gøre det hurtigere. Hvis vi sortere dataen først så kan vi f.eks. nøjes med 10 mil sammenligninger. Sortering tager dog tid. Uden at gå for meget i detaljer vil jeg afsløre at det gøres i bedste fald med det vi i IT verdnen kalder worstcase køretid n*log(n) hvor n er antallet af data eller i dette tilfælde linjer. Det betyder at vi skal tage 10 mil * 2 tals logeritmen til 10 mil. 2 tals logeritmen til 10 mil er cirka 22 så omkring 220 mil + de 10 = 230. Her er mit gæt så dog at du skal lægger omkring 40 mb til ramforbruget hvis du gerne vil have linjerne ud i den samme rækkefølge foruden potetielt 220 mil ekstra oprationer. Hvor lang tid tager det så at sammenligne og flytte 2 linjer. Tja ikke særlig lang tid men det kræver at man forsøger sig frem for der er massere af ubekendte. Hvis vi nu antager at det tager cirka 0,00001 sek. (tror ikke det er helt urealistisk med 0,01 millisekund) så vil vi altså bruge op til 230 mil * 0,00001 s eller 2300 sekunder for at få alle linjerne ud i sorteret orden og 4500 sekunder for den oprindelige orden. Dette giver os et rundt estimat på hhv 38,333 min og 75 min. Mere hvis du mangler ram. Hvis du programmere godt og har flere kerner osv. kan du selvfølgelig få det her ekstra ned.

Hvad er konklusionen så? Jeg tror jeg ville kigge på serveren og se hvor mange ram der er. Hvis du har mere end 8 GB ram så ville jeg nok gå klart efter processerkraft ved mindre end du brunger serveren til andre hårdre ting. Hvis du har mindre end 4 GB ville jeg helt sikkert gå efter ram. Mellem de 2 ved jeg ikke helt hvad jeg ville vælge. Alternativt kan du jo teste din server. Jeg ville nok se hvor lang tid det tager i dag og hvor fyldte ramne bliver når jeg sætter den igang med nogle lidt mindre testopgaver. Her ville jeg nok starte med at give den f.eks. 10.000 linje og så 100.000 linjer, 1.000.000 mil linjer og så 10.000.000 linjer for at se hvad der sker. Du kan overvåge processor og ram forbrug på serveren i mellemtiden. Hvis rammene bliver fyldt op ville jeg skaffe flere af dem først.

Svar: CPU of RAM brug på server ????

Lucas - PerfGrid — Sat, 02 Nov 2013 01:28:16 GMT

Den vil selvfølgelig bruge noget CPU for at finde alle de ting den nu skal fjerne, men hvis koden er skrevet dårligt, så vil du bruge en del buffer for dataen, så jeg vil skyde på at der vil blive brugt en del ram.

CPU of RAM brug på server ????

samuelsen — Fri, 01 Nov 2013 23:04:52 GMT

Jeg faldt lige over denne side

http://textmechanic.com/Remove-Duplicate-Lines.html

her kan du indsætte en text og denne online service fjerner så linjer der er ens. Super smart.

Her er mit spørgsmål. Hvis jeg nu indsætter en tekst med 10 millioner linjer, og beder serveren om at fjerne linjer der er ens. Vil dette arbejde så tage mest på ram eller cpu ?

Jeg tænker på denne service konkret, og ikke generalt. Jeg tænker at det må være cpu arbejde, men jeg er langt langt fra sikker. Jeg ved at man selvfælgelig kan teste dette, men har brug for noget information om det FØR jeg vælger at bruge penge på enten cpu eller ram.

på forhånd tak for hjælpen.