Du har ein maskin med 4GB ram, og du har fått i oppgåve å sortere 40TB data.

[siDDis]

https://queue.acm.or....cfm?id=1814327

[GeirGrusom]

Du vil sitte i dagesvis å implementere dette, og i mellomtiden så er løsningen blitt skrevet, og sortering fullført av konkurrentene dine.

[LonelyMan]

Lista er lengre enn effort som kreves. Jeg ville behøv ca 1 time på å skrive det, og jeg ville antakeligvis brukt 4-5 timer ekstra for å se over alt og gjøre det perfekt. Om konkurrentene mine skriver det ferdig på 30 minutter så tror jeg likevel at det vil lønne seg å bruke 30 minutter ekstra mtp. hvor mange ganger man kommer til å bruke programmet i fremtiden. Dette er likevel tåpelig å snakke om.

[siDDis]

Så du meinar at du kan implementere noko betre enn dette http://pastebin.com/LwbaT6Xb på eit par timar?

[LonelyMan]

Det du presenterer her er en komplett løsning, det som topic beskriver er en typisk skoleoppgave problemstilling. En komplett løsning i industrien har veldig lite med det å gjøre.

 

Det er stor forskjell å spørre forumet om å bidra med en komplett implementering av en industri-løsning på et to minutters innlegg og å svare på en skoleoppgave.

 

Jeg så forresten over koden du poster til, det er ikke bare en enkelt løsning på et problem, det er flere løsninger på mange problemer, hvilket heller er irrelevant til spørsmålet i topic.

 

Videre så ser det ut som om de vet hva slags algoritmer de ønsker å bruke, men måten de har kodet det på er det verste jeg har sett, helt og komplett elendig kode. Det er total mangel på teknisk forståelse i koden.

 

Enkelt sagt så er den koden for en datamaskin hva en orkan er for mennesker. Helt jævlig.

Endret 5. desember 2012 av LonelyMan

[siDDis]

Unnskyldninger og unnskyldninger....

Denne c koden vil generere ein fil på fleire gigabytes med random tall

#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
uint32_t m_z = 1337;
uint32_t m_w = 750001;

uint32_t
get_random()
{
m_z = 36969 * (m_z & 65535) + (m_z >> 16);
m_w = 18000 * (m_w & 65535) + (m_w >> 16);
return (m_z << 16) + m_w;
}
int
main()
{
	FILE *file;
	file = fopen("bigdata.txt","w");
	uint32_t i;
	for(i=0; i < 9999999999; i++){
			fprintf(file, "%u\n", get_random());
	}
	fclose(file);
	return 0;
}

Og sidan det er så enkelt for deg så gir eg deg ein oppgåve å skrive kode som oppretter ein fil som har sortert alle disse verdiane og som slår GNU sort.

[LonelyMan]

Er det en ny oppgave, topic begynte med en problemstilling og nå er det GNU vs meg?

 

Det er ingen vits i å skryte av en sort rutine du ikke har studert engang. Hvorfor skal jeg bruke masse tid på å slå en rutine du ikke har studert engang. Om den er så bra, hvilke sterke sider er det du ønsker å påvise som ikke kan slås?

 

Jeg forklarte min fremgangsmåte mtp topic i tråden, ikke sleng et ukesprosjekt på meg av den grunn.

 

Og helt utenfor konteksten, algoritmen kan være god den, jeg har ikke satt meg inn i den, men koden er elendig implementert, jeg vil være overrasket om ikke måten koden er laget vil invalidisere fordelene med algoritmen helt.

 

On second thought så trenger jeg ikke implementere mulighet for å sortere alle mulige data, jeg kunne jo bare laget en rutine for å sortere tilfeldige tall slik som du postet over, og sammenlikne det med gnu sort. Jeg får se om jeg orker, er litt opptatt nå. Men kanskje en gang i nærmeste fremtid. I mellom tiden så kan du jo bidra med noen tall resultater fra gnu sort slik at jeg vet hvilken tid jeg skal slå. Når jeg har en tid å gå ut ifra så går det fortere for meg å finne ut hvor mye mer jeg må optimalisere min kode så slipper jeg å optimalisere for mye eller for lite, men akkurat slik at den slår gnu sort.

 

