# Mikrobenchmark Sortierverfahren



## vandread (9. Okt 2010)

hallo,

ich habe folgende aufgabe gestellt bekommen...



> a) Implementieren Sie das von Ihnen in der Vorlesung entwickelte Sortierverfahren.
> b) Führen Sie einen MikroBenchmark für das in a) entwickelte Verfahren durch. Verwenden Sie repräsentative Werte für n (100.000 bis 600.000) und führen Sie mindestens 5 Tests für jedes n durch. Messen Sie jeweils die Laufzeit der Algorithmen.
> c) Stellen Sie die gemessenen Laufzeiten graphisch als Liniendiagramm dar, so dass Sie eine Aussage zum Laufzeitverhalten ableiten können. Hierzu können Sie beispielsweise EXCEL verwenden.
> d) Implementieren Sie auch das Sortierverfahren Bubblesort aus der Vorlesung und führen Sie auch hierzu einen MikroBenchmark durch.
> e) Vergleichen Sie das Laufzeitverhalten der beiden Verfahren anhand des durchgeführten Benchmarks bzw. des erzeugten Diagramms.



ich habe dann also folgendes programmiert...


```
public class Main {

    public static void main(String[] args) {
        long start;
        long end;
        int size = 200000;
        Integer[] array = new Integer[size];

        for (int i = 0; i < array.length; i++) {
            array[i] = ((int) (Math.random() * size) + 1);
        }

        start = System.currentTimeMillis();
        sort(array);
        end = System.currentTimeMillis();

        System.out.println("Start: " + start);
        System.out.println("End:   " + end);
        System.out.println("Time:  " + (end - start));
    }

    public static void sort(Integer[] unsorted) {
        Integer[] sorted = new Integer[unsorted.length];
        Integer least = null;
        Integer position = null;

        for (int i = 0; i < sorted.length; i++) {
            for (int j = 0; j < unsorted.length; j++) {
                if (least == null || (unsorted[j] != null && unsorted[j] < least)) {
                    least = unsorted[j];
                    position = j;
                }
            }
            unsorted[position] = null;
            sorted[i] = least;
            least = null;
        }
    }

    public static void bubbleSort(Integer[] unsorted) {
        boolean swapped = true;
        int j = 0;
        int tmp;

        while (swapped) {
            swapped = false;
            j++;

            for (int i = 0; i < unsorted.length - j; i++) {
                if (unsorted[i] > unsorted[i + 1]) {
                    tmp = unsorted[i];
                    unsorted[i] = unsorted[i + 1];
                    unsorted[i + 1] = tmp;
                    swapped = true;
                }
            }
        }
    }
}
```

ich habe eine methode sort welche meinen sortierverfahren durchführt und einmal die methode bubblesort welche eben den bubblesort macht.

am anfang des programmes erstelle ich ein array mit der länge n,
und fülle dann dieses array zufällig mit irgendwelchen zahlen die größer 0 und kleiner/gleich n sind.
dann sortiere ich dieses array und gebe mir in ms aus wie lange ich dafür gebraucht habe.

in dem code oben ist n = 200000 (size) und es wird die methode sort ausgeführt.

ich habe mir eigentlich gedacht das es nichts wildes ist doch irgendwie habe ich ein ziemlich komisches gefühl...
vor allem wegen dem beispiel diagramm welches mit der aufgabe ausgegeben wurde:







(leider ohne achsen beschriftung -.-)

okay also wenn ich das diagramm mir so anschaue dann hat er da für 100000 zahlen fast 0 ms gebraucht und für 200000 ca 200 ms (ich gehe mal davon aus das es ms sind...) usw...

so aber wenn ich jetzt mein programm laufen lasse...
dann kommen folgende sachen raus:

bubblesort
n = 100000 -› 104483 ms
n = 200000 -› 506135 ms

sort
n = 100000 -› 46630 ms
n = 200000 -› 268897 ms

mehr als 200000 habe ich nicht gemacht weil mir das einfach zu lange dauert und ich irgendwie das gefühl habe das es nicht stimmen kann...
warum habe ich das gefühl?
naja also erst mal weil mein bubblesort einfach so lange braucht und zweitens das mein eigener sortieralgorithmus viel schneller ist als der bubblesort... aber trozdem lange braucht...

was sagt ihr dazu?
kann das wirklich sein?

vor allem die werte sind ja x mal größer als die auf dem beispieldiagramm...


----------



## Antoras (9. Okt 2010)

Ich kann dir auch nicht sagen wie die Werte auf dem Diagramm zustande kommen. Fakt ist aber, dass Bubblesort beschissen langsam ist, da du ein quadratisches Laufzeitverhalten hast. Guck dir lieber Quicksort an, das hat unter besten Umständen eine Laufzeit von n*log(n)...


----------



## ice-breaker (9. Okt 2010)

Antoras hat gesagt.:


> Guck dir lieber Quicksort an, das hat unter besten Umständen eine Laufzeit von n*log(n)...


er hat aber vorgegeben bekommen, welche er benchmarken soll 


Wie die Werte zustandekommen ist bei Microbenchmarks nie nachvollziehbar, anderer Prozessor, andere Auslastung usw. und schon sind die Ergebnisse verfälscht.

Beide Ergebnisse sehen logisch aus, die Bubblesort-Implementierung von dir stoppt direkt wenn alle Elemente sortiert sind, von daher ist der Aufwand bei 100k und 200k Elementen linear, es sollten also nur doppelt soviele Vergleiche sein. Warum du jetzt so massive Unterschiede hast, ist eben sehr schwer zu sagen, möglicherweise mehr GC-Operationen, weil der Speicher voller ist und öfter versucht wird, etwas leerzuräumen oder wer weiß.

Die Grafik passt jedoch nicht zu dem wirklichen quadratischen Verhalten des Bubblesort-Algorithmuses, meiner Meinung nach müsste zumindest der mit randomisiertem Input deutlich steiler sein.


----------



## slawaweis (9. Okt 2010)

vandread hat gesagt.:


> vor allem die werte sind ja x mal größer als die auf dem beispieldiagramm...


vergiss die Zahlen auf dem Beispieldiagramm. Die sind vom Computer, von der Auslastung und Implementierung abhängig. Das wichtige ist, dass deine Ergebnisse optisch ähnliche Kurven ergeben, unabhängig von der Skalierung. Hier geht es darum verschiedene Sortieralgorithmen kennenzulernen und vergleichen zu können. Geschwindigkeitsrekorde erwartet hier keiner. Also erstelle mit deiner Implementierung erst mal alle Zahlen und das entsprechende Diagramm. Wenn es optisch zu sehr von dem Beispieldiagramm abweicht, dann muss man nach dem Problem suchen.



Antoras hat gesagt.:


> Ich kann dir auch nicht sagen wie die Werte auf dem Diagramm zustande kommen. Fakt ist aber, dass Bubblesort beschissen langsam ist, da du ein quadratisches Laufzeitverhalten hast. Guck dir lieber Quicksort an, das hat unter besten Umständen eine Laufzeit von n*log(n)...


habe bitte etwas mehr Respekt vor Bubblesort. Im besten Fall hat der Algorithmus eine Laufzeit von O(n), wie übrigens auf dem Beispieldiagramm schön zu sehen. Quicksort hat immer mindestens eine Laufzeit von O(n*log(n)). Bei einer Problemstellung, wo die Aufgabe fast sortiert ist, wäre der Bubblesort schneller. Deshalb werden in komplexen Systemen die Daten sogar vorher analysiert, um dann den optimaleren Algorithmus auszuwählen.

Slawa


----------



## Antoras (10. Okt 2010)

slawaweis hat gesagt.:


> habe bitte etwas mehr Respekt vor Bubblesort. Im besten Fall hat der Algorithmus eine Laufzeit von O(n), wie übrigens auf dem Beispieldiagramm schön zu sehen.


Ist mir bekannt. Ich hab Quicksort auch nicht als Allheilmittel hingestellt. Aber selbst mit Vorsortierung lohnt sich Bubblesort fast nie, da andere Algos wie Shellsort oder Insertionsort da in der Regel trotzdem schneller sind.


----------



## Marco13 (10. Okt 2010)

Und ganz nebenbei: Wenn du statt Integer[] arrays int[] arrays verwenden würdest, wäre das ganze nochmal deutlich schneller (wenn auch nur um einen konstanten Faktor - und darum, dass der ""egal"" ist, geht es ja in dieser Aufgabe  )


----------



## JohannisderKaeufer (10. Okt 2010)

Also ich glaube das es sich bei der Vertikalen Achse um Sekunden handelt und nicht wie anfangs gemeint ms.

Und wenn ich das Diagramm betrachte und da für 600 000 Zahlen mit Bubblesort 1500 Sek. also 25 Minuten rauskommen. Dann kann das einem doch vermeintlich lange vorkommen.

Wenn ich nun deine Ergebnisse mit denen des Diagrams vergleiche, scheint es mir das du auf deinem System etwa doppelt, bis dreifach so lange brauchst.

