---

Hej,

Håber virkelig der er en der kan hjælpe mig med at forstå dette:

Jeg tester fire forskellige sorteringsalgoritmer, og kalder en
sorteringsmetode x antal gange vha. en for-løkke og har så taget tiden inden
for-løkken og efter, og dividerer så med antal gange jeg har kaldt
funktionen.Dette for at få en rimelig præcis køretid. Det virkelige
underlige er, at med to af algoritmerne får jeg samme tid ud, om jeg så
sætter antal gennemkørsler til 10.000. For de to andre øges tiden som
forventlig.
Jeg kan med min gode vilje ikke se at det kan være noget i selve sorterings
koden, kan nogle hjælpe....

Tak,

AH

Mit kald ser fx sådan ud:

long tid1 = System.currentTimeMillis();
int antal = 10;
for( int i = 0; i < antal; i++) {
Insertionsort.sort(words); // indsat String[2500]
}
long tid2 = System.currentTimeMillis();
long tid = (tid2-tid1);
System.out.println("Tid : "+tid); // dividerer selv bagefter med antal
gange!

---

AH skrev:

>Jeg kan med min gode vilje ikke se at det kan være noget i selve sorterings
>koden

Prøv med ond vilje. Der er ikke noget i den citerede kode der
antyder hvor problemet ligger.

--
Bertel
http://lundhansen.dk/bertel/   FIDUSO: http://fiduso.dk/

---

"Bertel Lund Hansen" <nospam@lundhansen.dk> skrev i en meddelelse
> Prøv med ond vilje. Der er ikke noget i den citerede kode der
> antyder hvor problemet ligger.
> Bertel

Har lige prøvet med en god omgang ond vilje, men nej....
Koderne ser meget udskyldige ud! Fx:
Bubblesort1 kommer med korrekt køretid ved x antal kald.
Bubblesort2 kommer med samme køretid ved x antal kald.
De ligger i samme mappe, så heller ikke her forskel...

De ser således ud med String[] som argument:

class Bubblesort1 {
public static void sort(String[] number) {
int i,j;
String temp;
int max = number.length-1;
for (i = 0; i <= max; ++i) {
for (j = 0; j < max; ++j) {
if (number[j].compareTo(number[j+1]) > 0) {
temp = number[j];
number[j] = number[j+1];
number[j+1] = temp;
}
}
}
}
}

class Bubblesort2 {
public static void sort(String[] number) {
int i,j;
String temp;
int max = number.length-1;
boolean exchange = true;
for ( ; exchange; --max) {
exchange = false;
for (j = 0; j < max; ++j) {
if (number[j].compareTo(number[j+1]) > 0) {
temp = number[j];
number[j] = number[j+1];
number[j+1] = temp;
exchange = true;
}
}
}
}
}

---

AH skrev

> Har lige prøvet med en god omgang ond vilje, men nej....
> Koderne ser meget udskyldige ud! Fx:
> Bubblesort1 kommer med korrekt køretid ved x antal kald.
> Bubblesort2 kommer med samme køretid ved x antal kald.

Der er sorteringsalgoritmer der har lineær kompleksitet hvis de anvendes på
allerede sorteret data, hvilket ofte kan være ønskværdigt. Ved et hurtig kig
på din Bubblesort2 metode, kan man se, at den yderste løkke kun gennemløbes
en gang hvis data allerede er sorteret, hvilket netop giver en linær
kompleksitet. Den første metode derimod løber igennem begge løkker et fast
antal gange uanset om data er sorteret i forvejen og den har derfor altid
kvadratisk kompleksitet.

Tør man gætte på, at du benytter allerede sorteret data som input?


Mvh,
--
Filip Larsen <filip.larsen@mail.dk>

---

"Filip Larsen" <filip.larsen@mail.dk> skrev i en meddelelse
news:abdefp$icl$1@news.cybercity.dk...
> AH skrev
>
> Tør man gætte på, at du benytter allerede sorteret data som input?
>
>>Mit kald ser fx sådan ud:
>>
>> long tid1 = System.currentTimeMillis();
>> int antal = 10;
>> for( int i = 0; i < antal; i++) {
>> Insertionsort.sort(words); // indsat String[2500]
>> }
>> long tid2 = System.currentTimeMillis();
>> long tid = (tid2-tid1);
>> System.out.println("Tid : "+tid); // dividerer selv bagefter med antal
>> gange!
>
Der sker jo ikke den helt vilde reinitialisering mellem de enlkelte gennemløb


Mvh
Lars

---

Lars Mosegård skrev

> >> for( int i = 0; i < antal; i++) {
> >> Insertionsort.sort(words); // indsat String[2500]
> >> }

> Der sker jo ikke den helt vilde reinitialisering mellem de enlkelte
gennemløb