Jeg lastet ned GNU32 for windows og har nå sort programmet. Fortell meg hvilke parametere jeg skal bruke for å sortere tall i en fil. Sånn at jeg kan teste hvor raskt det tar.

Endret 5. desember 2012 av LonelyMan

[Lycantrophe]

Du trenger ingen.

 

sort [file]

 

Du kan hjelpe den litt på vei med:

 

sort --general-numeric-sort [file]

 

Bruk -S for å sette buffer-size og -o for å gi den en outputfil (så du slipper flaskehalsen i stdout)

Endret 5. desember 2012 av Lycantrophe

[GeirGrusom]

Jeg forklarte min fremgangsmåte mtp topic i tråden, ikke sleng et ukesprosjekt på meg av den grunn.

 

Jeg ville behøv ca 1 time på å skrive det, og jeg ville antakeligvis brukt 4-5 timer ekstra for å se over alt og gjøre det perfekt.

 

Så... ikke TDD altså?

[siDDis]

--numeric-sort er betre enn --general-numeric-sort av den grunn at --general-numeric-sort konverterer alle talla til float.

Komplett eksempel:

sort -S 8000M --parallel=8 -n bigdata.txt -o sorteddata.txt

Denne vil bruke 8GB ram og 8 tråder for å sorteringsjobben. -n er det same som --numeric-sort

[tomsi42]

--numeric-sort er betre enn --general-numeric-sort av den grunn at --general-numeric-sort konverterer alle talla til float.

Komplett eksempel:

sort -S 8000M --parallel=8 -n bigdata.txt -o sorteddata.txt

Denne vil bruke 8GB ram og 8 tråder for å sorteringsjobben. -n er det same som --numeric-sort

Så følgende kode løser TS sitt opprinnelige problem hvis dataene er tall;)

 

sort -S 4000M --parallel=8 -n bigdata.txt -o sorteddata.txt

 

Så det egentlig svaret er "Bruk Gnu sort"

[LonelyMan]

Jeg laga ferdig det sorteringsprogrammet i går, men det som er litt latterlig er at jeg ikke orket sjekke hva gnu sort faktisk gjorde, den sorterer strenger og jeg sorterte dwords direkte. GNU sorterte 600 MB med data på 2 minutter og min sorterte samme mengde data på 11 sekunder. Jeg gav GNU sort 900 MB buffer som er mer enn hele filen tilsammen, jeg satte 500 MB buffer på min egen. Jeg får se om jeg orker å omgjøre den til å konvertere tekst istedet, det vil ta litt lengre tid å konvertere tekst, men ikke noe som jeg tror GNU vil vinne over likevel. Den er altfor langt unna allerede. Jeg må si jeg er sjokkert over hvor ineffektiv gnu sort er. Jeg har ikke gjort noen effort i det hele tatt, og den er milevis unna. Egentlig er jeg ikke så veldig sjokkert, når jeg så gjennom gnu koden i går så skjønte jeg med en gang at algoritmen ikke ville hjelpe så fryktelig mye pga den dårlige kodingen.

 

 

GNU brukte 2 minutter og 11 sekunder, det er jo helt latterlig., og jeg vet at jeg behøver ikke veldig mange sekundene ekstra for å konvertere strenger istedet for dwords.

 

Her er begin.bat fila jeg brukte

 

@echo off
echo %TIME%
sort-7.6.exe -S 900000 -n -o c:\sort\GNUSorted.txt c:\sort\numbers.txt
echo %TIME%

 

numbers.txt er 547 MB og all konvertert data er verifisert i hex editor. Begge brukte en tråd. Siden jeg brukte dwords så sorterte jeg 3 ganger flere tall enn gnu sort, da de fleste tall var 10 digits lang, + 13,10 for ny linje, så er det 12 bytes per tall for gnu, og 4 bytes per tall for mitt program. Det er ganske mye impact å sortere en tabell som er 3 ganger større, bare forsøk det selv.

 

GNU sort: 2 minutter og 11 sekunder

Mitt uoptimaliserte program: 11 sekunder

 

