Class ParallelSorter
- java.lang.Object
-
- net.sf.cglib.util.SorterTemplate
-
- net.sf.cglib.util.ParallelSorter
-
public abstract class ParallelSorter extends SorterTemplate
For the efficient sorting of multiple arrays in parallel.Given two arrays of equal length and varying types, the standard technique for sorting them in parallel is to create a new temporary object for each row, store the objects in a temporary array, sort the array using a custom comparator, and the extract the original values back into their respective arrays. This is wasteful in both time and memory.
This class generates bytecode customized to the particular set of arrays you need to sort, in such a way that both arrays are sorted in-place, simultaneously.
Two sorting algorithms are provided. Quicksort is best when you only need to sort by a single column, as it requires very few comparisons and swaps. Mergesort is best used when sorting multiple columns, as it is a "stable" sort--that is, it does not affect the relative order of equal objects from previous sorts.
The mergesort algorithm here is an "in-place" variant, which while slower, does not require a temporary array.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) static class
ParallelSorter.ByteComparer
(package private) static class
ParallelSorter.ComparatorComparer
(package private) static interface
ParallelSorter.Comparer
(package private) static class
ParallelSorter.DoubleComparer
(package private) static class
ParallelSorter.FloatComparer
static class
ParallelSorter.Generator
(package private) static class
ParallelSorter.IntComparer
(package private) static class
ParallelSorter.LongComparer
(package private) static class
ParallelSorter.ObjectComparer
(package private) static class
ParallelSorter.ShortComparer
-
Field Summary
Fields Modifier and Type Field Description protected java.lang.Object[]
a
private ParallelSorter.Comparer
comparer
-
Constructor Summary
Constructors Modifier Constructor Description protected
ParallelSorter()
-
Method Summary
All Methods Static Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description private void
chooseComparer(int index, java.util.Comparator cmp)
protected int
compare(int i, int j)
static ParallelSorter
create(java.lang.Object[] arrays)
Create a new ParallelSorter object for a set of arrays.private int
len()
void
mergeSort(int index)
void
mergeSort(int index, int lo, int hi)
Sort the arrays using an in-place merge sort.void
mergeSort(int index, int lo, int hi, java.util.Comparator cmp)
Sort the arrays using an in-place merge sort.void
mergeSort(int index, java.util.Comparator cmp)
Sort the arrays using an in-place merge sort.abstract ParallelSorter
newInstance(java.lang.Object[] arrays)
void
quickSort(int index)
Sort the arrays using the quicksort algorithm.void
quickSort(int index, int lo, int hi)
Sort the arrays using the quicksort algorithm.void
quickSort(int index, int lo, int hi, java.util.Comparator cmp)
Sort the arrays using the quicksort algorithm.void
quickSort(int index, java.util.Comparator cmp)
Sort the arrays using the quicksort algorithm.-
Methods inherited from class net.sf.cglib.util.SorterTemplate
mergeSort, quickSort, swap
-
-
-
-
Field Detail
-
a
protected java.lang.Object[] a
-
comparer
private ParallelSorter.Comparer comparer
-
-
Method Detail
-
newInstance
public abstract ParallelSorter newInstance(java.lang.Object[] arrays)
-
create
public static ParallelSorter create(java.lang.Object[] arrays)
Create a new ParallelSorter object for a set of arrays. You may sort the arrays multiple times via the same ParallelSorter object.- Parameters:
arrays
- An array of arrays to sort. The arrays may be a mix of primitive and non-primitive types, but should all be the same length.loader
- ClassLoader for generated class, uses "current" if null
-
len
private int len()
-
quickSort
public void quickSort(int index)
Sort the arrays using the quicksort algorithm.- Parameters:
index
- array (column) to sort by
-
quickSort
public void quickSort(int index, int lo, int hi)
Sort the arrays using the quicksort algorithm.- Parameters:
index
- array (column) to sort bylo
- starting array index (row), inclusivehi
- ending array index (row), exclusive
-
quickSort
public void quickSort(int index, java.util.Comparator cmp)
Sort the arrays using the quicksort algorithm.- Parameters:
index
- array (column) to sort bycmp
- Comparator to use if the specified column is non-primitive
-
quickSort
public void quickSort(int index, int lo, int hi, java.util.Comparator cmp)
Sort the arrays using the quicksort algorithm.- Parameters:
index
- array (column) to sort bylo
- starting array index (row), inclusivehi
- ending array index (row), exclusivecmp
- Comparator to use if the specified column is non-primitive
-
mergeSort
public void mergeSort(int index)
- Parameters:
index
- array (column) to sort by
-
mergeSort
public void mergeSort(int index, int lo, int hi)
Sort the arrays using an in-place merge sort.- Parameters:
index
- array (column) to sort bylo
- starting array index (row), inclusivehi
- ending array index (row), exclusive
-
mergeSort
public void mergeSort(int index, java.util.Comparator cmp)
Sort the arrays using an in-place merge sort.- Parameters:
index
- array (column) to sort bylo
- starting array index (row), inclusivehi
- ending array index (row), exclusive
-
mergeSort
public void mergeSort(int index, int lo, int hi, java.util.Comparator cmp)
Sort the arrays using an in-place merge sort.- Parameters:
index
- array (column) to sort bylo
- starting array index (row), inclusivehi
- ending array index (row), exclusivecmp
- Comparator to use if the specified column is non-primitive
-
chooseComparer
private void chooseComparer(int index, java.util.Comparator cmp)
-
compare
protected int compare(int i, int j)
- Specified by:
compare
in classSorterTemplate
-
-