Skjønner meg ikke på while løkken.

[lassejl]

Hallo, sitter her med et helt sikkert meget enkelt problem men jeg klarer bare ikke se det. Det som skal skje er at noen tråder skal sortere int verdier, deretter skal arrayene som er resultatet av disse sorteringene flettes sammen. Har fikset dette lette med LinkedList, men tenkte jeg skulle prøve å få det til å gå raskere ved å unngå en slik liste og i stedet for å legge 2 arrays i en buffer for deretter at en tråd skal merge de så ville jeg prøve på at den første tråden som er ferdig med å sortere skal legge til et array og den neste skal da hente ut det arrayet og merge med sitt eget array. Og dette skal foregå helt til merginga er ferdig, det vil si da arrayet i bufferet er like langt som alle arrayene i trådene var tilsammen.

 

Tråden ser slik ut:

Der sb er pekeren til bufferet og values er arrayet den har fått satt før run metoden er kalt.

public void run() {
	int[] temp = RadixSort.sort(values, 16);
	if (!sb.canMerge()) { 
		sb.addArray(temp);
	} else {		
		while (sb.canMerge()) {
			sb.addArray(merge(sb.getArray(), temp));
		}
	}
}
}

Merge metoden tar bare inn 2 arrays og stokker de.

 

Bufferet ser slikt ut:

class SortBuffer {

int[] saved;
int totalLength;

SortBuffer(int i) {
	totalLength = i;
}

public int[] getArray() {
	int[] temp = saved;
	saved = null;
	return temp;
}

public void addArray(int[] a) {
	saved = a;
}

public boolean canMerge() {
	if (saved != null && saved.length == totalLength) {
		return false;
	}
	else {
		return saved != null ? true : false;
	}
}
}

 

Programmet henger seg i while løkken i tråden, av en eller annen grunn returnerer canMerge() alltid true.

 

Håper noen har svar, eventuellt en indikator på om dette vil gå kjappere enn med LinkedList, hvis ikke kan jeg jo bare gi opp hele greia med en gang ><.

[pgdx]

canMerge() returnerer tydeligvis false hver gang, i.e. saved == null.

 

Bytt ut canMerge med denne, som skriver ut saved, og som skal gi en indikasjon på hvor ofte den blir kalt, og hva saved faktisk er.

 

	public boolean canMerge() {
	System.out.println(getClass().getCanonicalName() + ".canMerge(): saved = " + saved + " (" + totalLength + ")");
	if (saved != null && saved.length == totalLength) {
		return false;
	}
	else {
		return saved != null;
	}
}

Ps: return saved!=null trenger ingen ternary expr.

[gunnard]

Håper noen har svar, eventuellt en indikator på om dette vil gå kjappere enn med LinkedList, hvis ikke kan jeg jo bare gi opp hele greia med en gang ><.

Fletting av to sorterte LinkedList vil ta O(N) kjøretid (dersom man husker på hvilket listeobjekt man sist sammenlignet i hver av listene og når et listeobjekts element er lagt til i den flettede listen/arrayet så oppdateres pekern fra dette listeobjektet til listeobjektets neste-peker). Fletting av to sorterte arrayer vil også ta O(N) kjøretid. I praksis vil det kanskje være noe forskjell, iallfall hvis du lager lister av arrayene for så å flette dem. Listeobjektene vil forøvrig ta mer plass i minnet.

 

Uansett, er god trening å implementere dette også, så hadde jeg vært deg ville jeg gjort det for treningens skyld

 

Vet ikke om det er meninga, men dersom for eksempel totalLength = 64 og disse saved-arrayene er på 16 vil først run()-kall lagre arrayen i sb-objektet, mens andre run()-kall gå inn i while-løkka, flette den første saved-arrayen med denne nye 16-arrayen, men siden sb.canMerge() fortsatt gir true (arrayene saved har nå lengde 32), vil den flette den flettede 32-arrayene i sb-objektet med den samme 16-arrayen temp som allerede er flettet inn, for så å få en 48-array, som igjen (sb.canMerge() fortsatt true) vil bli flettet med den samme 16-arrayen for å få en 64-array, nå vil sb.canMerge() gi false. Du vil altså få flettet den første 16-arrayen med tre identiske 16-arrayer (fra det andre run()-kallet).

 

