Vi har skrevet hel fordi vi må kunne flytte seminartimen til et større rom dersom det blir fullt, og derfor er det fint om studenter møter opp litt før.

Hvor blir det som skrives på fellesøvelsen lagt ut?
http://folk.uio.no/magnudae/INF1010/ er ikke oppdatert siden April.

Nei, dette vil skje når algoritmen som en tråd bruker til å sortere sin del av tabellen første gang er ganske treg (av orden n^2). Siden fletting er en ganske rask sorteringsalgoritme (av orden n*log(n)) vil bare det faktum at trådene bruker en god sorteringsalgoritme i seg selv gi en hastighetsøking, også selv om man ikke hadde puttet på flere kjerner. Så gir flere kjerner også et bedre resultat selvsagt.

Jeg benytter en ikke optimalisert selection sort. På en fire kjerners i7 3720qm får jeg beste resultat med ca 0,2 sekunder rundt 500 tråder med sowpods filen. Lager egne tråder for hver merge av to sorterte del arrayer. Drøyt 9 minutter på en tråd og 1,4 sec på 8192 tråder som ytterpunkter.

Lurt å sjekke at den sorterte tabellen man får ved hjelp av din sorteringsprogram er identisk med sorteringresultatet man får med Java sitt `Arrays.sort`. Hvis ikke disse stemmer, er det 99% sikkert at ikke alt fungerer som det skal.

java Sort 2 sowpods.txt out.txt
Took: 393 millis

java Sort 4 sowpods.txt out.txt
Took: 381 millis

Tiden som brukes for fil innlesning er ikke med.

Med “at det ikke ligger en null-peker som siste element.” menes at siste peker ikke er “null”.

java Oblig6 1 sowpods.txt out.txt
Took: 468 millis

java Oblig6 40 sowpods.txt out.txt
Took: 377 millis

java Oblig6 1000 sowpods.txt out.txt
Took: 866 millis

java Oblig6 2000 sowpods.txt out.txt
Took: 1156 millis

Hva mener dere med “at det ikke ligger en null-peker som siste element.”

Men når du skal flette bør du nok returnere pekeren til “felles”-tabellen, og så flette når du er tilbake fra kallet (slik at du ikke stenger monitoren mens du fletter).

Husk at notify() ikke frigjøre monitoren. Det eneste notify() gjør er å starte opp en tråd som venter i en wait().

Jeg er enig med deg at med denne løsningen trenger du ikke noe wait(), men som “Haggfinn” sier, da trenger du ikke noe notify() heller.

litt pseudokode:

class Buffer {
felles String[];
boolean merge;

Synkronisert void leggigjenellermerge (trådens array) {
hvis !merge{
felles = trådens;
merge = true; <-neste tråd vil da merge
notify(); <- tråden er ferdig med fellesdata
}
hvis merge{
String[]a = felles; <- kopi, felles forblir urørt
merge = false <- neste tråd merger ikke
notify(); <- tråden er ferdig med fellesdata
merge(a,trådens); <- og sorterer deretter
}
}
Ved å bruke boolean merge i en synkronistert metode vil du få true og false annenhver gang med sikkerhet. Hvis du da i merge() til slutt kaller leggigjenellermerge() igjen, har du en loop gående hvor annenhver tråd vil dø og de gjenværende tråder stadig får større del-løsninger.

Jeg ser ingen bruk for wait()