The previous and second iteration at:
MSD radix sort in Java for parallel arrays - follow-up
Changes:
arrays[j][i] != arrays[j + 1][i]to!Objects.equals(arrays[j][i], arrays[j + 1][i])inareEqual.net.coderodde.util.Arraysrenamed tonet.coderodde.util.CoderoddeArrays.- The
mergesort/buffer copy mess was hidden in a method.
CoderoddeArrays.java:
package net.coderodde.util;
import java.util.Objects;
public class CoderoddeArrays {
private static final int BITS_PER_BUCKET = 8;
private static final int BUCKETS = 1 << BITS_PER_BUCKET;
private static final int BUCKET_MASK = BUCKETS - 1;
private static final long SIGN_MASK = 1L << 63;
private static final int MERGESORT_THRESHOLD = 4096;
public static final <E> void sort(final Entry<E>[] array,
final int fromIndex,
final int toIndex) {
if (toIndex - fromIndex < 2) {
// Trivially sorted or indices ass-backwards.
return;
}
final Entry<E>[] buffer = array.clone();
sortImpl(array, buffer, 0, fromIndex, toIndex);
}
public static final <E> void sort(final Entry<E>[] array) {
sort(array, 0, array.length);
}
public static final <E extends Comparable<? super E>>
boolean isSorted(final E[] array,
final int fromIndex,
final int toIndex) {
for (int i = fromIndex; i < toIndex - 1; ++i) {
if (array[i].compareTo(array[i + 1]) > 0) {
return false;
}
}
return true;
}
public static final <E extends Comparable<? super E>>
boolean isSorted(final E[] array) {
return isSorted(array, 0, array.length);
}
public static final <E> boolean areEqual(final Entry<E>[]... arrays) {
for (int i = 0; i < arrays.length - 1; ++i) {
if (arrays[i].length != arrays[i + 1].length) {
return false;
}
}
for (int i = 0; i < arrays[0].length; ++i) {
for (int j = 0; j < arrays.length - 1; ++j) {
if (!Objects.equals(arrays[j][i], arrays[j + 1][i])) {
return false;
}
}
}
return true;
}
/**
* This static method sorts the entry array by bytes that are not
* most-significant.
*
* @param <E> the type of satellite data in the entry array.
* @param source the source array.
* @param target the target array.
* @param byteIndex the index of the byte to use as the sorting key. 0
* represents the least-significant byte.
* @param fromIndex the least index of the range to sort.
* @param toIndex the index one past the greatest index of the range to
* sort.
*/
private static <E> void sortImpl(final Entry<E>[] source,
final Entry<E>[] target,
final int recursionDepth,
final int fromIndex,
final int toIndex) {
// Try merge sort.
if (toIndex - fromIndex <= MERGESORT_THRESHOLD) {
mergesortAndCleanUp(source,
target,
recursionDepth,
fromIndex,
toIndex);
return;
}
final int[] bucketSizeMap = new int[BUCKETS];
final int[] startIndexMap = new int[BUCKETS];
final int[] processedMap = new int[BUCKETS];
// Compute the size of each bucket.
for (int i = fromIndex; i < toIndex; ++i) {
bucketSizeMap[getBucket(source[i].key(), recursionDepth)]++;
}
// Initialize the start index map.
startIndexMap[0] = fromIndex;
// Compute the start index map in its entirety.
for (int i = 1; i != BUCKETS; ++i) {
startIndexMap[i] = startIndexMap[i - 1] +
bucketSizeMap[i - 1];
}
// Insert the entries from 'source' into their respective 'target'.
for (int i = fromIndex; i < toIndex; ++i) {
final Entry<E> e = source[i];
final int index = getBucket(source[i].key(), recursionDepth);
target[startIndexMap[index] + processedMap[index]++] = e;
}
if (recursionDepth == 7) {
// There is nowhere to recur, return.
return;
}
// Recur to sort each bucket.
for (int i = 0; i != BUCKETS; ++i) {
if (bucketSizeMap[i] != 0) {
sortImpl(target,
source,
recursionDepth + 1,
startIndexMap[i],
startIndexMap[i] + bucketSizeMap[i]);
}
}
}
/**
* Sorts the range <code>[fromIndex, toIndex)</code> between the arrays
* <code>source</code> and <code>target</code>.
*
* @param <E> the type of entries' satellite data.
* @param source the source array; the data to sort is assumed to be in this
* array.
* @param target acts as an auxiliary array.
* @param fromIndex the least component index of the range to sort.
* @param toIndex <code>toIndex - 1</code> is the index of the rightmost
* component in the range to sort.
* @return <code>true</code> if there was an even amount of merge passes,
* which implies that the sorted range ended up in <code>source</code>.
* Otherwise <code>false</code> is returned, and the sorted range ended up
* in the array <code>target</code>.
*/
private static final <E> boolean mergesort(final Entry<E>[] source,
final Entry<E>[] target,
final int fromIndex,
final int toIndex) {
final int RANGE_LENGTH = toIndex - fromIndex;
Entry<E>[] s = source;
Entry<E>[] t = target;
int passes = 0;
for (int width = 1; width < RANGE_LENGTH; width <<= 1) {
++passes;
int c = 0;
for (; c < RANGE_LENGTH / width; c += 2) {
int left = fromIndex + c * width;
int right = left + width;
int i = left;
final int leftBound = right;
final int rightBound = Math.min(toIndex, right + width);
while (left < leftBound && right < rightBound) {
t[i++] = s[right].key() < s[left].key() ?
s[right++] :
s[left++];
}
while (left < leftBound) { t[i++] = s[left++]; }
while (right < rightBound) { t[i++] = s[right++]; }
}
if (c * width < RANGE_LENGTH) {
for (int i = fromIndex + c * width; i < toIndex; ++i) {
t[i] = s[i];
}
}
final Entry<E>[] tmp = s;
s = t;
t = tmp;
}
return (passes & 1) == 0;
}
private static final <E>
void mergesortAndCleanUp(final Entry<E>[] source,
final Entry<E>[] target,
final int recursionDepth,
final int fromIndex,
final int toIndex) {
// If 'even' is true, the sorted ranged ended up in 'source'.
final boolean even = mergesort(source, target, fromIndex, toIndex);
if (even) {
// source contains the sorted bucket.
if ((recursionDepth & 1) == 1) {
// byteIndex = 6, 4, 2, 0.
// source is buffer, copy to target.
System.arraycopy(source,
fromIndex,
target,
fromIndex,
toIndex - fromIndex);
}
} else {
// target contains the sorted bucket.
if ((recursionDepth & 1) == 0) {
// byteIndex = 5, 3, 1.
// target is buffer, copy to source.
System.arraycopy(target,
fromIndex,
source,
fromIndex,
toIndex - fromIndex);
}
}
}
private static final int getBucket(final long key,
final int recursionDepth) {
final int bitShift = 64 - (recursionDepth + 1) * BITS_PER_BUCKET;
return (int)((key ^ SIGN_MASK) >>> bitShift) & BUCKET_MASK;
}
}
Entry.java:
package net.coderodde.util;
/**
* The wrapper class holding a satellite datum and the key.
*
* @param <E> the type of a satellite datum.
*/
public final class Entry<E> implements Comparable<Entry<E>> {
/**
* The sorting key.
*/
private final long key;
/**
* The satellite data.
*/
private final E satelliteData;
/**
* Constructs a new <code>Entry</code> with key <code>key</code> and
* the satellite datum <code>satelliteData</code>.
*
* @param key the key of this entry.
* @param satelliteData the satellite data associated with the key.
*/
public Entry(final long key, final E satelliteData) {
this.key = key;
this.satelliteData = satelliteData;
}
public long key() {
return key;
}
public E satelliteData() {
return satelliteData;
}
/**
* Compares this <code>Entry</code> with another.
*
* @param o the entry to compare against.
*
* @return a negative value if this entry's key is less than that of
* <code>o</code>, a positive value if this entry's key is greater than that
* of <code>o</code>, or 0 if the two keys are equal.
*/
@Override
public int compareTo(Entry<E> o) {
return Long.compare(key, o.key);
}
}
Demo.java:
package net.coderodde.util;
import java.util.Random;
public class Demo {
private static final int N = 10000000;
public static void main(final String... args) {
final long seed = System.currentTimeMillis();
final Random rnd = new Random(seed);
final Entry<Integer>[] array1 = getRandomEntryArray(N, rnd);
final Entry<Integer>[] array2 = array1.clone();
System.out.println("Seed: " + seed);
long ta = System.currentTimeMillis();
net.coderodde.util.CoderoddeArrays.sort(array1);
long tb = System.currentTimeMillis();
System.out.println("net.coderodde.util.CoderoddeArrays.sort in " +
(tb - ta) + " ms.");
ta = System.currentTimeMillis();
java.util.Arrays.sort(array2);
tb = System.currentTimeMillis();
System.out.println("java.util.Arrays.sort in " +
(tb - ta) + " ms.");
System.out.println("Arrays are equal: " +
CoderoddeArrays.areEqual(array1, array2));
System.out.println("Sorted: " + CoderoddeArrays.isSorted(array1));
}
private static Entry<Integer>[] getRandomEntryArray(final int size,
final Random rnd) {
final Entry<Integer>[] array = new Entry[size];
for (int i = 0; i < size; ++i) {
array[i] = new Entry<>(rnd.nextLong(), null);
}
return array;
}
}
So, what do you think?