Dersom nå for eksempel totalLength = 60 vil aldri saved.length == totalLength dersom for eksempel både den første og andre run()-kallet er med arrayen er av lengde 16 (vil merge til 32, til 48, til 64, til 80 osv..). Så hvis jeg kan gjette på problemet ditt er det slik at du for eksempel får inn et 30-array, deler det i åtte til 4,4,4,4,4,4,3,3, en array med lengde 3 blir ferdig, denne legges i sb-objektet, en array med lengde 4 blir ferdig og flettes til 7, til 11, til 15, til 19, til 23, til 27, til 31, til 35 osv. Testen saved.length == totalLength er alltid false. Mest sannsynlig, med mindre problemet ditt er annerledes enn jeg har oppfattet, vil du bare fjerne testen ( while (sb.canMerge()) ). Dette fjerner problemet med flere flettinger av samme array (hvis dette da ikke var ønskelig) og problemet med at saved.length == totalLength alltid kan gi false. Dersom flere flettinger av samme array mot formodning er ønskelig kan testen saved.length == totalLength byttes til saved.length >= totalLength - ikke at jeg ser hvilken nytte slik fler-fletting har

[lassejl]

Ja, lol ser jo litt av problemet nå, tar jo alltid med den arrayen som ligger i tråden.

 

Men jeg kan jo ikke fjerne while løkken, for om jeg har 4 tråder vil jo bare flettingen skje 2 ganger og jeg sitter igjen med 2 arrays da jeg burde ha ett.

 

Fikk fikset det, gjorde bare om løkken til dette:

 

while (sb.canMerge()) {
temp = merge(sb.getArray(), temp);
sb.addArray(temp);
}

 

 

Meget skuffende resultat tho, beste er 0.078sec på 1mill tall, samme som før. Kjørte på 1 tråd med dual core cpu. Lurer litt på hvorfor 1 tråd går fortere enn 2 (0.109sec) på dual core men, er det slik at main metoden opptar en tråd eller noe?

 

Anyway, takk for svar og lol med den ternary greia, har liksom aldri brukt det før og tenkte at nå skulle jeg slå til med en slik enn men nei .

[steingrim]

Lurer litt på hvorfor 1 tråd går fortere enn 2 (0.109sec) på dual core men, er det slik at main metoden opptar en tråd eller noe?

Hvis datamengden er for liten, problemet ikke egner seg for parallellisering eller hvis implementasjonen ikke er helt korrekt vil man ofte finne at en tråd er bedre enn to. Er datamengden for liten vil overhead for kontekst-svitsjing bli større en gevinsten.

 

Trådprogrammering er vanskelig. Ikke la noen lure deg til å tro noe annet!

[gunnard]

Meget skuffende resultat tho, beste er 0.078sec på 1mill tall, samme som før. Kjørte på 1 tråd med dual core cpu. Lurer litt på hvorfor 1 tråd går fortere enn 2 (0.109sec) på dual core men, er det slik at main metoden opptar en tråd eller noe?

Main-tråden, den tråden JVM lager når den kaller på din main-metoden, er også en tråd ja. Så dersom du lager da to nye tråder vil programmet ditt ha totalt 3 tråder (egentlig kjører også GC på egen tråd, kanskje også flere). Poenget er imidlertid at prosessorer har tradisjonelt sett blitt designet for å takle og kjøre flere tråder parallelt (teknisk er det bare litt fra en tråd så litt fra annen tråd så litt til kanskje på den først, fordelingen her er det OSet som tar seg av). Siden main-tråden ikke gjør noe, eller bare ekstremt lite, for eksempel at den bare står og venter, vil ikke denne "oppta" en kjerne, for det er ingen tråder som har enerett på en kjerne. Omvendt er det derimot (så vidt jeg vet iallfall), en tråd vil bare kjøre på en kjerne.

 

Det man må passe seg for er at det ikke er mange flere tråder som ønsker å bruke all kapasitet av en kjerne enn man har kjerner i systemet. Altså, hvis du har en dobbelkjerner, er det OK å lage to tråder som sorterer, selv om det teknisk er flere tråder som JVM kjører, men det er dumt å lage flere beregningstråder enn dette. Likevel, siden prosessor-forbedringene før flerkjerneteknologien ble en realitet for mannen på gata brydde seg om å optimalisere bruk av flere tråder på en kjerne, vil man ikke merke noen betydelig forskjell ved for eksempel å lage tre beregningstråder. Men ved å gå opp til 10 er det merkbart, og med 100 blir det bare idioti. Jeg lagde et tilsvarende lite testprogram som viser dette:

 

 

Intel Core Duo T2400 @ 1.83GHz , 512 MB memory

 

(standard, -Xmx64m)

