Last active
June 17, 2019 05:21
-
-
Save coderodde/493407bc1c57352b53c2aa18b5c9a7a8 to your computer and use it in GitHub Desktop.
Gist for net.coderodde.util.Arrays.sort(byte[])
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 array the array to sort. | |
*/ | |
public static void sort(byte[] array) { | |
sort(array, 0, array.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(LENGTH1); | |
benchmark(LENGTH1); | |
benchmark(LENGTH2); | |
benchmark(LENGTH3); | |
benchmark(LENGTH4); | |
} | |
private static final int LENGTH1 = 100_000_000; | |
private static final int LENGTH2 = 10_000_000; | |
private static final int LENGTH3 = 1_000_000; | |
private static final int LENGTH4 = 100_000; | |
private static final void warmup(int length) { | |
runBenchmark(false, length); | |
} | |
private static final void benchmark(int length) { | |
runBenchmark(true, length); | |
} | |
private static final void runBenchmark(boolean output, int length) { | |
if (output) { | |
System.out.println("=== Length: " + length + " ==="); | |
} | |
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("--- Random array ---"); | |
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(); | |
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))); | |
System.out.println(); | |
} | |
array1 = createEqualElementByteArray(length); | |
array2 = array1.clone(); | |
array3 = array1.clone(); | |
startTime = System.nanoTime(); | |
java.util.Arrays.sort(array1); | |
endTime = System.nanoTime(); | |
if (output) { | |
System.out.println("--- Equal element array ---"); | |
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(); | |
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))); | |
System.out.println(); | |
System.out.println(); | |
} | |
} | |
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; | |
} | |
private static final byte[] createEqualElementByteArray(int length) { | |
byte[] array = new byte[length]; | |
for (int i = 0; i < length; i++) { | |
array[i] = -1; | |
} | |
return array; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment