Dele opp et array i subarray + et problem til

[Benbjo]

Jeg har et lite problem. Jeg har et stort array med int verdier. Dette arrayet ønsker jeg å dele opp i mindre arrayer der disse arrayene tilsammen inneholder alle de verdiene det store hadde.

 

Lite eksempel:

array0[5] inneholder (1,2,3,4,5). Ønsker å dele dette opp i fem andre arrays

array1[1], array2[1] osv osv array1 inneholder 1, array2 inneholder 2 osv.

 

Hvordan gjør jeg dette lettes mulig?

 

Annet spørmål: Har jeg lov til å ha et array som inneholder arrays?

Hvis jeg f.eks vil ha et array som inneholder array1 og array2. Er dette mulig?

Får feil når jeg prøver å gjøre dette.

[Generic]

Pøve å del dei inn litt bedre

[pgdx]

int[][] array = new int[10][10] vil gi deg et 10x10 array av heltall. Arrays er immutable, så det blir uansett en O(n)-operasjon. Har du sett på List<Integer>?

[Benbjo]

Hva mener du pgdx? Det svarte ikke akkurat på spørsmålene mine med mindre jeg missforstod noe.

 

Mitt eksempel var bare et enkelt eksempel. I mitt program har jeg et array på flere tusen tall som skal deles opp i flere arrays med mindre tall i.

 

Så ønsker jeg å putte inn disse arrayene jeg får inn i et nytt array. Altså et array med arrayer.

Så array[0] inneholder et array som inneholder heltall.

[gunnard]

Som pgdx sier kan du lage såkalte flerdimensjonale arrayer. Tenk på en en-dimensjonal array, altså det du snakker om, som en liste med elementer (en vektor hvis du er vant til det begrepet). Denne lages ved: int[] arraynavn = new int[elements];

En to-dimensjonal array er den naturlige utvidelsen av dette, som blir et rutenett av elementer (en matrise hvis du har hatt litt matematikk). Du kan tenke på dette som et regneark for eksempel i Excel. Det høres ut som det er dette du er ute etter, dette vil bli en array av array-objekter. Teknisk er en slik to-dimensjonal array bare en vanlig liste, men liste-elementene er ikke tall som i det en-dimensjonale tilfellet, men liste-elementene er her pekere til en-dimensjonale arrayer. Disse lages, som pgdx sier ved: int[][] arraynavn = new int[rowElements][columElements];

Du kan forøvrig ha arrayer der liste-elementene er to-dimensjonale arrayer, disse er da tre-dimensjonale arrayer, og så videre oppover.

 

Hvis du vil ha en effektiv løsning til ditt problem - og du ikke nå for sett hvordan du selv klarer å gjøre det - er det best om du skriver litt mer hva du er ute etter å gjøre. Hva er kriteriene for oppdelingen i mindre arrayer? Skal de mindre arrayene være av samme størrelse, inneholde tall i et gitt intervall? Hvordan er den arrayen du i utgangspunktet har bygd opp? Er det for eksempel sortert, kan inneholder duplikater som skal fjernes?

[Benbjo]

Vet om todimensjonelle arrayer. Skjønner ikke hva det har med det jeg spør om å gjøre.

 

Si at jeg har en array med 8000 forskjellige tall. Dette arrayet skal deles opp i 8 arrayer med 1000 tall i hver. Hensikten med dette er at jeg skal sortere disse mindre arrayene hver for seg (samtidig med tråder). Dette tar kortere tid enn å sortere det store arrayet.

 

Deretter hadde jeg tenkt til å putte de ferdig sorterte arrayene inn i et nytt array. Når det er to ferdigsorterte arrayer i det nye arrayet vil en metode kalles slik at disse arrayene flettes sammen. Til slutt får man altså et ferdigsortert array med 8000 heltall.

 

Det er kanskje en bedre måte å gjøre det på enn det jeg ahr tenkt? Kravet er uansett bare å bruke tråder.

[gunnard]

Dette minner ekstremt om mergesort, men dette visste du vel også? Men jeg vil regne med at den klassiske mergesort-algoritmen med thread-exploiting gir bedre kjøretid i spesialtilfeller og i gjennomsnitt, din algoritme vil jo ha O(N^2), mens mergesort har jo O(N*log(N)). Uansett, siden det er snakk om en primær datatype her gir jo quicksort bedre gjennomsnittlig kjøretid (i Java).

[pgdx]

Vet om todimensjonelle arrayer. Skjønner ikke hva det har med det jeg spør om å gjøre.

