2
\$\begingroup\$

I have this counting sort for byte values running in linear time with respect to array length:

Arrays.java

package net.coderodde.util;

import java.util.Random;

/**
 * This class contains static methods for sorting {@code byte} arrays.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Apr 24, 2019)
 */
public final class Arrays {

    /**
     * Sorts the given {@code byte} array in its entirety.
     * 
     * @param arrays the array to sort.
     */
    public static void sort(byte[] arrays) {
        sort(arrays, 0, arrays.length);
    }

    /**
     * Sorts the given {@code byte} array omitting first {@code fromIndex} 
     * array components starting from beginning, and omitting last 
     * {@code array.length - toIndex} array components from the ending.
     * 
     * @param array     the array holding the target range.
     * @param fromIndex the starting index of the target range.
     * @param toIndex   one position to the right from the last element 
     *                  belonging to the target range.
     */
    public static void sort(byte[] array, int fromIndex, int toIndex) {
        rangeCheck(array.length, fromIndex, toIndex);
        int[] bucketCounters = new int[256];

        for (int index = fromIndex; index < toIndex; index++) {
            bucketCounters[Byte.toUnsignedInt(array[index])]++;
        }

        int index = fromIndex;

        // Insert the negative values first:
        for (int bucketIndex = 128; bucketIndex != 256; bucketIndex++) {
            java.util.Arrays.fill(array,
                                  index, 
                                  index += bucketCounters[bucketIndex], 
                                  (byte) bucketIndex);
        }

        // Insert the positive values next:
        for (int bucketIndex = 0; bucketIndex != 128; bucketIndex++) {
            java.util.Arrays.fill(array,
                                  index,
                                  index += bucketCounters[bucketIndex],
                                  (byte) bucketIndex);
        }
    }

    /**
     * Checks that {@code fromIndex} and {@code toIndex} are in
     * the range and throws an exception if they aren't.
     */
    private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
        if (fromIndex > toIndex) {
            throw new IllegalArgumentException(
                    "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
        }

        if (fromIndex < 0) {
            throw new ArrayIndexOutOfBoundsException(fromIndex);
        }

        if (toIndex > arrayLength) {
            throw new ArrayIndexOutOfBoundsException(toIndex);
        }
    }

    public static void main(String[] args) {
        warmup();
        benchmark();
    }

    private static final int LENGTH = 50_000_000;

    private static final void warmup() {
        runBenchmark(false);
    }

    private static final void benchmark() {
        runBenchmark(true);
    }

    private static final void runBenchmark(boolean output) {
        long seed = System.currentTimeMillis();
        Random random = new Random();
        byte[] array1 = createRandomByteArray(LENGTH, random);
        byte[] array2 = array1.clone();
        byte[] array3 = array1.clone();

        if (output) {
            System.out.println("seed = " + seed);
        }

        long startTime = System.nanoTime();
        java.util.Arrays.sort(array1);
        long endTime = System.nanoTime();

        if (output) {
            System.out.println("java.util.Arrays.sort(byte[]) in " +
                               (endTime - startTime) / 1e6 + 
                               " milliseconds.");
        }

        startTime = System.nanoTime();
        java.util.Arrays.parallelSort(array2);
        endTime = System.nanoTime();

        if (output) {
            System.out.println("java.util.Arrays.parallelSort(byte[]) in " +
                               (endTime - startTime) / 1e6 + 
                               " milliseconds.");
        }

        startTime = System.nanoTime();
        net.coderodde.util.Arrays.sort(array3);
        endTime = System.nanoTime();

        if (output) {
            System.out.println("net.coderodde.Arrays.sort(byte[]) in " +
                               (endTime - startTime) / 1e6 + 
                               " milliseconds.");

            System.out.println("Algorithms agree: " + 
                    (java.util.Arrays.equals(array1, array2) &&
                     java.util.Arrays.equals(array1, array3)));
        }
    }

    private static final byte[] createRandomByteArray(int length, 
                                                      Random random) {
        byte[] array = new byte[length];

        for (int i = 0; i < length; i++) {
            array[i] = (byte) random.nextInt();
        }

        return array;
    }
}

Typical output

seed = 1556112137029
java.util.Arrays.sort(byte[]) in 67.6446 milliseconds.
java.util.Arrays.parallelSort(byte[]) in 210.0057 milliseconds.
net.coderodde.Arrays.sort(byte[]) in 46.6332 milliseconds.
Algorithms agree: true
\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

I find the big points covered well:

  • class and methods have one clear, documented purpose
  • the API follows the well-known java.util.Arrays
    (if not to the point of documenting RuntimeExceptions thrown)

I'd try to get rid of magic literals and code replication:
size counts = new int[Byte.MAX_VALUE-Byte.MIN_VALUE+1] (or 1<<Byte.SIZE?), use

for (int bucket = Byte.MIN_VALUE ; bucket <= Byte.MAX_VALUE; bucket++)
    Arrays.fill(array,
                index, 
                index += counts[Byte.toUnsignedInt((byte) bucket)], 
                (byte) bucket);

I found it interesting to ogle the RTE source code I use.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.