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

[siDDis]

Dette er eit åpent spørsmål som har mange svar(og mange gode).

 

Korleis ville du ha tenkt å utført dette?

[Alexen]

En form for mergesort kanskje?

[Djn]

Hm. Hva med dette:

 

Splitt den opp i de største filene jeg praktisk kan sortere (på ren gjetning et sted rundt 2GB), sorter hver av dem separat, og lagre de som separate filer igjen. Åpne alle de filene, og slå de sammen linje for linje; skriv resultatet til disk løpende.

edit: Aha, mergesort er en bedre variant av denne idéen.

 

Alternativt kan man gjøre et slags hierarkisk splitt/hersk-prosjekt. Tipp et midtpunkt for nøkkelen man sorterer på. Les gjennom alt, og skriv linjene til en over-fil og en under-fil. Gjenta for hver halvpart, og fortsett nedover inntil en av underdelene er liten nok til å sortere totalt; append denne til en resultatfil. Hvis man gjør det depth-first (og konsekvent enten minst-først eller størst-først) skal resultatfilen bli sortert. (Forsåvidt en quicksort-variant).

Endret 7. november 2012 av Djn

[siDDis]

Hmm, eg er overraska at ingen foreslår at dei ville ha brukt ein database til akkurat dette. Sjølv ville eg har gjort det med å flytte dataten til eit hadoop cluster og laga ein Mapreduce task.

[process]

Vil det ikke være relevant med mer informasjon rundt forutsetningene?

 

Hva slags data er det?

Hvordan er det lagret? (antall filer, min/max/avg størrelse på filer)

 

Og bryter du ikke med forutsetningene ved å bruke et cluster, da har du plutselig mer enn 4Gb RAM?

I såfall ville jeg lastet det opp på en IBM maskin og kjørt det som en batch jobb

 

Jeg vet TS er en kunnskapsrik kar, men denne tråden skjønner jeg ikke helt

[tomsi42]

Jeg vet TS er en kunnskapsrik kar, men denne tråden skjønner jeg ikke helt

Jeg skjønte heller ikke tråden; savnet alt for mye info.

 

F.eks. Bruker 40TB med data det meste av diskplassen? Eller har vi uendelig med diskplass?

 

Og er dette noe andelerledes enn problemstillingen fra 50-60 tallet da man hadde 4kb med minne og 40MB med data? Dvs. den gangen hadde de gjerne 4kb med minne og 200-300MB med data ...

[SkoMedHull]

Trenger vi all informasjonen som ligger i hvert element, eller kan vi analysere hvert element og tildele det en størrelse av et slag?

 

Da kunne man sortert bare disse størrelsene og deretter bare flytte dataene på riktig plass utfra resultatet av sorteringen.

 

Gitt at det er veldig små elementer så blir naturlig nok dette mindre aktuelt.

[siDDis]

Trenger du å vite kva slags data det er når du veit at den er sorterbar og på 40TB? Det er ingen som vil sortere 40 blobber på 1TB med videodata

Diskplass var ikkje ein begrensning som var nevnt ergo utan betydning.

Ja eg veit at Mapreduce ikkje er så veldig mykje betre når det var ein begrensning på ein maskin 4GB.

Men eg er litt forbausa over at fleire ikkje ville bare ha putta dataen i ein database og sortert det der, dei fleste databaser har jo merge-sort innebygd.

 

Spørsmålet er eit typisk opptaksspørsmål i Silicon Valley. Det er ikkje feil å implementere sin eigen sorteringsalgoritme, men tid til det er det ikkje alle som har.

[SkoMedHull]

Du må nok ta en liten titt på hvilken del av forumet du har postet dette. Det å sende data til en database og sette i gang en innebygget sorteringsprosedyre er ikke programmering i seg selv, og de fleste går da mer i dybden enn dette. Hvis jeg hadde fått et spørsmål på en eksamen som lød noe sånt som "Hvordan ville du funnet et ord i et tekstdokument?" og hadde svart "Jeg hadde åpnet dokumentet i MS Word og trykket ctrl +f" så hadde det vært litt for enkelt. Konteksten rundt spørsmålet er misvisende hvis du er ute etter noe så enkelt som du foreslår.

 

Hvis spørsmålet ikke hadde vært i denne delen av forumet, men heller en mer generell del av forumet og lagt frem som et praktisk problem som måtte løses så hadde du nok fått helt andre svar.

Endret 9. november 2012 av SkoMedHull

[siDDis]

Eg er ueinige med deg, då eg ser på dette som eit generelt spørsmål til utviklerar. Det handlar trossalt om databehandling.