Da skjønner du ikke todimensjonale array.

[steingrim]

Vet om todimensjonelle arrayer. Skjønner ikke hva det har med det jeg spør om å gjøre.

Nuvel...

 

Si at jeg har en array med 8000 forskjellige tall. Dette arrayet skal deles opp i 8 arrayer med 1000 tall i hver.

new int[8][1000]

[Benbjo]

Det vil ikke fungere.

Altså: Jeg leser en skog med tall fra en fil. I den filen er det gitt hvor mange tråder jeg skal lage. Skal altså dele opp disse tallene i en mengde array. Disse arrayene skal en og en sorteres ved hjelp av tråder.

 

Deretter når de er ferdig sortert sendes de til en "buffer" klasse som tar vare på arrayene som er sortert i et annet array. Når det er to elementer i dette arrayet skal en ny tråd opprettes som fletter de to elementene (som er to sorterte arrayer) sammen.

 

EDIT: Skjønner hva du mener med to-dimensjonale arrays nå, men missforstod hva du mente. Men slik jeg har tenkt vil det ikke virke.

Endret 4. mai 2008 av Benbjo

[steingrim]

EDIT: Skjønner hva du mener med to-dimensjonale arrays nå, men missforstod hva du mente. Men slik jeg har tenkt vil det ikke virke.

Tenk annerledes

 

Hver tråd får sin array i det todimensjonale arrayet. Hvorfor fungerer ikke det?

[Benbjo]

Jo ok, ser at det fungerer nå. Måtte bare tenke litt og modifisere litt kode. Blir ikke helt som jeg hadde tenkt da, så må fikse litt senere også. Har ikke brukt to-dimensjonale arrays på denne måten før.

 

Ok, nå har jeg altså lest inn en fil som har 8000 heltall. Så har en array usortert[8][1001] (grunnen til at det er 1001 plasser er for å sikre mot feil hvis antall heltall er oddetall)

 

Den som nå skal skje er at jeg skal sortere usortert fra 0-7. Dette skal gjøres i en egen klasse som utvider Thread. Sorteringen skal skje i run() metoden. Ergo må jeg ha 8 tråder, dvs kjøre run 8 ganger. Problemet er at run() må startes via start() og denne kan ikke ta imot parametere. Hvordan skal jeg løse dette?

[steingrim]

Problemet er at run() må startes via start() og denne kan ikke ta imot parametere. Hvordan skal jeg løse dette?

Siden klassen din arver fra Thread kan du jo bare gi de til objektet på en annen måte. Lag noen set'ere for parametere eller gi de til konstruktøren.

[Benbjo]

Kom til slutt på at jeg kunne lage et objekt av klassen som skal sortere arrayet hver gang jeg skulle lage en ny tråd så sende med den delen av arrayet jeg har laget tidligere som parameter og lage en konstruktør.

 

Takk uansett

[gunnard]

Bra du har fått det til

 

Forresten, beklager helt feil kjøringstidsmål i posten min over dersom du i tillegg til trådutnyttelsen kjører en mer raffinert sorteringsalgoritme som radix sort etterpå.. (ser det har kommet et annet emne som gjør dette) Da er selvsagt algoritmen din O(N) (ved radix sort)..

[Benbjo]

Er ikke så avansert i java enda. Man kan i oppgaven fritt velge sorteringsmetode. Foreløpig kjører jeg med innstikkssortering. Selvsagt mye treigere enn nevnte radixsort, samt quicksort og mergesort.

 

Dog sliter jeg med heap space error hvis jeg prøver å sortere 6.4 mill tall. Satser på at jeg finner ut av hvorfor Ellers virker alt greit med den sorteringsmetoden jeg bruker.

[gunnard]

Ok Da er det O(N^2) hvis du lurte..

 

Den heap space erroren skyldes jo bare at JVM ikke blir tillatt / ikke ønsker (er kanskje noen innstillinger man kan endre?) å tildele programmet mer minneplass.. Grensen for hvor mange tall ditt program kan sortere avhenger av om du lager kopier av tallene eller ikke, men et sted vil grensen gå uansett.

[Benbjo]

Ja meget mulig. Hørte noen rykter om det får se om jeg får fikset på det i morgen.

[gunnard]

Hvis du fortsatt får den feilen kan du prøve å bruke -Xmx opsjonen når du kjører programmet. Den setter den maksimale grensen av minne JVM kan bruke. Som standard står den på 64MB, hos meg kan jeg sette den opp til like over 1610MB. (bruk for eksempel java -Xmx256m -jar MyJarFile.jar)