Timsort Bachelor 2015

package com.google.caliper.timsort; import com.google.caliper.timsort.SortingAlgorithms; import java.util.Random; import com.google.caliper.BeforeExperiment; import com.google.caliper.Benchmark; import com.google.caliper.Param;

public final class TimsortBenchmark {        Random rand = new Random(0607);        Random randNum = new Random(1991);        Integer[] temp;        Integer[] tab;        Integer[] sortingTab;

       @Param({"64"}) private int length;        @Param({"2", "5", "8"}) private int probability;

       @BeforeExperiment void setUp() {                tab = new Integer[length];                tab[0] = rand.nextInt((2147483645) + 1) + 0;                  for(int i = 1; i < tab.length; i++){                        if ((randNum.nextInt((10 - 1) + 1) + 1) > (10 - probability) ) {                                tab[i] = rand.nextInt((2147483646 - tab[i-1]) + 1) + tab[i - 1];                        }                        else {                                tab[i] = rand.nextInt((tab[i-1] + 0) + 1) + 0;                        }                }                sortingTab = new Integer[tab.length];

               /* tab = new Integer[length];                tab[0] = 1;                for(int i = 1; i < tab.length; i++){                        //tab[i] = tab[i - 1] - (100 - probability) + (rand.nextInt(100 - 1 + 1) + 1);                        tab[i] = rand.nextInt();                }                sortingTab = new Integer[tab.length]; */        }

        @Benchmark void binarySort(int reps) {                for (int i = 0; i < reps; i++) {                        System.arraycopy(tab, 0, sortingTab, 0, tab.length);                        SortingAlgorithms.binarySort(sortingTab);                }        }