[Djn]

Jeg tenkte forsåvidt på et DB-fag jeg hadde en gang (som blant mye annet snakket om forskjellige måter å joine og sortere data som tar mye mer plass enn man har minne til), men jeg antok også at du mente algoritmisk-hvordan og ikke praktisk-hvordan jeg ville gjort det.

 

Metodisk ville jeg bare brukt gnu sort, som allerede gjør noe smart med å sortere deler og merge dem hvis den tror det er nødvendig.

Endret 9. november 2012 av Djn

[process]

Trenger du å vite kva slags data det er når du veit at den er sorterbar og på 40TB? Det er ingen som vil sortere 40 blobber på 1TB med videodata

 

Struktur på dataene og hvordan de skal sorteres er svært vesentlig for valg av sorteringsalgoritme. Her er også størrelsen på det som utgjør ett element vesentlig, da det vil si noe om antall elementer.

 

Overnevnte faktorer vil avgjøre effektiviteten til ulike metoder for å sortere og jeg mener dette er en forutsetning for å kunne gi et godt svar. Det er dog muligens ikke detaljnivået du er ute etter.

 

Jeg må gjette meg til at du sikter til tekstfiler med entries pr. n linje, som skal sorteres alfanumerisk i en lineær rekkefølge? Dette er i så fall en vesentlig forutsetning.

 

Spørsmålet er eit typisk opptaksspørsmål i Silicon Valley. Det er ikkje feil å implementere sin eigen sorteringsalgoritme, men tid til det er det ikkje alle som har.

 

Men du skal ha kjennskap til de allerede implementerte algortimene og hvilken som er best for de gitte dataene og sorteringsmetodene.

[siDDis]

Nei eg sikter til data som er sorterbar, kva form det har er uvesentleg. Korleis du skal få dataen "strukturert" for å kunne sortere det er også uvesentleg.

 

Det handler heller ikkje om kjennskap til algoritmer eller kva som er den beste sorteringsmetoden, for det er ikkje det som det blir spurt om. (Sortering er faktisk eit eige fagfelt).

Det handler om kva du ville ha gjort! Derfor synes eg GNU sort er eit fantastisk genialt svar! For då får du tid til å ta kaffepause saman med kollegane dine

 

Implementere merge sort er heller ikkje eit dårleg svar, men det viser kanskje at du altfor lett overkompliserer noko som ikkje trenger å være så vanskeleg.

 

Det er iallefall min meining.

[LonelyMan]

Dette er eit åpent spørsmål som har mange svar(og mange gode).

 

Korleis ville du ha tenkt å utført dette?

 

Jeg ville tenkt på å utføre det på best mulig måte som lar seg gjøre. All type data har struktur, hver struktur har sine egne fordeler med forskjellige algoritmer, for å fortelle videre hvordan det best lar seg gjøre må jeg vite strukturen og formålet. Jeg kan se to formål, 1: raskest mulig sortering eller 2: bare bli ferdig med sorteringen i det hele tatt.

 

I begge tilfeller må jeg vite strukturen til dataene for å vinne frem med formålene.

[StoltHD]

.

Endret 4. desember 2012 av StoltHD

[LonelyMan]

Med såpass mye data (jeg må likevel vite strukturen) så ville jeg gått frem forsiktig for å mest ytelse. Jeg ville gjort følgende:

 

1: Sjekke cpuid for hva maskinvaren støtter, sse støtte.

2: Om den støtter sse, ville jeg lastet inn 128 bytes om gangen med page alignment

3: Jeg ville om mulig sjekket for large page støtte og allokert lesebuffer med large page

4: Jeg ville brukt sse instruksjoner for å unngå cachen ved skriving, skrive direkte til RAM (med så store data lønner det seg ikke å la de flyte oppover hierarkiet)

5: Jeg ville brukt sekvensiell scan ved lesing fra filer for å optimalisere cachen ved lesing

6: Jeg ville brukt flagg for å skrive direkte til disk, unngå cache ved skriving

7: Jeg ville styrt unna memory mapped files og lastet inn kun multipler av clustersize på den gitte disken for å spare tid og redusere overflødig data.

8: Jeg ville sjekket cpuid for størrelse på L3 cache og pre-allokert en page-alignet minneblokk basert på størrelsen på L3 kun ved lesing

7: Deretter ville jeg lest 128 byte-chunker med sse instruksjoner (muligens en stream instruksjon som bypasser cachen)

8: Jeg ville lest dataene fra slutten av bufferen og tilbake for å unngå cache pollution på visse cpu'er

