Obligatorisk oppgave nr. 4
Oblig 4 er nå publisert med innleveringsfrist kl 14 onsdag 16. mai. Merk dato og tidspunkt. Som det står i oppgaven skal det leveres lister til fakultetet rett etter 16. mai med navn på alle som har fått godkjent alle de fire obligatoriske oppgavene. Det betyr at fristen denne gang er mer absolutt en tidligere.
Les oppgaven og snakk med retteren din.
På starten av fellesøvelsen den 25. april vil Stein Gjessing være tilstede og svare på spørsmål om oppgaven. Lykke til.
139 Responses to “Obligatorisk oppgave nr. 4”
Er det et krav at programmet skal sortere på samme array?
Eller er det lov å dele det opp i mindre deler for så å flette delene sammen til slutt?
[Reply]
Stein Gjessing Reply:
April 24th, 2012 at 11:39
> Er det et krav at programmet skal sortere på samme array?
Nei det er ikke et krav (Jeg tror kanskje ikke det er mulig)
>Eller er det lov å dele det opp i mindre deler for så å flette delene sammen til slutt?
Du SKAL dele opp i mindre deler, men du SKAL alltid flette sammen 2 ferdigsorterte deler (til en større del), osv.
[Reply]
Sigmund Hansen Reply:
April 25th, 2012 at 14:21
> Jeg tror kanskje ikke det er mulig
Om du snakker om fletting, så går det helt fint an å gjøre på stedet (in-place), men det tar litt lengre tid enn å gjøre det med ekstra rekker. Det bruker derimot mindre minne.
Det finnes selvfølgelig algoritmer som ikke kan gjøres på stedet. Alle varianter av bøttesortering krever f.eks. at bøttene er egne rekker (eller andre datastrukturer). Tresortering krever at alt puttes i et søketre.
Men man kan alltids putte resultatet tilbake i den opprinnelige strukturen i sortert rekkefølge til slutt, men det gir en ekstra gjennomgang til slutt i noen algoritmer.
[Reply]
Øverst i sowpods filen står det at den inneholder x-antall ord. Er dette antallet riktig?
[Reply]
Tarjei Reply:
April 24th, 2012 at 18:34
Det står at filen inneholder 267751 ord, dog når jeg kjører programmet kræsjer det, noe som får meg til å tro at filen ikke inneholder dette antallet ord(funker for den andre filen).
[Reply]
Martin Reply:
April 24th, 2012 at 19:16
Det er riktig antall ord i sowpods.txt.
[Reply]
Sigmund Hansen Reply:
April 25th, 2012 at 00:23
Antallet er nok riktig, men pass deg for tomme linjer om du bruker Scanner.nextLine()
[Reply]
Tarjei Reply:
April 25th, 2012 at 10:13
Og da var problemet løst
Takk
Er det meningen at vi skal bruke en såkalt “quicksort” algoritme når vi skal sortere ordene?
[Reply]
Stein Gjessing Reply:
April 25th, 2012 at 12:24
NEI. Du kan velge akkurat den sorteringsalgoritmen du vil. Oppgaven anbefaler at du skriver en enkel algoritme med en enkel invariant. Men du må gjerne bruke quicksort hvis du vil, men den er litt fiklete å få til. I grove trekk er invarianten enkel i quicksort, men den helt detaljerte iinvarianten er ikke det.
Quicksort var pensum i fjor, men er ikke pensum i år.
[Reply]
Hva menes med dette i oppgaveteksten?
“Hver tråd skal sortere N= «antOrd»/«antTråder» ord (+/- 1)”
[Reply]
Stein Gjessing Reply:
April 25th, 2012 at 16:14
At hver tråd skal sortere like mange ord (pluss eller minus ett ord)
[Reply]
Hva er sorteringskriteriet? Alfabetisk?
[Reply]
Marius Reply:
April 25th, 2012 at 19:11
På plenum i dag, hørtes det ut som om det var størelsen på ordet som var rangeringen.
[Reply]
Stein Gjessing Reply:
April 25th, 2012 at 19:32
Alfabetisk.
[Reply]
Hei,
Veit ikke om jeg har skjønt dette rett, men vil det være riktig om hver tråd har sin egen sorteringsalgoritme?
Slik at denne ikke er låst eller synchronized for da sparer jeg vel ikke noe tid?
[Reply]
Stein Gjessing Reply:
April 25th, 2012 at 19:33
Du har helt rett.
Men jeg ville nok sagt at hver tråd UTFØRER sin egen sortering, men at alle trådene gjør dette i henhold til samme sorteringsalgoritme
[Reply]
Hei, er det en god idé å sortere vha Quicksort algoritmen?
[Reply]
Stein Gjessing Reply:
April 26th, 2012 at 14:01
Ja, men du må regne med å fikle litt for å få det riktig.
[Reply]
Kan jeg bruke ferdige sorteringsmetoder i java.util.Arrays?
[Reply]
Stein Gjessing Reply:
April 27th, 2012 at 11:33
Sitat fra oppgaven: ” Du skal selv programmere (og skjønne alle detaljer i) den sorteringsalgoritmen du velger.”
[Reply]
Hvor lang tid skal det ta for et program å komme gjennom sowpods(267751 ord) med 1 tråd, for at koden skal bli godkjent?
Koden min brukte rundt 10sek med 100 tråder, litt over 4 min med 10 tråder. Programmet har kjørt 15+ min nå uten resultat med 1 tråd.
[Reply]
Karl Reply:
April 27th, 2012 at 23:35
30+ min nå med 1 tråd på sowpods. Er det meningen at dette skal ta så lang tid eller må jeg endre strukturen på koden min?
[Reply]
joshi Reply:
May 1st, 2012 at 00:36
Hvis du bruker f.eks. innstikk vil det ta så lang tid ja. Men det som det blir sagt under, det viktige er å forstå effekten av parallellisering og Amdahl’s lov. Det er ikke noe poeng i å løse sowpods.txt med 1 tråd innstikk for annet enn å understreke hvor dramatisk tidsbesparingen kan være.
Innstikk og bubble sort kan fungere bra på mindre utvalg, men har n^2 average, noe som er polynomial tid. Om du blir ferdig med innstikk kan du jo prøve merge sort eller quicksort som begge har n log n som average. Bruk denne artikkelen til å se forskjeller (big O er ikke pensum, men veldig interessant!):
http://en.wikipedia.org/wiki/Sorting_algorithm
Men se den enorme forskjellen, her er kjøretiden for sowpods for en rekke andre algoritmer (1 tråd).:
[00:32:58] joshi@safir: ~/inf1010/2011/oblig4/old $ javac Sort.java
[00:33:01] joshi@safir: ~/inf1010/2011/oblig4/old $ java Sort sowpods.txt 0
Read 267751 words in 0.08 sec from sowpods.txt.
Radix sort 1.56 sec
Merge sort 0.35 sec
Quicksort 0.23 sec
Heap sort 0.31 sec
[00:45:28] joshi@safir: ~/inf1010/2011/oblig4/old $ java Sort 800000.txt 0
Read 800000 words in 0.20 sec from 800000.txt.
Radix sort 0.71 sec
Merge sort 1.07 sec
Quicksort 0.76 sec
Heap sort 1.71 sec
[Reply]
Martin Reply:
April 28th, 2012 at 08:58
Sånn jeg forstod det, var ikke sorteringsalgoritmens effektivitet av betydning: poenget ligger i å se hvordan tråder påvirker kjøretiden.
[Reply]
Arash Reply:
April 29th, 2012 at 02:10
Min kode bruker ca 45 minutter med 500 tråder(eller det blir laget 999 tråder tilsammen).
Tror ikke at det er noe “spesiell” krav på tiden, siden det ikke står i oppgaveteksten.
Btw, det går også på Pcen din. Altså hvor rask den er.
[Reply]
Jeg bruker en pyramidestruktur på trådene mine, vil dere si at hver tråd som ikke brukes til å sortere teller som en tråd?
Hvis jeg skal sortere med 4 tråder blir da disse delt opp i 2 tråder hvor hver av dem lager 2 tråder hver som sorterer. På den måten er det 2+4 tråder aktive samtidig, men kun 4 som sorterer. De overflødige 2 blir satt på vent og gjør ingenting.
[Reply]
Hvor stor er egentlig oppgaven cirka? I forhold til oblig 3?
[Reply]
Stein Gjessing Reply:
May 2nd, 2012 at 22:06
En tredjedel ??
[Reply]
Hei,
Er det noen der ute som kan jeg meg et tips på hvordan jeg tildeler hver enkelt tråd N-antall ord fra arrayen?
[Reply]
Martin Reply:
May 2nd, 2012 at 22:19
Trådene mine er en indre klasse i hovedklassen min, slik at de har direkte tilgang til arrayen, men hadde de ikke vært det, hadde jeg sørget for at de hadde fått en peker til arrayen. I konstruktøren mottar de en nedre og øvre indeks som beskriver området de skal sortere. La N være heltallsdivisjonen av «antOrd»/«antTråder». Med enkle løkker sørger jeg for at de «antOrd» % «antTråder» første trådene får N + 1 ord, og de «antTråder» – «antOrd» % «antTråder» neste trådene får N ord.
[Reply]
Arash Reply:
May 9th, 2012 at 03:06
En mye enklere måte dele navnene på er å gi de antOrd%antTråd siste trådene “N+1″ ord, og resten “N” ord.
Denne formelen fungerer i “alle” tilfeller.
Hvis vi tar utgangspunkt i det første eksempelet:
antOrd = 5163
antTraader = 128
modulu = 43 (5163 %128)
N = 40 (5163/128)
Da får de “43″ siste trådene N+1(40+1=41) ord.
Altså fra tråd nr “0″ til og med tråd nr “85″ får N(40) ord, og fra tråd nr “86″ så legger man ET ekstra ord til arrayene(N+1).
[Reply]
Arash Reply:
May 9th, 2012 at 03:07
*mye enklere måte å…
[Reply]
Martin Reply:
May 9th, 2012 at 08:39
Dette er nøyaktig det samme, bortsett fra at du gir N+1 ord til de siste trådene,mens jeg gir N+1 ord til de første trådene. Hvordan er det enklere?
[Reply]
Martin Reply:
May 9th, 2012 at 08:57
Kanskje forvirringen oppstod ved at jeg brukte ord til å beskrive aritmetikken min, men det er enkelt å overbevise om at dette er likt:
Du definerer N = 40 = 5163 / 128 = antOrd/antTraader. Som nettopp er heltallsdivisjonen av «antOrd»/«antTråder».
Du kaller resten for modulo (modulo er operasjonen, men ikke et godt navn på resultatet, forresten) modulu = 43 (5163 %128) = antOrd%antTraader, som nettopp er «antOrd» % «antTråder».
Dernest lar du resten av trådene = 128 – 43 = antTraader – modulo = antTraader – antOrd%antTraader få hakket færre ord, som igjen er forbausende i overensstemmelse med mitt forslag.
Du kan lage en konstruktør i tråden som har (minst) tre parametre: Hele tabellen, nedre grense og øvre grense.
[Reply]
Takk for tipsene, og superrask tilbakemelding! Da skal jeg se hva jeg får til her…
Kan det også være en mulighet å bruke Arrays.copyOfRange() ?
[Reply]
steing Reply:
May 3rd, 2012 at 08:47
Ja, men kan du ikke bare hente en og en peker fra tabellen som er parameter og legge pekerene ferdig sortert inn i en ny tabell. Innvarianten på den nye tabellen kan være at den er ferdig sortert fra 0 til k, der k øker fra 0 til lengden av tabellen.
[Reply]
Blir det feil om sorteringsalgoritmen er i en synkronisertmetode i en annen klasse enn trådklassen?
[Reply]
steing Reply:
May 3rd, 2012 at 08:33
Ja, det blir antagelig feil
[Reply]
Haavar Reply:
May 7th, 2012 at 21:27
Men det er vel ikke feil at sorteringsalgoritmen er synkronisert ?
[Reply]
Stein Gjessing Reply:
May 7th, 2012 at 23:38
Joo – jeg tror det. Sorteringsalgoritmen utføres av trådene, og tråder er jo ikke synkronisert (“synchronized”).
Mange skal utføres samtidig og helt uavhengig av hverandre.
Det er bare når du legger inn resultater i en monitor at metodene i monitor-objektet er synkronisert og at det derfor bare kan utføres en monitor-metode om gangen.
Hva menes med invariant? ( “Lag gjerne en enkel algoritme med en grei invariant.”)
[Reply]
steing Reply:
May 3rd, 2012 at 11:35
Invarianter (eller invariante tilstandspåstander) kan du lese om i lysarkene fra forelesningen den 19. april
[Reply]
Miriam Reply:
May 8th, 2012 at 10:56
Hvor finner man lysarkene? Jeg finner ikke noe via kurssidene…
[Reply]
Martin Reply:
May 8th, 2012 at 14:05
I høyremargen under ‘Underivsning’:
http://www.uio.no/studier/emner/matnat/ifi/INF1010/v12/tid-og-sted.html
Er det lov å bruke f.eks ArrayList i programmet? f.eks når man skal sortere?
[Reply]
Det må vel være lov siden det ikke står noe om det. Men husk at du skal skjønne alle detaljer i sorteringsalgoritmen, og det er kanskje litt vanskelig hvis du bruker ArrayList. Meningen var at du skulle bruke en vanlig array.
[Reply]
Når en tråd har sortert sin egen del, skal den da puttes inn i en ferdig løsnings-array eller lignende, for så å sortere den der? Vil det si at vi først skal sortere et bruddstykke, og så putte bruddstykke inn i løsnings-arrayen som igjen skal sorteres? Eller har jeg misforstått?
[Reply]
Stein Gjessing Reply:
May 3rd, 2012 at 21:28
Jeg tror det er best at en ferdige sortert del puttes inn i en beholder (eller lignende). Når det er to slike ferdige sorterte biter i beholderen, kan en tråd hente disse ut og sortere dem ved å flette dem.
[Reply]
Lassie Reply:
May 3rd, 2012 at 21:56
Men hva vil det si å flette dem? Er det en spesiell teknikk for akkurat dette? Eller er det bare å sortere igjen.
[Reply]
Stein Gjessing Reply:
May 3rd, 2012 at 22:06
Når du fletter to sorterte arrayer, så får du en ny sortert resultatarray som har lengde lik summen av de to. En måte å gjøre dette på er å først lage en tom resultatarray av riktig lengde, og så gå i en løkke og flytte det til enhver tid minste elementet fra en av de to arrayene over i resultatarrayen.
Haavar Reply:
May 4th, 2012 at 12:21
Men resultatarrayen må jo igjen da flettes inn i den endelige arrayen.. eller?
Har jeg forstått dette riktig? Altså..
1. først sorterer hver tråd et bruddstykke
2. så sorterer vi to og to bruddstykker sammen til en “resultatarray” som Stein sier..
3. Deretter må denne resultatarrayen flettes inn i en endelig array, altså den arrayen vi skal stå igjen med og som har lik lengde den opprinnelige
Stein Gjessing Reply:
May 4th, 2012 at 14:30
Den endelige arrayen er resultatet av den aller siste flettingen
Hei,
Er det lov å benytte seg av f.eks ExecutorService og CountDownLatch ?
[Reply]
Stein Gjessing Reply:
May 4th, 2012 at 14:29
CountDownLatch er pensum, og det kan du absolutt bruke. ExecutorService og ThreadPools er ikke pensum og det er ikke sikkert du kan få hjelp til å bruke det. Snakk med retteren din om det på forhånd hvis du har lyst til å bruke det.
[Reply]
Hva er fristen for å gi tilbakemelding på Oblig3. Er det 2 uker altså idag?
[Reply]
Hei!
Når det gjelder ord som blir til overs, er det lov å putte alle disse inn i EN array, som da blir større enn alle de andre, eller må ordene som er til overs puttes ett og ett inn i de allerede eksisterende arrayene? I oppgaven står det +/- 1, en er dette et absolutt krav?
[Reply]
Stein Gjessing Reply:
May 4th, 2012 at 15:07
Ja, jeg synes dette bør være et absolutt krav. Hvis f.eks arrayen er 66 lang, og du får beskjed om å bruke 4 tråder, får du 16 ved heltallsdivisjon og en rest på 2.
Da kan du legge til 1 på de første arraybitene du sender til de første trådene (som da blir 16+1 = 17 lange). Når du har gjort dette to ganger, er det ingen igjen til overs, og de (to) siste trådene får en arraybit med lengde 16. I oppgaven burde det da stått at alle arraybiter er like lange (+1/-0).
[Reply]
Jeg deler opp navnelisten i rett antall tråder og sender hvert delarray til konstruktør i trådklassen.
Run metoden kaller på sortermetoden i trådklassen.
Når jeg gjør utskrift av feks første element i delarray før det sendes til konstruktør og utskrift av samme element i runmetoden så er det ikke alltid samme element. Ofte er det likt men så plutselig skrives samme element i runmetoden til flere tråder ut flere ganger.
Fungerer det ikke å sende delarray til trådklassen?
[Reply]
Jonny Reply:
May 5th, 2012 at 12:32
Hva mener du med “delarray”? Du gir bare tråden pekeren til hovedarray’en (den du opprettet når du leste filen med ordene som skal sorteres), sammen med hvilke indekser tråden skal jobbe med (start- og stopp-indeks, eller startindeks og antall elementer eller lignende).
[Reply]
Erik Reply:
May 5th, 2012 at 16:42
Det blir fortsatt feil. Det ser ut som noen av trådene endrer på peker til hovedarrayet. Hva kan være feil?
[Reply]
Delarrayer er mulig Reply:
May 5th, 2012 at 12:38
http://www.2shared.com/file/rNXYbeaa/Erik.html
Forsøk på å gjenskape fremgangsmåten din ga ikke nevnte feil.
[Reply]
Jonny Reply:
May 5th, 2012 at 12:47
Ja, mulig å gjøre det slik, men blir ekstra minneforbruk og tidsbruk på å kopiere array-elementer.
[Reply]
Erik Reply:
May 5th, 2012 at 13:06
Takk for flott svar, jeg studerer koden og prøver å finne ut hva jeg har gjort feil.
[Reply]
Hei,
Har prøvd å gå ut ifra forslaget som ble gitt på forelesningen der det ble laget tråder i en slags tre-struktur.
Jeg lurer på: Når jeg kommer til det punktet at jeg ikke lenger lager nye tråder, men heller begynner å sortere en andel av arrayet, hvordan skal jeg flette disse delene på vei “tilbake”? Jeg anntar at det ikke er godkjent å bare sortere de ferdig-sorterte delene på vei tilbake? Dette er vel ikke fletting?
Sånn jeg forstår det da er at når jeg lager trådene må jeg alltid dele den aktuelle andelen av arrayet som skal sorteres i to deler – større og mindre enn en eller annen verdi(median?)? Og dermed kan jeg til sutt flette ved at delen til venstre alltid er mindre enn den til høyre. Er dette riktig?
Så lurer jeg på; hvis jeg gjør det på denne måten ville jeg vel egentlig ikke trengt å flette på vei tilbake, da arrayet allerede ville vært sortert når alle trådene har gjort sin del.
Jeg skjønner altså ikke helt hvordan jeg skal gjøre dette.
Noen som har tips?
[Reply]
Stein Gjessing Reply:
May 7th, 2012 at 08:35
Ja, det blir en slags tre-struktur, men aller først deler du tabellen (arrayet) opp i mange like store biter og sorterer dem hver for seg (“Hver tråd skal sortere N= «antOrd»/«antTråder» ord “). Når du så starter å flette alle disse bitene blir det en slags tre-struktur, der stadig færre tråder fletter stadig lengere biter. Til slutt fletter en tråd to biter som til sammen er hele tabellen.
[Reply]
Espen Reply:
May 7th, 2012 at 12:27
Okei, men hvis man gjør det på denne måten, betyr fletting da noe annet enn sortering? må jeg ikke da hele tiden(på vei nedover treet) sortere de ferdig sorterte delene, ettersom disse antakeligvis verken er større eller mindre enn hverandre?
[Reply]
Stein Gjessing Reply:
May 7th, 2012 at 13:02
Fletting (Flettesortering, Engelsk: Merge sort) er faktisk i seg selv en meget effektiv sorteringsmetode.
Er det krav at det er maintråden som skriver ferdig sortert liste til fil?
I mitt program er det tråden som fletter ferdig som kaller på skriTilFil metoden, er det en dårlig løsning?
[Reply]
Stein Gjessing Reply:
May 7th, 2012 at 08:36
Nei, jeg synes det høres ut som en helt grei løsning.
[Reply]
Ok, jeg har nå fått til at alle trådene som blir laget sorterer sin del av ord listen, da har alle trådene en sortert array med ord/navn. Hva skal jeg gjøre nå for og sette alle disse delene sammen til en fult sortert liste?
Forstår ikke helt hvordan jeg skal bruke trådene til og flette sammen alle disse arrayene.
[Reply]
Stein Gjessing Reply:
May 9th, 2012 at 16:07
Når en tråd har en ferdig sortert tabell (array), kan den gi den til en monitor / beholder. Fra denne beholderen kan en/noen tråder hente ut to og to tabeller, sortere dem ved å flette dem sammen, og så legge resultatet ned i en monitor/beholder (dette er enten den samme eller en annen beholder). Det er mange måter å finne ut at oppgaven er ferdig løst, f.eks. når en tråd har laget en tabell som er like lang som den originale, usorterte tabellen.
[Reply]
Sigmund Reply:
May 9th, 2012 at 17:03
Ok, men det jeg ikke helt forstår er når en tråd har sortert sin del, så skal den sende den sorterte arrayet til beholderen. Hvordan skal den samme tråden jobbe med det som er i beholderen. Siden jeg har jo for eksempel 128 tråder. Da skal vell 64 tråder flette sammen 2 lister. Så 32 tråder, så 16 tråder etc etc.
Er det en god tutorial et sted om monitor?
[Reply]
Stein Gjessing Reply:
May 9th, 2012 at 17:14
>Er det en god tutorial et sted om monitor?
Jeg skal se om jeg finner noe, men hvis du kan det som står i lysarkene fra forelesningene kan du nok for INF1010.
Stein Gjessing Reply:
May 9th, 2012 at 22:30
>Er det en god tutorial et sted om monitor?
Jeg fant dette:
http://en.wikipedia.org/wiki/Monitor_(synchronization)
Thomas Reply:
May 10th, 2012 at 09:57
Du trenger ikke bruke den samme tråden til å flette. Hver gang monitorklassen har mottatt 2 sorterte tråder, oppretter du et nytt trådobjekt av en annen klasse som fletter disse 2 trådene. Når flettetråden er ferdig sendes den ferdige flettede tråden tilbake til monitorklassen. Monitorklassen må ha en sjekk om alle tråder er ferdig sortert/flettet, feks når mottatt array har lengde lik antall ord i innlest fil.
Stein Gjessing Reply:
May 10th, 2012 at 10:09
Det Thomas sier er veldig bra, men her er bare en liten presisering:
Du trenger ikke bruke den samme tråden til å flette. Hver gang monitorklassen har mottatt 2 sorterte ARRAYER, oppretter du et nytt trådobjekt av en annen klasse som fletter disse 2 ARRAYENE. Når flettetråden er ferdig sendes den ferdige flettede ARRAYEN tilbake til monitorklassen. Monitorklassen må ha en sjekk om alle ARRAYER er ferdig sortert/flettet, feks når mottatt array har lengde lik antall ord i innlest fil.
Sigmund Reply:
May 10th, 2012 at 16:12
Takk for hjelpen, ser ut som alt fungerer nå, får vertfall skrevet ut en sortert liste
Prøver å lage en slags tre-struktur på disse trådene mine. Hvis jeg fra kommandolinja får at antTråder skal være 4, er det slik at det kun er lov å si “new MyThread()” 4 ganger? Eller er det kun 4 tråder som kan kjøre i parallell, mens andre venter (på å flette)?
[Reply]
Stein Gjessing Reply:
May 9th, 2012 at 16:37
Du kan godt la andre vente på å flette (og kanskje tre-strukturen oppstår av seg selv ?)
[Reply]
Inthu Reply:
May 9th, 2012 at 17:16
Ja, jeg lagde bare første tråd fra main, så gjorde den resten av jobben. Men i tilfellet med antTråder=4 endte jeg opp med å lage 7 tråder hvorav 4 sorterte, mens resten ventet. Etter sortering ble de sovende trådene vekket og startet flettingen.
Slik koden min er blir det lagd utrolig mange tråder i det tilfellet hvor antTråder=128. Ikke noe særlig tidsbesparende. Prøvde å fjerne ventingen, ved at én tråd lagde ett tråd og fortsatte noe av sorteringen selv. Men da ble array-et sortert delvis (og flettingen kræsjet).
[Reply]
Stein Gjessing Reply:
May 9th, 2012 at 19:11
>ved at én tråd lagde ett tråd og fortsatte noe av sorteringen selv.
Det er nok mulig å få riktig, men litt mer fiklete.
Men hvis du må lage 128+127 tråder er ikke det så galt. I INF1010 er det viktigere å forstå og bruke tråder enn å få det helt optimalt. En sovende tråd bruker ikke mye ressures, så det synes jeg ikke er så farlig. Det tar litt tid å lage en ny tråd, men som sagt, det bryr vi oss ikke så mye om i INF1010.
Er det meningen at man skal merke noen forskjell ved bruk av flere tråder? Programmet mitt bruker Merge Sort og tar ca 5 sekunder fra start til mål uavhengig av antall tråder. Er det rett og slett fordi det er de synkroniserte metodene i monitoren som tar mesteparten av tiden, samtidig som den første sorteringen tar ca like lang (kort) tid uavhengig av antall tråder, eller er det noe kritisk galt med programmet?
[Reply]
Jonny Reply:
May 10th, 2012 at 11:29
Prøv med en tregere sorteringsalgoritme, så blir det enklere å se effekten. Ved å bruke insertion sort ser tidsforbruket slik ut med min implementasjon (dette er kun sorteringen – innlesing av fil, kreering av tråder og skriving av resultater til fil holdes utenfor):
1 tråd: 1824.188 sek
2 tråder: 431.974 sek
4 tråder: 125.799 sek
8 tråder: 40.833 sek
16 tråder: 13.346 sek
32 tråder: 5.131 sek
64 tråder: 2.614 sek
128 tråder: 1.779 sek
Med quicksort-algoritmen tar sortering rundt omkring 0.5 sek nesten uansett hvor mange tråder som jobber…
[Reply]
Obs. Hvis noen får denne erroren:
java.lang.OutOfMemoryError: unable to create new native thread
Når dere sitter på et ekstern skrivebord. Koblet til ifi via. f.eks. putty eller xterm, så ikke bekymre dere.
Det er nemlig satt en begrensning på hvor mange tråder man kan kjøre når man er koblet til eksternt. Jeg tror begrensningen er på 200 tråder.
Ta heller å test programmet på din egen maskin, eller dra til ifi og test der.
[Reply]
Noen som har en forklaring på dette fenomenet:
1 trad – 1.538 sek
5 trad – 0.244 sek
10 tråder – 0.265 sek
100 tråder – 0.24 sek
1000 tråder – 0.388 sek
2000 tråder – 0.653 sek
Den bruker lengre tid hvis jeg bruker 100+ tråder? og bruker bare mer og mer tid ettersom jeg øker antallet tråder over 100. Tallene er hentet fra names.txt dog gjelder det alle filene jeg kjører. Er det fordi arrayen blir delt opp i for mange deler, og at det faktisk tar lengre tid å håndtere så mange små arrayer?
[Reply]
Jonny Reply:
May 10th, 2012 at 17:37
Det finnes sikkert minst like mange forklaringer som det finnes måter å implementere dette på…
Hvis kreeringen av trådene er med i disse måleverdiene, er det en god forklaring på dette. En annen sak er at det blir svært mange små jobber som skal flettes sammen, så det går en del tid til dette (implementasjonen av flettingen vil få større og større betydning jo flere tråder du har). Det blir også få elementer i hver delarray med så mange tråder (100 tråder = 51/52 elementer i hver delarray, 2000 tråder = 2/3 elementer i hver delarray… selve sorteringsalgoritmen blir for så små array’er mindre viktig).
[Reply]
Fant en fin måte å kopiere et del-array inn i et annet array.
System.arraycopy(Object src,int srcPos,Object dest,int destPos,int length)
Men er dette lov å bruke? Eller må jeg gjennom hele arrayet og kopiere over den delen jeg trenger manuelt (med f.eks. en for-løkke)?
[Reply]
Stein Gjessing Reply:
May 10th, 2012 at 18:19
Jeg synes du skal trene i å lage løkker med å gå gjennom hele arrayen og manuelt kopiere.
[Reply]
Spør for én siste gang, for å være på den sikre siden.
“Første parameter i kommandolinjen kaller vi «antTråder» («threadCnt») og angir antall tråder som skal brukes til sorteringen. … Hver tråd skal sortere N= «antOrd»/«antTråder» ord (+/- 1).”
Slik jeg har skrevet programmet, oppretter den tråder som kommer i 2-er potens. Dvs, hvis jeg gir et tall i intervallet [5,8] på kommandolinja blir det opprettet 2^3=8 tråder. Gir jeg et tall i intervallet [9,16] blir det opprettet 2^4=16 tråder. Ingen av trådene vet hvor mange andre tråder det er laget. De fortsetter å dele seg i to så lenge antall elementer de har fått er større enn «antOrd»/«antTråder».
java Sort 6 names.txt resNames.txt
Her ender de siste 8 trådene med å sortere mellom 645 og 647 ord mens antOrd/antTråder=830.
Programmet fungerer strålende utenom dette, så hvor strengt bør jeg følge oppgaveteksten? Får jeg ikke-godkjent om jeg lar det ligge slik det er nå???
[Reply]
Arne Reply:
May 11th, 2012 at 22:21
Om du ikke klarer å la hver tråd sortere enten N eller N+1 ord, tror jeg du bør vurdere å finne på noe annet.
[Reply]
Stein Gjessing Reply:
May 11th, 2012 at 22:33
Så vidt jeg skjønner på det du skriver så løser du ikke problemet slik det er beskrevet (Hver tråd skal sortere N= «antOrd»/«antTråder» ord), men en variant der du først lar to tråder få ansvaret for hver sin del, så dele opp i to igjen, osv helt til hver del selv sorterer en del som er mindre enn N. Flettingen skjer på “vei opp”, og når de to første trådene har gjort den siste flettingen, så er tabellen ferdig sortert.
Jeg synes dette er en flott måte å uføre sortering med fletting på (kanskje bedre enn den opprinnelige oppgaven), og du vil opplagt få dette godkjent.
[Reply]
Høres ikke ut som du er helt i vater, hva i alle dager er det du har tenkt på her?
[Reply]
Inthu Reply:
May 12th, 2012 at 01:34
Er spørsmålet rettet mot meg? I så fall tenkte jeg bare på å få ordene sortert raskest mulig. Hadde gjort noen ukesoppgaver hvor jeg hadde brukt tilsvarende teknikk, så dette var det første som dukket opp da jeg starta på obligen. Deretter leste jeg nøye gjennom obligen og så at jeg ikke hadde oppfylt så mange av kravene. Men programmet mitt sorterte den største filen på mindre enn 0.5 sekunder og testen viste at alt faktisk var sortert. Da var jeg i grunnen fornøyd. Ble bare usikker på hvordan retteren kommer til å se på dette.
[Reply]
Stein Gjessing Reply:
May 12th, 2012 at 08:05
>Deretter leste jeg nøye gjennom
Bare husk til eksamen: Gjør det først, deretter kan du begynne å tenke.
[Reply]
Jeg sliter med inndeling av de ulike arrayelementene. Jeg er ganske sikker på at det skjer noe rart når jeg deler de opp og sender de med som grenser til to ulike tråder.
Hva gjør jeg galt her?
//threadCount er antall tråder man skal bruke
if (monitor.threadCount > monitor.existingThreads){
int half = boundary1 + (boundary2/2);
int rest = 0;
if ((boundary1 + (boundary2/2))%2 > 0){
rest = (boundary1 + (boundary2/2))%2;
}
Threads t1 = new Threads(boundary1, half, latch, wordArray, this, monitor);
Threads t2 = new Threads(half, (boundary2+rest) ,latch, wordArray, this, monitor);
t1.run();
t2.run();
t1.join();
t2.join();
}
[Reply]
Jonny Reply:
May 13th, 2012 at 11:31
Det første du bør gjøre er å endre “boundary1 + (boundary2/2)” til “(boundary1 + boundary2) / 2″.
[Reply]
Jonny Reply:
May 13th, 2012 at 11:47
Hva “rest” gjør her ser rart ut, du kan bare kutte ut den variabelen. Den andre tråden blir da
Threads t2 = new Threads(half, boundary2, latch, wordArray, this, monitor);
Med endringene mine vi altså t1 få halvparten av elementene, mens t2 vil få den andre halvparten (1 element mer hvis boundary2 – boundary1 er et oddetall). Veit ikke om det er det du ønsker, men…
[Reply]
Trine Reply:
May 13th, 2012 at 13:39
Tusen takk, nå fungerer ihvertfall inndelingen riktig såvidt jeg kan se.
Men den begynner aldri å sortere nå? :S
if (monitor.threadCount > monitor.existingThreads){
int half = boundary1 + (boundary2/2);
int rest = 0;
if ((boundary1 + (boundary2/2))%2 > 0){
rest = (boundary1 + (boundary2/2))%2;
}
Threads t1 = new Threads(boundary1, half, latch, wordArray, this, monitor);
Threads t2 = new Threads(half, (boundary2+rest) ,latch, wordArray, this, monitor);
t1.run();
t2.run();
t1.join();
t2.join();
} else {
sort();
print();
}
Jonny Reply:
May 13th, 2012 at 14:18
Jeg er litt usikker på om jeg skjønner koden din helt, men… jeg regner med denne koden er innholdet i run()-metoden i klassen Threads, som du har definert? Og at sort-metoden er en eller annen sorteringsmetode som sorterer wordArray fra og med indeks boundary1 opp til indeks boundary2?
Du mangler flettesortering etter at de 2 trådene er ferdig med sorteringen (du må putte inn flettesortering etter t2.join()). Og kommentarene jeg ga tidligere gjelder fortsatt
Trine Reply:
May 13th, 2012 at 15:31
Ops, ble litt klipp og lim, glemte å gi den redigerte versjonen.
Hva jeg kopierte inn er nesten hele run-metoden, og den kaller på sort() som er sorteringmetoden. Etter den har sortert ferdig, kaller sort() på merge().
Problemet nå er at den aldri kaller på sort nå :S
Har testet litt rundt og funnet ut at den faller ut i for-løkken i konstruktøren. Den tar inn de riktige tallene i riktig rekkefølge osv, men den går ut av programmet etterpå.
Threads(int boundary1, int boundary2, CountDownLatch latch, String[] wordArray, Threads mor, Monitor monitor){
this.boundary1 = boundary1;
this.boundary2 = boundary2;
this.latch = latch;
this.mor = mor;
this.wordArray = wordArray;
this.monitor = monitor;
monitor.existingThreads++;
//overfører verdiene fra store array til et eget
System.out.println(“\nLager eget array”);
int cnt = 0; //teller
ownArray = new String [boundary2 - boundary1];
for (int i = boundary1; i < boundary2; i++){
ownArray[cnt] = wordArray[i];
System.out.println(ownArray[cnt]);
cnt++;
}
}
Jonny Reply:
May 14th, 2012 at 00:07
Her har jeg prøvd å fjerne unødvendige ting fra koden din, dette ser ut til å fungere:
private static class Threads extends Thread { private static volatile int threadCount = 1; private static volatile int existingThreads = 0; private int boundary1; private int boundary2; private String[] wordArray; private Threads( int boundary1, int boundary2, String[] wordArray) { this.boundary1 = boundary1; this.boundary2 = boundary2; this.wordArray = wordArray; existingThreads++; } @Override public void run() { if (threadCount > existingThreads) { int half = (boundary1 + boundary2) / 2; Threads t1 = new Threads(boundary1, half, wordArray); Threads t2 = new Threads(half, boundary2, wordArray); t1.run(); t2.run(); while (t1.isAlive()) { try { t1.join(); } catch (InterruptedException e) { } } while (t2.isAlive()) { try { t2.join(); } catch (InterruptedException e) { } } MergeSort.mergeSortedSlices(wordArray, boundary1, half, boundary2); } else { QuickSort.impl.sort(wordArray, boundary1, boundary2); } } }De to sorteringsmetodene har jeg ikke med kode for her…
Koden for å starte sorteringen, som kjøres etter at ordene som skal sorteres er lest fra fil, ser slik ut:
Threads.threadCount = threadCount; new Threads(0, words.length, words).run();der words er en String[]-array og threadCount er antall tråder. Obs: Koden i threads kan komme til å opprette en tråd for mye slik det er implementert, da den etter å ha sjekket at threadCount ikke er nådd oppretter to nye tråder.
Jonny Reply:
May 14th, 2012 at 00:18
Når dette er sagt: denne koden følger ikke oppgaveteksten, da du ikke her har noen kontroll på hvor mange elementer hver tråd håndterer (du kan ikke engang si eksakt hvor mange tråder som blir kreert, bortsett fra at det blir minst threadCount tråder…) Sjekken som blir gjort på første linje i run()-metoden kan gjøres av flere tråder på nesten samme tid, dermed kan flere tråder enn threadCount bli kreert (ikke bare en for mye). Det vil også kunne bli ganske store forskjeller i hvor mange elementer hver tråd vil håndtere (noen tråder vil håndtere minst dobbelt så mange som andre tråder, gjerne 4 ganger eller 8 ganger flere også…)
Jonny Reply:
May 14th, 2012 at 00:32
Det skal forresten være t1.start() og t2.start(), ikke .run(), ellers hjelper det lite å starte flere tråder… det er greit å kjøre run() direkte for hovedtråden, derimot.
Trine Reply:
May 13th, 2012 at 16:07
Arrayet lages i feil strørrelse for tråd nr.2, ser jeg, men får det ikke til å stemme når jeg forandrer på det.
[Reply]
Nu har jeg laget en ny versjon av obligen som følger oppgaveteksten. Det som er annerledes nå er at jeg tok med en monitor klasse, så nå er synkronisering inn i bildet. Brukte samme quicksort-metode som i forrige versjon, men når jeg nå kjører
java Sort 1 sowpods.txt resSowpods.txt
bruker den 979.47 sec!!!
Dette er laaaangt ifra 0.26 sec som er tiden for den første versjonen. Hva er det som tar så lang tid??? Synkroniseringen??
[Reply]
Jonny Reply:
May 13th, 2012 at 23:38
Når du kjører med kun 1 tråd bør vel synkroniseringen ha minimalt å si…
[Reply]
Inthu Reply:
May 14th, 2012 at 10:47
Det trodde jeg også =/ Med én tråd bør begge kodene mine gå nesten like fort i og med at ingenting blir fletta. Jeg ser også at det kun er én tråd som blir oppretta, så det er den ene som jobber… Skjønner meg ikke på disse trådene.
[Reply]
Inthu Reply:
May 14th, 2012 at 11:39
Jooo… Når noe skjer i monitoren min, så er det vel main-tråden som gjør det(?). I monitoren skjer fletting på følgende måte:
Det kommer inn en tråd. Er tråden nr oddetall, blir resultatene den tar med seg lagret i en midlertidig array. Er tråden nr partall, lager jeg en peker til den tråden og sender med resultatene den selv kom med + det midlertidig lagrede resultatet fra en eller annen forrige tråd. Da kaller jeg på en metode inni denne tråden som kom inn.
Spørsmålet er, vil den tråden som får med seg resultatene gjøre sin greie på “egenhånd”? Eller er det fortsatt main-tråden som gjør det, og dermed venter på svar fra tråden før main-tråden fortsetter? Må jeg eventuelt lage en ny tråd for at denne flette-sekvensen skal gå i parallell?
[Reply]
Stein Gjessing Reply:
May 14th, 2012 at 17:28
>Når noe skjer i monitoren min, så er det vel main-tråden som gjør det(?)
Nei, når noe skjer i en monitor er det den tråden som kaller monitormetoden som utføres.
>Da kaller jeg på en metode inni denne tråden som kom inn.
Hvis jeg har skjønt deg riktig gjør du noe som kalles “call back”. Det kan være ganske komplisert, og du risikerer å ikke låse opp monitoren, det er den tråden som kalte monitoren som da utfører inne i en annen tråd etc. (altså ganske komplisert).
Prøv å bare legg fra deg resultater i monitoren, eventuelt at tråder venter på resultater (fra andre tråder) inne i monitoren.
Hvis jeg har skjønt deg rett:
I ditt tilfelle kan det hende at det kan bli riktig hvis oddetalstråder bare legger fra seg resultatet, mens partallstråder bruker resultatet til oddetallstråder, eventuelt etter å ha ventet på at oddetallstråden er ferdig.
[Reply]
Inthu Reply:
May 14th, 2012 at 19:24
> Nei, når noe skjer i en monitor er det den tråden som kaller monitormetoden som utføres.
Sjølvsagt! Litt for “tidlig” om morgenen.
Programmet fungerer fint nå, så gir meg der =) Mange takk for all hjelpen jeg har fått hittil.
Har ennå ikke blitt god venn med oppgaveteksten. Programmet sorterer nå nesten like raskt som den første versjonen. Med kommandoen
java Sort 20 names.txt resNames.txt
blir det laget 20 tråder med riktig antall elementer for KUN sortering. For fletting blir det nå laget EKSTRA tråder. Tilsammen blir det laget 39 tråder der 20 av trådene er fra sorterings-delen (som ikke lenger gjør noe). Har jeg greid å bomme på kravene igjen??
Hvordan kan jeg eventuelt la en allerede oppretta tråd ta seg av flettingen uten at monitoren driver og venter på den?
[Reply]
Stein Gjessing Reply:
May 14th, 2012 at 15:14
>Har jeg greid å bomme på kravene igjen??
Nei, du har ikke bommet på kravene. Dette er helt OK.
>Hvordan kan jeg eventuelt la en allerede oppretta tråd ta seg av flettingen uten at monitoren driver og venter på den?
Det er mange måter å gjøre dette på. Her er en måte (i grove trekk):
La alle trådene sine run-metoder ha to faser:
1. Sorter sin del og legg den i en en beholder (monitor)
2. while(flere biter å flette) {hent to biter fra en beholder og flett dem}
[Reply]
Programmet mitt funker helt perfekt på min egen pc med alle mulig verdier for antall tråder.
Men når jeg idag skulle jeg prøve programmet mitt på en av skole pcene, så kræsjet programmet ved høyt antall tråder(500++). Jeg får: java.lang.OutOfMemoryError: unable to create new native thread (eller noe ligende).
Er dette noe jeg må ta hensyn til??
[Reply]
Heihei Reply:
May 15th, 2012 at 15:32
Det stod ett eller annet sted at dersom du logger deg på skolepc-er via putty eller remote-desktop så kan du få outOfMemoryException. Kanskje det er noe lignende som har skjedd her, sikkert ikke noe problem.
[Reply]
Har et merkelig problem når det gjelder skriving til fil der ikke alle ordene blir skrevet. Stopper et sted på “m”, alt etter hvor mange tråder jeg bruker (??).
Dette oppstår ikke når jeg tester ved å skrive til kommandolinjen (på samme sted som jeg skriver til fil).
slik:
for (String s : merged) {
pw.println(s);
}
Noen som har den fjerneste anelse hva som er galt?
[Reply]
Chris Reply:
May 15th, 2012 at 13:38
Her gikk det galt. Skal stå:
for (String s : sortedTable) {
System.out.println(s);
pw.println(s);
}
[Reply]
Marit Reply:
May 15th, 2012 at 18:05
Husk pw.close(). Jeg glemte det og da stoppet det rundt m et sted
[Reply]
Chris Reply:
May 15th, 2012 at 19:26
Glimrende! Var der feilen lå
Jonny Reply:
May 15th, 2012 at 14:58
Er du sikker på at ’sortedTable’ inneholder det forventede antall elementer? Skriving til fil går også mye kjappere enn skriving til skjerm, kanskje det kan gi et hint om hva som er galt…?
[Reply]
Når jeg kjører programmet mitt med 2 tråder fungerer alt perfekt, men når jeg kjører med flere tråder blir den endelige filen full av rot. De første 300-ish ordene er fint sortert, men resten er tilsynelatende helt tilfeldig skrevet. Er det noen som vet hva dette skyldes?
[Reply]
Jonny Reply:
May 15th, 2012 at 16:01
Vanskelig å si uten å vite noe om hvordan du gjør ting. Tips: legg inn utskrift hver gang sort()-metoden og merge()-metoden blir kalt, med hvilke indekser metodene jobber med ift. hoved-array’en.
[Reply]
Martin Reply:
May 15th, 2012 at 17:26
Hvis maintråden ikke venter på de andre trådene, er det mulig at tråden(e) som hadde ansvaret for de 300-ish første ordene hadde gjort seg ferdig, men de andre trådene hadde ikke rukket å komme så langt.
[Reply]
Jeg har et problem som ser ut til å være nokså vanskelig for meg å løse. Programmet mitt fungerer med 128 tråder når jeg skal sortere, merge og skrive til fil, men dette gjelder kun for testfilen names.txt . Historien er en litt annen når jeg skal gjøre det med sowpods.txt.. Jeg mistenker at det kan ha noe med at trådene begynner å gå litt i veien for hverandre fordi filen er større..Men ser ikke helt hvorfor..Metoden som legger ferdigsorterte arrayer inn i en tabell er synchronized og den som tar ut arrayer for merging er også synchronized, så trådene skal jo ikke kunne manipulere data samtidig? Er forvirret…
[Reply]
Chris Reply:
May 15th, 2012 at 19:48
Mitt tips er å bruke en så enkel sorteringsalgoritme som mulig, da minker du rom for feil. Bruker selv insertion som er relativt enkel å feilsøke på.
Se også gjennom der du lager trådene og i monitoren at det er helt riktig størrelse på arrayer o.l.
Hadde selv et tilsynelatende stort problem som kokte ned til at det skulle stå “endIndex” istedenfor “endIndex-1″ på størrelsen til en array.
[Reply]
Er det noen som kan forklare denne feilmeldingen:
Exception in thread “Thread-0″ java.lang.ArrayIndexOutOfBoundsException: 5163
Altså array out of bonds på 5163 som vil si hele arrayet.. Hva gjør jeg galt? =/
[Reply]
Martin Reply:
May 15th, 2012 at 22:51
Husk at indekseringen starter på 0, så har du en array som har 5163 elementer, har det siste elementet indeks 5162.
[Reply]
Skal programmet kunne kjøre med kun én tråd?
[Reply]
Stein Gjessing Reply:
May 16th, 2012 at 11:12
Det hadde jo vært fint, men da blir det jo ikke mye fletting. Men jeg tror ikke du får det underkjent hvis den eneste feilen er at det ikke funker med en tråd.
[Reply]
Programmet mitt funker noen ganger, og andre ganger ikke. Har jeg fått en deadlock? Hvordan fikser jeg dette? Hjelp!
[Reply]
Stein Gjessing Reply:
May 16th, 2012 at 11:14
Det er typisk slik som skjer når metoder ikke er synchronized, pluss at ting skjer i forskjellig rekkefølge hver gang. Som vanlig: prøv med utskrifter for å se hva som skjer.
[Reply]
Miriam Reply:
May 16th, 2012 at 11:27
Såvidt jeg kan se er metodene i monitoren synchronized. Og på utskriftene får jeg noen ganger hele, og andre ganger deler av lista (til fil), og det virker som at prosessen stopper opp midt i (til skjerm). Nå bruker jeg bare en monitor. Kan det være problemet?
[Reply]
Stein Gjessing Reply:
May 16th, 2012 at 11:31
En monitor er supert. Men du må programmere den riktig. Prøv å skrive ut hvor mange sorterte array-biter den til enhver tid inneholder. Og så må du jo si wait på riktig måte (og notify) , slik at du venter til det finnes to array-biter du kan flette.
Hovedproblemet mitt ligger nok i at jeg får flettet de to første, men vet ikke hva jeg skal gjøre med den. Har prøvd å sende den tilbake til monitoren, men det er da disse finurlige problemene oppstår. Noen ganger går det helt fint, andre ganger stopper det opp. Står litt fast på hvordan å angripe… Hjelp!?!
[Reply]
Stein Gjessing Reply:
May 16th, 2012 at 12:29
Ja, programmeringen av monitoren i dette tilfellet er nok litt finurlig.
Men uansett hvordan det går, lever en versjon som kompilerer og virker av og til innen kl 14. Send samtidig en epost til retteren din (eventuelt til joshi (ved ifi.uio.no) hvis du ikke vet hvem retteren din er) og forklar problemet, og jobb så vider med å få det til å virke i flere tilfeller
[Reply]
Miriam Reply:
May 16th, 2012 at 12:41
Ok. Tusen takk for hjelpen
[Reply]
Er det noen som ser hvorfor det blir arrayIndexoutofbounds 16 her…(har 16 ord i testfilen..) Vet at indeksen starter på 0 i et array..
public void sort() {
for(int i=0; i< Ord.length; i++) {
System.out.println("i: " + i);
for(int j = i+1; i<Ord.length; j++) {
if (Ord[i].compareTo(Ord[j])<0) {
System.out.println("j: " + j);
String tmp = Ord[i];
Ord[i] = Ord[j];
Ord[j] = tmp;
}
System.out.println("Sortert liste " + Ord[j]);
}
}
}
[Reply]
SS Reply:
May 16th, 2012 at 13:10
Oki glem den forrige, fikset feilen..
[Reply]
Leave a Reply