GNU sorterte omtrent: 45,583,333 tall (45 millioner tall)

Mitt sorterte omtrent: 136,750,000 (136 millioner tall)

 

Mitt elendige program som ikke ligger noen effort i er 1100% raskere. Det vi trygt kan si ut ifra dette er at min sorteringskode er mye raskere enn GNU sin. Det som gjenstår å se, er om jeg klarer å konvertere og tolke tekst-tall raskere enn GNU klarer, og om jeg klarer å lese og skrive raskere til disk enn GNU kan. Det som er verifisert her er at min sorteringsalgoritme er raskest (på tross av at jeg ikke har gjort noen effort her)

 

Jeg har ingen anelse hvor lenge GNU folkene har jobbet på den koden, men jeg sparket den i rompa over ca 10 minutter effort. Det som er mest latterlig er at jeg leste hele filen fra disk til minnet før jeg begynte å sortere den, dvs jeg mistet masse verdifull tid som jeg kunne utnyttet ved å lese den sekvensiell i bulker. hehe. Om jeg gjør det går sekundene veldig fort nedover. Men jeg ser ingen grunn slik som tallene står nå.

Endret 6. desember 2012 av LonelyMan

[siDDis]

Vell, du benchmarker nå bare in memory sorting. Med Python(numpy) sorterer eg ein liste med integere med omtrent tilsvarande hastigheit som deg. Sortering handler også om IO, ikkje bare cpu.

[LonelyMan]

Mine tall benchmarker ikke bare minnet.

 

1. Lese fra fil = X

2. Sortere i minnet = Y

3. Skrive til disk = Z

 

X + Y + Z = 11 sekunder.

[LonelyMan]

Nå har jeg laget en rutine for å konvertere strings til integer og optimalisert den noenlunde.

 

Rutinen klarer å konvertere 47,844,260 (47,8 millioner) strenger på 1366 millisekund (1,3 sekunder) hvor hver tall-streng er 9 siffer langt, dvs en milliard. Men nå vil over halvparten av tallene i en fil være halvparten av dette. Denne hastigheten er målt med høypresisjon, og den leser først streng-tallet, konverterer det og så skriver det tilbake til en dword i programmet (3 steps).

 

Den roterer f.eks samme mengde tall-strenger på 1 siffer på bare 172 millisekunder. Så vi må ta gjennomsnittet av 1,3 sekunder og 0,17 sekunder for å finne et reelt resultat for å konvertere hele fila som blir 683 millisekunder.

 

For å konvertere alle tallene i den fila jeg brukte i testresultatet (547 MB) så vil det ta noe rundt 683 millisekunder å konvertere streng til integer. Å konvertere fra integer til streng gjør jeg på rundt 70% av tiden å konvertere fra streng til integer så totalt sett kan vi legge på 1161 millisekunder på den totale tiden for å sortere fila.

 

Jeg hadde 11 sekunder opprinnelig, + 1161 millisekunder blir 12,161 sekunder totalt.

 

I tillegg så sorterte jeg 136 millioner tall med quicksort varianten min, jeg skulle egentlig bare sortert 45 millioner, hvilket er 3 ganger for mye, så vi må trekke fra mye tid fra sorteringen min også, men jeg orker ikke det nå.

 

Jeg orker ikke implementere det i programmet, så jeg legger heller bare rutinen her i forumet om noen vil teste den.

 

proc a2dw uses ebx edi esi,szstr
	mov edi,[szstr]
	xor cl,cl
	mov eax,edi
	sub eax,4
	   .z1: add eax,4
	cmp [eax],cl
	je .z4
	cmp [eax+1],cl
	je .z3
	cmp [eax+2],cl
	je .z2
	cmp [eax+3],cl
	jne .z1
	sub eax,edi
	add eax,3
	jmp .z5
	   .z2: sub eax,edi
	add eax,2
	jmp .z5
	   .z3: sub eax,edi
	add eax,1
	jmp .z5
	   .z4: sub eax,edi
	   .z5: xor ecx,ecx
	test eax,eax
	jz .z9
	   .z6: xor edx,edx
	mov dl,[edi]
	sub dl,$30
	mov esi,eax
	dec esi
	push eax
	mov eax,edx
	push ebx
	mov ebx,$a
	test esi,esi
	jz .z8
	   .z7: mul ebx
	dec esi
	jnz .z7
	   .z8: pop ebx
	add ecx,eax
	pop eax
	inc edi
	dec eax
	jnz .z6
	   .z9: mov eax,ecx
	ret
endp

 

Da sier jeg meg ferdig her. (La ved rutinen i en egen dll hvis noen vil teste, får se om jeg legger ved quicksort også i en dll senere) a2dw tar en parameter, peker til en streng som skal konverteres til integer, og returnerer integeren.

 

(Lagt ved quicksort varianten min i en dll. Den tar 2 parametere, første parameter er peker til tabellen som inneholder alle integer som skal sorteres, andre parameter er hvor mange tall som er i tabellen, ikke hvor mange bytes, men hvor mange 32 bit integer tall)

 

EDIT: Fikset a2dw dll filen, bildet var ugyldig da jeg ikke hadde noen api referanser i dll'en så nektet systemet å laste den, fikset det nå. (Ny fil vedlagt)

qsort.zip

a2dw.zip

Endret 8. desember 2012 av LonelyMan

[siDDis]

Flott du tar utfordringa på alvor, men det gjenstår litt enda.

Din implementasjon er kanskje noko raskare enn numpy sin, men tråden handler om store mengder data(100-1000 gonger meir enn det du har av minne). Du har sikkert brukt fleire timar allereie og på noko som eg brukte 1 minutt å løyse nesten like kjapt som deg med numpy.

 

Og kvar tallsiffer varierer mellom 1 til 9 tegn. Ut i frå beskrivelsen din så tar du utgangspunkt at alle tall har 9 siffer. Men er det fordi du sparer enormt på ytelsen ved å gjøre det?

 

Og kva slags disk leser du frå? Eg brukar totalt 6 sekunder på å skrive ein fil frå /dev/zero og lese den til /dev/null. Og flaskehalsen der er utan tvil SSD disken min.

[LonelyMan]

Man sparer ikke på ytelsen ved å ta utgangspunkt i 9 siffer. 9 siffer er å ta utgangspunkt i det verste som kan skje. 1 siffer er hvor man sparer på ytelsen.

 

Jeg bruker 2 stk WD velociraptor disker i raid 0, mekaniske disker, så jeg sliter på ytelsen selv her. Alt i maskina mi er bra, med unntak av diskene.

 

Det spiller ingen rolle om du tester med en halv GB eller med 20 GB. Om ikke GNU sort klarer å yte bedre med alle forhold på sitt beste, så er der ikke noe mer å teste til GNU sin fordel. Når GNU har all minne tilgjengelig (mer enn størrelsen på fila) så vil ikke GNU yte mer om du setter den på 20 GB istedet for en halv.

 

Sorteringstiden er allerede verifisert, konverteringstiden er allerede verifisert, det eneste vi kan teste ut ved å øke fra en halv GB til 20 GB er om GNU er raskere på disk-ytelse, hvilket jeg mener personlig vil være bortkastet tid å teste, jeg tror virkelig ikke den har noe større ytelse der.

 

Men der er en ting jeg ønsker verifisert, nå kjører jeg windows varianten av GNU sort. Kan noen sjekke linux varianten og se om den yter bedre?

Endret 7. desember 2012 av LonelyMan

[siDDis]

Den er tilsvarande lik på yelsen på Linux

 

Edit: Det skal stå at eg brukar totalt 6 sekunder på å skrive ein fil på 500MB

[LonelyMan]

Apropos måle tiden på kode så har jeg skrevet et lite bibliotek for å måle kode, den har 6 funksjoner.

 

start_timing

stop_micro

stop_milli

stop_second

stop_ticks

set_output

 

kjør 'start_timing' før den delen av koden du skal måle, og bruk en av de neste 4 metodene for å stoppe målingen. Den returnerer målingen og den printer også ut en messagebox med resultatet, hvis du ikke vil ha messagebox kan du kjører siste metode "set_output" og FALSE som parameter. Om noen vil ha den.

tid.zip

Endret 12. desember 2012 av LonelyMan