View Javadoc
1   /*
2    * Copyright 2024 Hochschule Luzern Informatik.
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    *      http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  package ch.hslu.exercises.sw11.ex2.quicksort;
17  
18  import ch.hslu.exercises.sw11.ex1.n41.array.init.RandomInitTask;
19  import org.slf4j.Logger;
20  import org.slf4j.LoggerFactory;
21  
22  import java.time.Duration;
23  import java.util.Arrays;
24  import java.util.concurrent.ForkJoinPool;
25  import java.util.stream.LongStream;
26  
27  /**
28   * Vergleich von verschiedenen Quicksort-Implementationen.
29   */
30  public final class DemoQuicksort {
31  
32      private static final Logger LOG = LoggerFactory.getLogger(DemoQuicksort.class);
33  
34      /**
35       * Privater Konstruktor.
36       */
37      private DemoQuicksort() {
38      }
39  
40      public static void main(final String[] args) {
41          final int size = 100_000;
42          final int[] arrayOriginal = new int[size];
43          try (final ForkJoinPool pool = new ForkJoinPool()) {
44              RandomInitTask initTask = new RandomInitTask(arrayOriginal, 100);
45              pool.invoke(initTask);
46  
47              //Cold
48              int[] arrayCold = Arrays.copyOf(arrayOriginal, size);
49              sortRecursive(arrayCold, size);
50  
51              double averageDurationConcurrentSortingInMillis = LongStream.range(0, 10)
52                      .map(t -> sortConcurrent(arrayOriginal, size, pool, size / Runtime.getRuntime().availableProcessors()).toMillis())
53                      .average()
54                      .orElseThrow(RuntimeException::new);
55  
56              LOG.info("QuicksortTask completed in {} ms for {} elements", averageDurationConcurrentSortingInMillis, size);
57  
58  
59              double averageDurationRecursiveSortingInMillis = LongStream.range(0, 5)
60                      .map(t -> sortRecursive(arrayOriginal, size).toMillis())
61                      .average()
62                      .orElseThrow(RuntimeException::new);
63              LOG.info("Quicksort Recursive completed in {} ms for {} elements", averageDurationRecursiveSortingInMillis, size);
64  
65              double averageDurationDoublePivotSortingInMillis = LongStream.range(0, 10)
66                      .map(t -> sortDoublePivotQuicksort(arrayOriginal, size).toMillis())
67                      .average()
68                      .orElseThrow(RuntimeException::new);
69              LOG.info("Arrays.sort() completed in {} ms for {} elements", averageDurationDoublePivotSortingInMillis, size);
70  
71          }
72      }
73  
74      private static Duration sortDoublePivotQuicksort(int[] arrayOriginal, int size) {
75          Duration duration;
76          long start;
77          long stop;
78          int[] arraySort = Arrays.copyOf(arrayOriginal, size);
79          start = System.nanoTime();
80          Arrays.sort(arraySort);
81          stop = System.nanoTime();
82          duration = Duration.ofNanos(stop - start);
83  //        LOG.info("Arrays.sort    : {} msec.", duration.toMillis());
84          return duration;
85      }
86  
87      private static Duration sortRecursive(int[] arrayOriginal, int size) {
88          Duration duration;
89          long start;
90          long stop;
91          int[] arrayRec = Arrays.copyOf(arrayOriginal, size);
92          start = System.nanoTime();
93          QuicksortRecursive.quicksort(arrayRec);
94          stop = System.nanoTime();
95          duration = Duration.ofNanos(stop - start);
96  //        LOG.info("QuicksortRec.  : {} msec.", duration.toMillis());
97          return duration;
98      }
99  
100     private static Duration sortConcurrent(int[] arrayOriginal, int size, ForkJoinPool pool, int threshold) {
101         long start;
102         long stop;
103         Duration duration;
104         int[] arrayTask = Arrays.copyOf(arrayOriginal, size);
105         final QuicksortTask sortTask = new QuicksortTask(arrayTask, threshold);
106         start = System.nanoTime();
107         pool.invoke(sortTask);
108         stop = System.nanoTime();
109         duration = Duration.ofNanos(stop - start);
110 //        LOG.info("QuicksortTask  : {} msec.", duration.toMillis());
111         return duration;
112     }
113 }