       @Benchmark void insertSort(int reps){ //throws NotSortedException {                for (int i = 0; i < reps; i++) {                        temp = new Integer[tab.length * 2];                        System.arraycopy(tab, 0, sortingTab, 0, tab.length);                        SortingAlgorithms.insertSort(sortingTab, temp);                }        }

package com.google.caliper.timsort; public class SortingAlgorithms {

    //textbook    public void mergeSort(Integer[] array, int start,int end){        if(start < end){                int mid = (start + end) / 2;                mergeSort(array,start, mid);                mergeSort(array, mid + 1, end);                merge(array, start, end);        }        }

       public void regMergeSort(Integer[] array, int start,int end){

               if(start < end){                        int mid = (start + end) / 2;                        mergeSort(array,start, mid);                        mergeSort(array, mid + 1, end);                        regMerge(array, start, end);                }

       }

       public static boolean isSorted(Integer[] array){                 for(int i = 0; i < array.length - 1; i++){         if ( array[i] > array[i+1]){         return false;         }         }                         return true;                }

       private void merge(Integer[] input, int start,int r){                int mid = (start + r) / 2;                int i1 = 0;                int i2 = start;                int i3 = mid + 1;

               Integer[] temp = new Integer[r - start + 1];

               if(input[mid] < input[r]){                        while(i2 <= mid){                                if(input[i2] < input[i3])                                temp[i1++] = input[i2++];                                else                                        temp[i1++] = input[i3++];                        }

                       while ( i3 <= r )                        temp[i1++] = input[i3++];                }

               else                {                        while(i3 <= r){                                if(input[i2] < input[i3])                                temp[i1++] = input[i2++];                                else                                        temp[i1++] = input[i3++];                        }

                       while ( i2 <= mid )                        temp[i1++] = input[i2++];                }

                for ( int i = start; i <= r; i++ )                        input[i] = temp[i-start];

       }

       private void regMerge(Integer[] array, int start,int end){                int mid = (start + end) / 2;                int i1 = 0;                int i2 = start;                int i3 = mid + 1;

               Integer[] temp = new Integer[end - start + 1];

                while ( i2 <= mid && i3 <= end )                        if ( array[i2] < array[i3] )                            temp[i1++] = array[i2++];                        else                            temp[i1++] = array[i3++];

                   while ( i2 <= mid )                        temp[i1++] = array[i2++];

                   while ( i3 <= end )                        temp[i1++] = array[i3++];

                for ( int i = start; i <= end; i++ )                        array[i] = temp[i-start];

       }

       //My implementation of timsort        public static Integer[] insertSort(Integer[] list, Integer[] temp){                int length = list.length - 1;                int left = length;                int right = length;                int lo, hi, m, current, n;                temp[left] = list[0];

               for(int i = 1; i < length; i++){                                              if(list[i] >= temp[right]){                                right = right + 1;                                temp[right] = list[i];                                continue;                        }

                       if(list[i] <= temp[left]){                                left = left - 1;                                temp[left] = list[i];                                continue;                        }                                              

                        lo = left;                         hi = right;

                        m = 0;                         while(lo < hi){                                // m = (lo + hi) >>> 1;                           m = lo + ((hi - lo) / 2 );

                                if(list[i] < temp[m])                                         hi = m;                                 else lo = m + 1;                         }

                       current = lo - 1;

                       if(right - current < current - left){

                               /*                                int j = right + 1;                                while(j > current + 1){                                        temp[j] = temp[j - 1];                                        j--;                                }                                right = right + 1;                                temp[current + 1] = list[i];

                               */                                                    right++;                            n = right - current;                            /*                            switch(n ) {                                 case 2:  temp[current + 3] = temp[current + 2];                                 case 1:  temp[current + 2] = temp[current + 1];                                 break;                                    default: System.arraycopy(temp, current + 1, temp, current + 2, n  );

                                }                                                    */                                System.arraycopy(temp, current + 1, temp, current + 2, n  );                                temp[current + 1] = list[i];                                          }

                       else {

                               /*                                int j = left - 1;                                while(j < current){                                        temp[j] = temp[j + 1];                                        j++;                                }                                left = left - 1;                                temp[current] = list[i];

                               */

                                n = current - (left - 1);                                 /*                                 switch(n ) {                                 case 2:  temp[current - 2] = temp[current - 1];                                 case 1:  temp[current - 1] = temp[current];                                 break;                                    default: System.arraycopy(temp, left, temp, left - 1, n  );

                                }                                 */                                 System.arraycopy(temp, left, temp, left - 1, n  );                                left--;                                temp[current] = list[i];

                       }

               }

               System.arraycopy(temp, left, list, 0, length  );        /*                    for(int i = 0; i < length; i++){                        list[i] = temp[left];                        left = left + 1;                }

               */                return list;

       }

       public static Integer[] binarySort(Integer[] a) {

               int lo = 0;                int start = lo;                int hi = a.length; if (start == lo) start++; for ( ; start < hi; start++) { Integer pivot = a[start];

// Set left (and right) to the index where a[start] (pivot) belongs int left = lo; int right = start; assert left <= right; /* * Invariants: *   pivot >= all in [lo, left). *   pivot <  all in [right, start). */ while (left < right) { int mid = (left + right) >>> 1; if (pivot < a[mid]) right = mid; else left = mid + 1; }

/* * The invariants still hold: pivot >= all in [lo, left) and * pivot < all in [left, start), so pivot belongs at left.  Note * that if there are elements equal to pivot, left points to the * first slot after them -- that's why this sort is stable. * Slide elements over to make room to make room for pivot. */ int n = start - left;  // The number of elements to move // Switch is just an optimization for arraycopy in default case

/* for(int j = start; j >= left + 1; j--)   {      a[j] = a[j - 1];   }  

*/ switch(n) { case 2:  a[left + 2] = a[left + 1]; case 1:  a[left + 1] = a[left]; break; default: System.arraycopy(a, left, a, left + 1, n); }

a[left] = pivot; } return a; }

       public void kNearSort(Integer[] a) {

               int lo = 0;                int start = lo;                int hi = a.length;                int k = 10;                int remainingMoves = k; if (start == lo) start++; for ( ; start < hi; start++) { Integer pivot = a[start];

int left = lo; int right = start; assert left <= right;

while (left < right) { int mid = (left + right) >>> 1; if (pivot < a[mid]) right = mid; else left = mid + 1; }

int n = start - left;  // The number of elements to move remainingMoves = remainingMoves - n;

if(remainingMoves < 1)        return;

remainingMoves += k;

switch(n) { case 2:  a[left + 2] = a[left + 1]; case 1:  a[left + 1] = a[left]; break; default: System.arraycopy(a, left, a, left + 1, n); }

a[left] = pivot; }

}

[Mangler bilder]

Forbedring av Flettesortering

Flettesortering er en del av timsort, så viss vi kan gjøre noen forbedringer på flettesorteringen, så kan vi også forbedre timsort.

Den første forbedringen i flettesorteringen, som vi fikk i oppdrag å implementere ligger i flette metoden, den bruker da en while løkke, som gjør to tester for hver iterasjon:

Den tester hele tiden på om det er gjenværende elementer i begge tabellene, som vi bruker til fletting, altså at ingen av tabellene er tomme. Denne testen kjøres da for hvert element som blir flettet, så lenge begge tabellene inneholder elementer.

Det finnes en måte, som gjør at vi klarer oss med en test, men vi må vite hvilken tabell, som går tom for elementer først. Dette kan vi finne ut av ved å sammenligne det siste elementet fra hver tabell, tabellen med det minste siste elementet, blir tømt først. Når vi vet hvilken tabell, som blir tømt først trenger vi bare å teste på om den tabellen inneholder elementer.

Vi får da følgende kode:

Valget av en microbenchmarking verktøy sto mellom Google Caliper og VisualVM. I begynnelsen måtte vi finne ut hvilken av de to vi ville bruke, men siden vi ikke hadde noe som helst erfaring med microbenchmarking verktøy og veilederen anbefalte Google Caliper, virket det som et fornuftig valg.

I begynnelsen trodde vi oppsettet av Caliper skulle være enkelt. På nedlastingssiden var det en JAR fil vi kunne laste ned (caliper-1.0-beta-1-all.jar), og uten å faktisk prøve verktøyet antok vi at å legge JAR filen i build-path’en til prosjektet vårt var alt som skulle til. Det var det desverre ikke, og i tillegg leste vi mange innlegg på internett (stackoverflow, etc) hvor folk rapporterte at versjonen vi hadde av caliper ikke funket på windows maskiner.

En veldig stor hindring for oss når det kom til caliper er at vi har alltid vært veldig avhengig av andre folk som har like problemer som oss, som kanskje har løst problemet sitt, eller vist hvilken retning de tok for å løse det. Dette var ikke like lett med caliper på grunn av at det er ikke så mange som bruker det (ser det ut som) og finne hjelp online er ikke lett.

Etter vi fant ut at å legge til JAR filen i build path ikke funket, og hvis det hadde funket var det stor sjanse for at Windows maskinene (som vi bruker) ikke klarer å kjøre det, måtte vi laste ned kilde kode fra GIT repository fra Caliper sin side. På siden har også hoved utviklereren, Gregory Kick, en tutorial video på youtube som går gjennom alle stegene for å lage en fungerende benchmark (https://www.youtube.com/watch?t=129&v=Rbx0HUCnF24). Problemet med denne videoen er for det meste at det er Mac Gregory bruker, og vi måtte finne en måte å oversette terminal kommandoene han bruker i videoen til eclipse.

Det første vi begynte med var å laste ned kilde-koden til caliper (https://code.google.com/p/caliper/source/checkout). Etter det er gjort har man en mappe som heter caliper, og en mappe inni den mappen som også heter caliper. Det er den andre Caliper mappen vi har lyst på. Denne importerer vi i eclipse som et eksisterende Maven prosjekt. Pek til mappen, og eclipse vil finne POM.xml filen inni og gjør alt for deg. Etter det så viser Gregory på sin video at han skriver “mvn clean install”. Jeg omgjorde dette til “Run As -> Maven Clean” og deretter “Run As -> Maven Install” på eclipse. Dette funket på hjemme PCen min, men har ikke funket på mange andre Windows PCer. Så langt har vi bare klart å installere caliper på 2 Windows PCer, og en linux PC (ved hjelp av terminal kommandoene).

Etter noe tid vil Caliper installeres på maskinen, og du kan finne installasjonen i %User%/.m2/, hvor maven har alle sine installasjoner. Nå er Caliper installert og klar til bruk.

Når vi lagde vår første benchmark brukte vi også videoen til Gregory Kick som eksempel, og vi kom frem til noe etter kort tid. Den første benchmark koden så ut som dette:

package com.google.caliper.timsort;

import com.google.caliper.timsort.SortingAlgorithms;

import java.util.Random;

import com.google.caliper.AfterExperiment;

import com.google.caliper.BeforeExperiment;

import com.google.caliper.Benchmark;

public final class TimsortBenchmark {

Random rand = new Random(0607);

Integer[] tab = new Integer[1002];

@BeforeExperiment void setUp() {

    System.gc();

    tab[0] = 1;

    for(int i = 1; i < tab.length; i++){

        tab[i] = tab[i - 1] - 20 + (rand.nextInt(100 - 1 + 1) + 1);

    }

}

@AfterExperiment void tearDown(){

    tab = null;

}

@Benchmark void binarySort(int reps) {

    Integer[] binaryTab = tab;

    for (int i = 0; i < reps; i++) {

        SortingAlgorithms.binarySort(binaryTab);

    }

}

@Benchmark void insertSort(int reps) {

    Integer[] insertTab = tab;

    for (int i = 0; i < reps; i++) {

        SortingAlgorithms.insertSort(insertTab);

    }

}

}

Som man kan se i tearDown funksjonen, prøver vi å gjøre tabellen til null, og har en Garbage Collection som blir kjørt i begynnelsen av hver setUp. Dette gjorde vi fordi vi fikk en feilmelding om at Java sin Garbage Collector ble kjørt under benchmarking av vår implementasjon av insettingsortering. Dette var feil måte å løse problemet på, og løsningen vil du se i neste versjon av benchmark koden.

Vi visste ikke hva, men det var noe som var feil. Om det var selve algoritmen eller bug i Caliper eller benchmark koden visste vi ikke. Vi fant ut i ettertid at det var selve benchmark koden som hadde feil i seg. Vi vet fortsatt ikke nøyaktig hva koden gjorde som var feil, men feilen var at insettingssortering-kode ble rundt 10-15 ganger raskere enn den Timsort bruker, som er en åpenbar feil. Vi så nærmere på noen andre eksempler laget av utviklerene til Caliper, mer nøyaktig eksempelet de har om ArraySort (https://code.google.com/p/caliper/source/browse/examples/src/main/java/examples/ArraySortBenchmark.java) og så at for hver repetisjon så kopierer caliper elementene som skal sorteres i en ny tabell, og sorterer den. Vi tror at feilen vår lå der, og at vår benchmarking tok den samme, sorterte tabellen, og “sorterte” den mange ganger, dermed fikk vi vanvittig raske resultater.

package com.google.caliper.timsort;

import com.google.caliper.timsort.SortingAlgorithms;

import java.util.Random;

import com.google.caliper.BeforeExperiment;

import com.google.caliper.Benchmark;

import com.google.caliper.Param;

public final class TimsortBenchmark {

Random rand = new Random(0607);

Random randNum = new Random(1991);

Integer[] temp;

Integer[] tab;

Integer[] sortingTab;

        @Param({"64", "128", "1280", "12800"}) private int length;

@Param({"2", "5", "8"}) private int probability;

@BeforeExperiment void setUp() {

    tab = new Integer[length];

    tab[0] = rand.nextInt((2147483645) + 1) + 0;

    for(int i = 1; i < tab.length; i++){

        if ((randNum.nextInt((10 - 1) + 1) + 1) > (10 - probability) ) {

            tab[i] = rand.nextInt((2147483646 - tab[i-1]) + 1) + tab[i - 1];

        }

        else {

            tab[i] = rand.nextInt((tab[i-1] + 0) + 1) + 0;

        }

    }

    sortingTab = new Integer[tab.length];

    }

@Benchmark void binarySort(int reps) {

    for (int i = 0; i < reps; i++) {

        System.arraycopy(tab, 0, sortingTab, 0, tab.length);

        SortingAlgorithms.binarySort(sortingTab);

    }

}

@Benchmark void insertSort(int reps){ //throws NotSortedException {

    for (int i = 0; i < reps; i++) {

        System.arraycopy(tab, 0, sortingTab, 0, tab.length);

        SortingAlgorithms.insertSort(sortingTab);

    }

}

@Benchmark void mySort(int reps){ //throws NotSortedException {

    for (int i = 0; i < reps; i++) {

        System.arraycopy(tab, 0, sortingTab, 0, tab.length);

        SortingAlgorithms.mySort(sortingTab);

    }

}

}

Når man tenker på ytelse i algoritmer, tenker man ofte på Big-O notasjon, og beste/verste tilfeller. Når vi nå skal se på forandring av implementasjon på algoritmen, burde den teoretiske ytelsen være den samme, men den praktiske kan forandres.  For å kunne måle skikkelig, må vi måle tid på kjøring av algoritmene mange ganger, med forskjellige data-sett(men samme på begge to selvfølgelig!), og store datasett. Og det må selvfølgelig gjøres på samme maskin, med samme hardware osv for å sammenligne, men bør også sammenligne på flere forskjellige maskiner. Vi bruker primært windows maskiner selv, men det kan være lurt å teste ytelse på linux, da ofte der OSet selv tar mindre ressurser. For java kan vi bruke noe smo heter Java VisualVM som kan lastes ned her.

http://docs.oracle.com/javase/6/docs/technotes/guides/visualvm/

Vi fikk i oppdrag å undersøke insertion sort. Det første vi oppdaget var at vi kunne bruke binær søking for å minke antall sammenligninger, binær søking funker bare på sorterte lister, men det går bra siden den delene av listen, som vi søker i er allerede sortert.

Vi oppdaget at insertion sort som var brukt i timsort allerede tok dette i bruk, så ingen forbedringder.

● Implementere prosjektgivers ideer til forbedring og/eller egne

● Finne en presis og reproduserbar måte å måle gevinst hvis det kan oppnås 

● Se på forskjellen mellom python- og java versjonen til algoritmen