DemoQuicksort.java

/*
 * Copyright 2024 Hochschule Luzern Informatik.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package ch.hslu.exercises.sw11.ex2.quicksort;

import ch.hslu.exercises.sw11.ex1.n41.array.init.RandomInitTask;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.time.Duration;
import java.util.Arrays;
import java.util.concurrent.ForkJoinPool;
import java.util.stream.LongStream;

/**
 * Vergleich von verschiedenen Quicksort-Implementationen.
 */
public final class DemoQuicksort {

    private static final Logger LOG = LoggerFactory.getLogger(DemoQuicksort.class);

    /**
     * Privater Konstruktor.
     */
    private DemoQuicksort() {
    }

    public static void main(final String[] args) {
        final int size = 100_000;
        final int[] arrayOriginal = new int[size];
        try (final ForkJoinPool pool = new ForkJoinPool()) {
            RandomInitTask initTask = new RandomInitTask(arrayOriginal, 100);
            pool.invoke(initTask);

            //Cold
            int[] arrayCold = Arrays.copyOf(arrayOriginal, size);
            sortRecursive(arrayCold, size);

            double averageDurationConcurrentSortingInMillis = LongStream.range(0, 10)
                    .map(t -> sortConcurrent(arrayOriginal, size, pool, size / Runtime.getRuntime().availableProcessors()).toMillis())
                    .average()
                    .orElseThrow(RuntimeException::new);

            LOG.info("QuicksortTask completed in {} ms for {} elements", averageDurationConcurrentSortingInMillis, size);


            double averageDurationRecursiveSortingInMillis = LongStream.range(0, 5)
                    .map(t -> sortRecursive(arrayOriginal, size).toMillis())
                    .average()
                    .orElseThrow(RuntimeException::new);
            LOG.info("Quicksort Recursive completed in {} ms for {} elements", averageDurationRecursiveSortingInMillis, size);

            double averageDurationDoublePivotSortingInMillis = LongStream.range(0, 10)
                    .map(t -> sortDoublePivotQuicksort(arrayOriginal, size).toMillis())
                    .average()
                    .orElseThrow(RuntimeException::new);
            LOG.info("Arrays.sort() completed in {} ms for {} elements", averageDurationDoublePivotSortingInMillis, size);

        }
    }

    private static Duration sortDoublePivotQuicksort(int[] arrayOriginal, int size) {
        Duration duration;
        long start;
        long stop;
        int[] arraySort = Arrays.copyOf(arrayOriginal, size);
        start = System.nanoTime();
        Arrays.sort(arraySort);
        stop = System.nanoTime();
        duration = Duration.ofNanos(stop - start);
//        LOG.info("Arrays.sort    : {} msec.", duration.toMillis());
        return duration;
    }

    private static Duration sortRecursive(int[] arrayOriginal, int size) {
        Duration duration;
        long start;
        long stop;
        int[] arrayRec = Arrays.copyOf(arrayOriginal, size);
        start = System.nanoTime();
        QuicksortRecursive.quicksort(arrayRec);
        stop = System.nanoTime();
        duration = Duration.ofNanos(stop - start);
//        LOG.info("QuicksortRec.  : {} msec.", duration.toMillis());
        return duration;
    }

    private static Duration sortConcurrent(int[] arrayOriginal, int size, ForkJoinPool pool, int threshold) {
        long start;
        long stop;
        Duration duration;
        int[] arrayTask = Arrays.copyOf(arrayOriginal, size);
        final QuicksortTask sortTask = new QuicksortTask(arrayTask, threshold);
        start = System.nanoTime();
        pool.invoke(sortTask);
        stop = System.nanoTime();
        duration = Duration.ofNanos(stop - start);
//        LOG.info("QuicksortTask  : {} msec.", duration.toMillis());
        return duration;
    }
}