Næ, det ville sandelig være synd at sige. Jeg havde ikke lige kigget på den
kodesnip, så det er godt der er nogle andre der er vågne her :)


Mvh,
--
Filip Larsen <filip.larsen@mail.dk>

---

"Filip Larsen" <filip.larsen@mail.dk> skrev i en meddelelse
news:abdhr7$ocv$1@news.cybercity.dk...
> Lars Mosegård skrev
>
> > >> for( int i = 0; i < antal; i++) {
> > >> Insertionsort.sort(words); // indsat String[2500]
> > >> }
>
> > Der sker jo ikke den helt vilde reinitialisering mellem de enlkelte
> gennemløb
>
> Næ, det ville sandelig være synd at sige. Jeg havde ikke lige kigget på
den
> kodesnip, så det er godt der er nogle andre der er vågne her :)
>
>
> Mvh,
> --
> Filip Larsen <filip.larsen@mail.dk>
>
>

Under dække af, at det kan være svært at se skoven for træer (!), har jeg
med jeres hjælp endelig set hvor problemet ligger. Tak skal I ha' for
hjælpen.
Men...
hvordan kan jeg nu smartes (og uden at pårvirke min tidsmåling) sørge for,
at String[] word, som ikke i første kald er sorteret!, forbliver usorteret
til kald to og fremdeles?

Måske det også ligger lige for...
På forhånd tak.
Mvh. AH.

---

AH skrev:

>hvordan kan jeg nu smartes (og uden at pårvirke min tidsmåling) sørge for,
>at String[] word, som ikke i første kald er sorteret!, forbliver usorteret
>til kald to og fremdeles?

Lav to arrays, det ene gemmer de oprindelige strenge, og det
andet sorteres. Hver sorteringsrunde starter så med at A1
kopieres til A2.

--
Bertel
http://lundhansen.dk/bertel/   FIDUSO: http://fiduso.dk/

---

"Bertel Lund Hansen" <nospam@lundhansen.dk> wrote in message
news:5qnkdug22t0b6aqs0kfbdp5mkuhlgolt2h@news.telia.dk...
> AH skrev:
>
> >hvordan kan jeg nu smartes (og uden at pårvirke min tidsmåling) sørge
for,
> >at String[] word, som ikke i første kald er sorteret!, forbliver
usorteret
> >til kald to og fremdeles?
>
> Lav to arrays, det ene gemmer de oprindelige strenge, og det
> andet sorteres. Hver sorteringsrunde starter så med at A1
> kopieres til A2.

Og her skal du så selvfølgelig huske IKKE bare at kopiere A2 = A1 - så
refererer de nemlig til samme array og du har samme problem som før.
Brug fx System.arraycopy i stedet.

Hvis din tidsmåling skal være helt retfærdig, skal du jo så udelade den tid
kopieringen tager - fx ved

String[] words;
String[] randomwords = ...;

long totaltid=0;
for(int i = 0; i< count; i++) {
System.arraycopy(randomwords,0,words,0,words.length);
start = System.getCurrentTimeMillis();
sort(words);
total += System.getCurrentTimeMillis()-start;
}

System.out.println("Avg time: " + (total * 1000.0) / count);

Prinicpielt bør du jo også "gøre noget" med words - ellers kunne en meget
optimerende oversætter jo optimere stort set hele programmet væk
Men jeg tror nu ikke der er nogen java-oversættere der er så smarte.
>
> --
> Bertel

Niels Harremoës

---

Niels Ull Harremoës skrev

> Hvis din tidsmåling skal være helt retfærdig, skal du jo så udelade den
tid
> kopieringen tager - fx ved
>
> String[] words;
> String[] randomwords = ...;
>
> long totaltid=0;
> for(int i = 0; i< count; i++) {
> System.arraycopy(randomwords,0,words,0,words.length);
> start = System.getCurrentTimeMillis();
> sort(words);
> total += System.getCurrentTimeMillis()-start;
> }

Problemet ved dette er, at granulariteten af System.currentTimeMillis() ikke
er god nok, hvilket også er grunden til i første omgang at lave sortering i
en løkke. Hvis man føler, at der bruges meget tid på at forberede data til
sortering, så kan man evt. tage tid på dette i en separat løkke, fx. som

long time1 = System.currentTimeMillis();
for (int i = 0; i < samples; i++) {
data = prepareData(i);
sort(data);
}
long time2 = System.currentTimeMillis();
for (int i = 0; i < samples; i++) {
data = prepareData(i);
}
long time3 = System.currentTimeMillis();
double sortTime = ((time2-time1)-(time3-time2))/(double)samples;

hvor prepareData fx. så enten kopierer et array eller laver et sæt
tilfældige data baseret på parameteren i, eller hvad der nu er relevant.


Mvh,
--
Filip Larsen <filip.larsen@mail.dk>