Da heißt es dann also abwarten und Teetrinken.


----------



## Sonecc (11. Okt 2010)

Wenn du 2 Sortierverfahren vergleichen willst, sollten beide die gleichen Bedingungen haben. Das bedeutet auch, dass beide mit den gleichen Werten arbeiten sollten. Dem Code nach zu urteilen ist das bei dir nicht der Fall.


----------



## fastjack (11. Okt 2010)

Zum benchen  kannst Du auch gut [Eigenwerbung]QuickBench[/Eigenwerbung] benutzen (http://www.java-forum.org/blogs/fastjack/125-benchmarking.html).

Ein entsprechender Benchmark würde in Deinem Fall so aussehen:


```
package blog.benchmarking;


public class SortBenches {

    public static void main(String[] args) {
        QuickBench.benchNxM(10, 50000, new long[] { 10, 100, 1000 },
                new long[] { 100000, 200000 }, new Bench[] {new BubbleSortBench(),
                new SortBench()});
    }

    // Benchmark zu BubbleSort
    static class BubbleSortBench implements Bench {

        Integer[] array = null;

        @Override
        public String getName() {
            return "Bubble-Sort";
        }

        @Override
        public void reset() {
            array = null;
        }

        @Override
        public void prepare(long lm) {
            array = new Integer[(int) lm];
            for (int i = 0; i < array.length; i++) {
                array[i] = ((int) (Math.random() * lm) + 1);
            }
        }

        @Override
        public void execute(long lm) {
            bubbleSort(array);
        }

    }

    // Benchmark zu Sort
    static class SortBench implements Bench {

        Integer[] array = null;

        @Override
        public String getName() {
            return "Sort";
        }

        @Override
        public void reset() {
            array = null;
        }

        @Override
        public void prepare(long lm) {
            array = new Integer[(int) lm];
            for (int i = 0; i < array.length; i++) {
                array[i] = ((int) (Math.random() * lm) + 1);
            }
        }

        @Override
        public void execute(long lm) {
            sort(array);
        }

    }

    /* Originalmethoden */

    public static void bubbleSort(Integer[] unsorted) {
        boolean swapped = true;
        int j = 0;
        int tmp;

        while (swapped) {
            swapped = false;
            j++;

            for (int i = 0; i < unsorted.length - j; i++) {
                if (unsorted[i] > unsorted[i + 1]) {
                    tmp = unsorted[i];
                    unsorted[i] = unsorted[i + 1];
                    unsorted[i + 1] = tmp;
                    swapped = true;
                }
            }
        }
    }

    public static void sort(Integer[] unsorted) {
        Integer[] sorted = new Integer[unsorted.length];
        Integer least = null;
        Integer position = null;

        for (int i = 0; i < sorted.length; i++) {
            for (int j = 0; j < unsorted.length; j++) {
                if (least == null || (unsorted[j] != null && unsorted[j] < least)) {
                    least = unsorted[j];
                    position = j;
                }
            }
            unsorted[position] = null;
            sorted[i] = least;
            least = null;
        }
    }

}
```


----------



## Sonecc (11. Okt 2010)

in einer hausaufgabe eine fremde Lib zu benutzen wird wohl nicht erlaubt sein^^


----------



## fastjack (11. Okt 2010)

Er soll nur die Zeiten messen und dann eine Kurve malen. Da steht nichts davon, das er das Verfahren zum Zeitmessen mut abgeben muß


----------



## fastjack (11. Okt 2010)

```
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
| Bench                     |   Rounds |    Objects |       ms | ms (avg) |              nt |        nt (avg) |
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
| Bubble-Sort               |        1 |         10 |        0 |        0 |           1.956 |           1.956 |
| Bubble-Sort               |       10 |         10 |        0 |        0 |          14.946 |           1.494 |
| Bubble-Sort               |      100 |         10 |        0 |        0 |         141.154 |           1.411 |
| Bubble-Sort               |        1 |        100 |        0 |        0 |          57.410 |          57.410 |
| Bubble-Sort               |       10 |        100 |        0 |        0 |         557.332 |          55.733 |
| Bubble-Sort               |      100 |        100 |        6 |        0 |       5.765.398 |          57.653 |
| Bubble-Sort               |        1 |      1.000 |        7 |        7 |       7.674.649 |       7.674.649 |
| Bubble-Sort               |       10 |      1.000 |       77 |        7 |             ... |             ... |
| Bubble-Sort               |      100 |      1.000 |      603 |        6 |             ... |             ... |
| Bubble-Sort               |        1 |     10.000 |      663 |      663 |             ... |             ... |
| Bubble-Sort               |       10 |     10.000 |    6.644 |      664 |             ... |             ... |
| Bubble-Sort               |      100 |     10.000 |   66.307 |      663 |             ... |             ... |
| Sort                      |        1 |         10 |        0 |        0 |           2.305 |           2.305 |
| Sort                      |       10 |         10 |        0 |        0 |          15.367 |           1.536 |
| Sort                      |      100 |         10 |        0 |        0 |         144.995 |           1.449 |
| Sort                      |        1 |        100 |        0 |        0 |          56.082 |          56.082 |
| Sort                      |       10 |        100 |        0 |        0 |         526.116 |          52.611 |
| Sort                      |      100 |        100 |        5 |        0 |       5.195.914 |          51.959 |
| Sort                      |        1 |      1.000 |        5 |        5 |       4.833.296 |       4.833.296 |
| Sort                      |       10 |      1.000 |       48 |        4 |             ... |             ... |
| Sort                      |      100 |      1.000 |      483 |        4 |             ... |             ... |
| Sort                      |        1 |     10.000 |      487 |      487 |             ... |             ... |
| Sort                      |       10 |     10.000 |    4.851 |      485 |             ... |             ... |
| Sort                      |      100 |     10.000 |   48.627 |      486 |             ... |             ... |
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
java version 1.6.0_16
Java(TM) SE Runtime Environment(build 1.6.0_16-b01)
Java HotSpot(TM) Client VM(build 14.2-b01, mixed mode)
Windows Vista(6.0) x86
Max memory: 63MB
```

Intel Core2Duo E7400 2* 2.8Ghz, 4GB RAM

Nachtrag:


```
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
| Bench                     |   Rounds |    Objects |       ms | ms (avg) |              nt |        nt (avg) |
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
| Bubble-Sort               |        1 |    100.000 |  163.597 |  163.597 |             ... |             ... |
| Bubble-Sort               |        1 |    200.000 |  803.460 |  803.460 |             ... |             ... |
| Sort                      |        1 |    100.000 |   49.006 |   49.006 |             ... |             ... |
| Sort                      |        1 |    200.000 |  237.442 |  237.442 |             ... |             ... |
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
java version 1.6.0_16
Java(TM) SE Runtime Environment(build 1.6.0_16-b01)
Java HotSpot(TM) Client VM(build 14.2-b01, mixed mode)
Windows Vista(6.0) x86
Max memory: 63MB
```


----------



## Sonecc (11. Okt 2010)

Explizit steht es nicht dabei, in der Regel bedeutet im Studium ein "Implementieren sie" für "Schreib es und gib es ab" (zumindest an meiner Uni)


----------



## fastjack (11. Okt 2010)

Das erste, was ich damals lernte war, mach das was auf dem Zettel steht, und NUR das. Alles andere ist Bonus und für Bonus gibts keine Punkte (weil ja auch nicht gefragt, so der Prof.). Die ersten Zettel habe ich auch mit allerlei zusätzlichem Zeugs ausgestattet, um dann festzustellen, das Andere ganz plain gearbeitet haben und am Ende noch mehr Punkte hatten als ich, natürlich bei weniger Zeiteinsatz. Und Zeit war knapp an der FU-Berlin, das kann ich dir sagen.


----------



## vandread (11. Okt 2010)

erst mal vielen dank an alle für die tipps und anregungen und meinungen und sonst alles 

@Sonecc:
ja da hast du recht doch der prof. meinte das es so auch okay sein würde da es hier um durchschnitts werte gehen soll um zu schauen welcher alg. im allgemeinen besser bzw schneller arbeitet...

hier sind mal meine ergebnisse...
ich habe ein paar messungen ausgelassen weil mir das dann doch zu doof war studenlang den pc einfach rechnen zu lassen und ihn in ruhe zu lassen damit alle berechnungen unter "fast" gleichen bedingungen laufen...


----------



## fastjack (11. Okt 2010)

Kein guter Tag für BubbleSort... Nur der Interesse halber, kannst Du mal Deine Hardware-Infos posten.


----------



## vandread (11. Okt 2010)

Intel Core2 Due E6600
2048MB G.Skill PC2-1066
Sapphire Vapor-X Radeon HD 5770 1GB GDDR5 OC-E
WD Raptor 150GB 10.000U
Asus P5W DH Deluxe


----------



## fastjack (15. Dez 2010)

-- bitte löschen  --


----------