9: Jeg ville sjekket cpuid om prosessoren støtter ht, om den gjør det ville jeg vurdert om dataene er varierte nok til om jeg ville unngå bruk av HT eller ikke.

10: Jeg ville flyttet alle variabler som ikke gjenbrukes til en egen virtuell side med nocache flagg satt

11: Deretter ville jeg forsøkt å dele stackplass mellom viktige prosedyrer som arbeider paralellt

12: Jeg ville delt opp arbeidet i chunker mellom trådene og satt affinitet til litt høyere enn normalt

13: Jeg ville optimalisert min egen quicksort algoritme på min egen måte, om man kan bruke den algoritmen, det avhenger av type data og struktur

14: Jeg ville unngått all form for api funksjoner mens den arbeider for å forhindre ring 0 og forstyrrelse av tråd synkronisering, og annen forstyrring forøvrig

15: Jeg ville brukt brukernivå synkronisering med pause instruksjoner for å unngå cache pollution

 

Dette er bare sånn, generelt sett, det avhenger fremdeles hva slags data vi snakker om.

[GeirGrusom]

Det er vel neppe CPU-en som er flaskehalsen her... Tror du har langt mer å tjene på en effektiv algoritme enn hva CPU-en måtte finne på å støtte.

[Hieronymus]

Dette er bare sånn, generelt sett, det avhenger fremdeles hva slags data vi snakker om.

 

Jeg tipper at du finner opp hjulet på nytt hver gang du skal løse en oppgave.

[tomsi42]

Jeg tipper at du finner opp hjulet på nytt hver gang du skal løse en oppgave.

Det vel heller snakk om å sjekke forholdene før man velger riktige hjul?

[LonelyMan]

tomsi42 har forstått det. Om man spør en sportsutøver hvordan han har tenkt å gå frem for å vinne i en konkurranse, så legger han frem detaljert plan som er god, så spør mannen, "finner du opp hjulet hver gang du skal vinne i sporten". Så svarer sportsmannen "Jeg finner ikke opp hjulet, jeg benytter meg av hjulet, det er en vesentlig forskjell".

 

Det er noen som tror at det er automatikk i alt, at den beste løsningen allerede blir implementert automatisk, det gjør ikke det. Og spesielt ikke i dette tilfellet. Over halvparten av lista vil ikke bli automatisk implementert på tross av hva de over tror om det.

 

GeirGrusom, du har virkelig ikke forstått det.

 

1: Du sier en bedre algoritme er løsningen, jeg har nettopp fylt inn i lista mi at jeg ville brukt en bedre customized algoritme.

 

2: Flaskehals teorien din er bare en illusjon, se illustrasjon jeg har tegnet her:

3: SSE kan skrive data opp mot 7.5 ganger raskere enn tradisjonell måte og det er ikke et given at kompilatoren vil gjøre dette automatisk for deg, spesielt vil ikke kompilatoren vite hvilken fremgangsmåte som passer best og den kan heller ikke optimalisere bruken av registrene på tvers av prosedyrer. Potensielt spart tid her er 7.5 ganger på toppen av illustrasjonen over (som kommer i tillegg), og dette er en cpu spesifik optimalisering.

 

4: Du vet ikke hvor komplisert strukturen av dataene er på oppgaven, om strukturen er veldig komplisert så vil det kreve mer prosessorkraft, og da kan det være at HT lønner seg, HT er prosessor spesifik.

 

5: sekvensiell scan er en system spesifik optimalisering og er ikke cpu spesifik, så det jeg nevner er ikke bare cpu spesifike optimaliseringer. Det handler om å fortelle systemet mest mulig om hva du skal gjøre slik at det kan gjøre det på best mulig måte. Her sparer man mye tid også, hvor mye nøyaktig er uviss.

 

6: deling av virtuelt område mellom prosedyrer (samt bruker-synkronisering) kan forhindre aliasing problemer, potensielt (hvis uoppmerksom) så kan man spare opp mot 200 sykluser per iterasjon og i verste fall om du er uforsiktig kan du spare millioner av sykluser per iterasjon, totalt sett er dette en katastrofe hvis du ikke adresserer det og din variant vil være haugevis mye tregere.

 

7: Om du ikke bruker multipler av clustersize så vil du gjenlese de samme dataene flere ganger per iterasjon, og denne typen optimalisering er ikke cpu spesifik, den er disk-spesifik og er katastrofalt å ikke addressere. Her snakker vi om hundrevis av millioner sykluser spart.

 

Og jeg kunne nevnt mer..

Endret 5. desember 2012 av LonelyMan