Sorting of 5000000 integer elements was successfully completed in 1.375 seconds using a single thread.

Sorting of 5000000 integer elements was successfully completed in 1.359 seconds using a single thread.

Sorting of 5000000 integer elements was successfully completed in 1.359 seconds using a single thread.

 

Sorting of 5000000 integer elements was successfully completed in 0.844 seconds using 2 threads.

Sorting of 5000000 integer elements was successfully completed in 0.875 seconds using 2 threads.

Sorting of 5000000 integer elements was successfully completed in 0.844 seconds using 2 threads.

 

Sorting of 5000000 integer elements was successfully completed in 0.891 seconds using 3 threads.

Sorting of 5000000 integer elements was successfully completed in 0.875 seconds using 3 threads.

Sorting of 5000000 integer elements was successfully completed in 0.875 seconds using 3 threads.

 

Sorting of 5000000 integer elements was successfully completed in 1.125 seconds using 10 threads.

Sorting of 5000000 integer elements was successfully completed in 1.156 seconds using 10 threads.

Sorting of 5000000 integer elements was successfully completed in 1.078 seconds using 10 threads.

 

Sorting of 5000000 integer elements was successfully completed in 4.906 seconds using 100 threads.

Sorting of 5000000 integer elements was successfully completed in 4.844 seconds using 100 threads.

Sorting of 5000000 integer elements was successfully completed in 5.094 seconds using 100 threads.

 

(with the option -Xmx128m)

Sorting of 10000000 integer elements was successfully completed in 2.844 seconds using a single thread.

Sorting of 10000000 integer elements was successfully completed in 2.843 seconds using a single thread.

Sorting of 10000000 integer elements was successfully completed in 2.89 seconds using a single thread.

 

Sorting of 10000000 integer elements was successfully completed in 1.719 seconds using 2 threads.

Sorting of 10000000 integer elements was successfully completed in 1.735 seconds using 2 threads.

Sorting of 10000000 integer elements was successfully completed in 1.734 seconds using 2 threads.

 

Sorting of 10000000 integer elements was successfully completed in 1.75 seconds using 3 threads.

Sorting of 10000000 integer elements was successfully completed in 1.812 seconds using 3 threads.

Sorting of 10000000 integer elements was successfully completed in 1.75 seconds using 3 threads.

 

Sorting of 10000000 integer elements was successfully completed in 2.234 seconds using 10 threads.

Sorting of 10000000 integer elements was successfully completed in 2.265 seconds using 10 threads.

Sorting of 10000000 integer elements was successfully completed in 2.266 seconds using 10 threads.

 

Sorting of 10000000 integer elements was successfully completed in 9.547 seconds using 100 threads.

Sorting of 10000000 integer elements was successfully completed in 9.359 seconds using 100 threads.

Sorting of 10000000 integer elements was successfully completed in 9.266 seconds using 100 threads.

 

 

Forresten, dersom du prøver å sortere litt flere tall og finner at programmet ditt ikke kjører raskere med to tråder på en dobbelkjerne enn med en tråd på samme prosessor er det trolig noe galt. Det kan for eksempel være at du har synkronisert sorteringsmetoden (da kan bare en sorteringsmetode kjøre om gangen).

[lassejl]

Fant ut hva jeg hadde gjordt galt, ganske dumt faktisk. Det som skulle skje var at alle trådene skulle vente til alt var ferdig og jeg brukte join() til dette. Men jeg tenkte feil og gjorde dette i for løkken som lagde alle trådene.

Slik:

for (int i = 0; i < values.length; i++) {
		Sorter s = new Sorter(values[i], this.sb);
		s.start();
		try {
			s.join();
		} catch (Exception e) {}
	}

Da vil jo den første tråden vente med å starte til neste er ferdig osv . Fikset nå da, ganske stor forbedring på hastigheten.

 

Btw, noen tips om hvordan ting kan gå fortest mulig i java? Hørt at final og static metoder skal hjelpe, også å bruke decreament på for løkker istedet for increament (--/++), men noen som har noen flere triks?

[Blue-water]

Lykke til meg konkuransen lasse, alle håper du vinner. (selv om vi vet du taper.... haha)

 

<3

[lassejl]

Å jasså? Har ikke hørt om noen som sorterer raskere enn meg enda

 

6.4 millioner tall på 380-400ms på en 8 kjerners pc er vel ikke så dårlig er det vel?

 

Regner med du er med i konkuransen selv siden du nevner det så kan jo i meg ditt resultat?

Endret 18. mai 2008 av lassejl