Package elki.database.ids

Class QuickSelectDBIDs

java.lang.Object

elki.database.ids.QuickSelectDBIDs

public final class QuickSelectDBIDs
extends java.lang.Object

QuickSelect computes ("selects") the element at a given rank and can be used to compute Medians and arbitrary quantiles by computing the appropriate rank.

This algorithm is essentially an incomplete QuickSort that only descends into that part of the data that we are interested in, and also attributed to Charles Antony Richard Hoare

Since:

0.7.5

Author:

Erich Schubert

Field Summary

Fields

Modifier and Type	Field	Description
private static int	SMALL	For small arrays, use a simpler method:

Constructor Summary

Constructors

Modifier	Constructor	Description
private	QuickSelectDBIDs()	Do not instantiate - static methods only!

Method Summary

Modifier and Type	Method	Description
private static int	bestPivot(int rank, int m1, int m2, int m3, int m4, int m5)	Choose the best pivot for the given rank.
private static void	insertionSort(ArrayModifiableDBIDs data, java.util.Comparator<? super DBIDRef> comparator, int start, int end, DBIDArrayIter iter1, DBIDArrayIter iter2)	Sort a small array using repetitive insertion sort.
private static void	insertionSort(ModifiableDoubleDBIDList data, int start, int end, DoubleDBIDListIter iter1, DoubleDBIDListIter iter2)	Sort a small array using repetitive insertion sort.
static int	median(ArrayModifiableDBIDs data, java.util.Comparator<? super DBIDRef> comparator)	Compute the median of an array efficiently using the QuickSelect method.
static int	median(ArrayModifiableDBIDs data, java.util.Comparator<? super DBIDRef> comparator, int begin, int end)	Compute the median of an array efficiently using the QuickSelect method.
static int	median(ModifiableDoubleDBIDList data)	Compute the median of an array efficiently using the QuickSelect method.
static int	median(ModifiableDoubleDBIDList data, int begin, int end)	Compute the median of an array efficiently using the QuickSelect method.
static int	quantile(ArrayModifiableDBIDs data, java.util.Comparator<? super DBIDRef> comparator, double quant)	Compute the median of an array efficiently using the QuickSelect method.
static int	quantile(ArrayModifiableDBIDs data, java.util.Comparator<? super DBIDRef> comparator, int begin, int end, double quant)	Compute the median of an array efficiently using the QuickSelect method.
static int	quantile(ModifiableDoubleDBIDList data, double quant)	Compute the median of an array efficiently using the QuickSelect method.
static int	quantile(ModifiableDoubleDBIDList data, int begin, int end, double quant)	Compute the median of an array efficiently using the QuickSelect method.
static void	quickSelect(ArrayModifiableDBIDs data, java.util.Comparator<? super DBIDRef> comparator, int rank)	QuickSelect is essentially quicksort, except that we only "sort" that half of the array that we are interested in.
static void	quickSelect(ArrayModifiableDBIDs data, java.util.Comparator<? super DBIDRef> comparator, int start, int end, int rank)	QuickSelect is essentially quicksort, except that we only "sort" that half of the array that we are interested in.
static void	quickSelect(ModifiableDoubleDBIDList data, int rank)	QuickSelect is essentially quicksort, except that we only "sort" that half of the array that we are interested in.
static void	quickSelect(ModifiableDoubleDBIDList data, int start, int end, int rank)	QuickSelect is essentially quicksort, except that we only "sort" that half of the array that we are interested in.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

SMALL

private static final int SMALL

For small arrays, use a simpler method:

See Also:

Constant Field Values

Constructor Detail

QuickSelectDBIDs

private QuickSelectDBIDs()

Do not instantiate - static methods only!

Method Detail

bestPivot

private static int bestPivot(int rank,
                             int m1,
                             int m2,
                             int m3,
                             int m4,
                             int m5)

Choose the best pivot for the given rank.

Parameters:

rank - Rank

m1 - Pivot candidate

m2 - Pivot candidate

m3 - Pivot candidate

m4 - Pivot candidate

m5 - Pivot candidate

Returns:

Best pivot candidate

quickSelect

public static void quickSelect(ArrayModifiableDBIDs data,
                               java.util.Comparator<? super DBIDRef> comparator,
                               int rank)

QuickSelect is essentially quicksort, except that we only "sort" that half of the array that we are interested in. Note: the array is modified by this.

Parameters:

data - Data to process

comparator - Comparator to use

rank - Rank position that we are interested in (integer!)

median

public static int median(ArrayModifiableDBIDs data,
                         java.util.Comparator<? super DBIDRef> comparator)

Compute the median of an array efficiently using the QuickSelect method.

Note: the array is modified by this.

Parameters:

data - Data to process

comparator - Comparator to use

Returns:

Median position

median

public static int median(ArrayModifiableDBIDs data,
                         java.util.Comparator<? super DBIDRef> comparator,
                         int begin,
                         int end)

Compute the median of an array efficiently using the QuickSelect method.

On an odd length, it will return the lower element.

Note: the array is modified by this.

Parameters:

data - Data to process

comparator - Comparator to use

begin - Begin of valid values

end - End of valid values (exclusive!)

Returns:

Median position

quantile

public static int quantile(ArrayModifiableDBIDs data,
                           java.util.Comparator<? super DBIDRef> comparator,
                           double quant)

Compute the median of an array efficiently using the QuickSelect method.

Note: the array is modified by this.

Parameters:

data - Data to process

comparator - Comparator to use

quant - Quantile to compute

Returns:

Quantile position

quantile

public static int quantile(ArrayModifiableDBIDs data,
                           java.util.Comparator<? super DBIDRef> comparator,
                           int begin,
                           int end,
                           double quant)

Compute the median of an array efficiently using the QuickSelect method.

It will prefer the lower element.

Note: the array is modified by this.

Parameters:

data - Data to process

comparator - Comparator to use

begin - Begin of valid values

end - End of valid values (exclusive)

quant - Quantile to compute

Returns:

Quantile position

quickSelect

public static void quickSelect(ArrayModifiableDBIDs data,
                               java.util.Comparator<? super DBIDRef> comparator,
                               int start,
                               int end,
                               int rank)

QuickSelect is essentially quicksort, except that we only "sort" that half of the array that we are interested in.

Parameters:

data - Data to process

comparator - Comparator to use

start - Interval start

end - Interval end (exclusive)

rank - rank position we are interested in (starting at 0)

insertionSort

private static void insertionSort(ArrayModifiableDBIDs data,
                                  java.util.Comparator<? super DBIDRef> comparator,
                                  int start,
                                  int end,
                                  DBIDArrayIter iter1,
                                  DBIDArrayIter iter2)

Sort a small array using repetitive insertion sort.

Parameters:

data - Data to sort

start - Interval start

end - Interval end

quickSelect

public static void quickSelect(ModifiableDoubleDBIDList data,
                               int rank)

QuickSelect is essentially quicksort, except that we only "sort" that half of the array that we are interested in.

Note: the array is modified by this.

Parameters:

data - Data to process

rank - Rank position that we are interested in (integer!)

median

public static int median(ModifiableDoubleDBIDList data)

Compute the median of an array efficiently using the QuickSelect method.

Note: the array is modified by this.

Parameters:

data - Data to process

Returns:

Median position

median

public static int median(ModifiableDoubleDBIDList data,
                         int begin,
                         int end)

Compute the median of an array efficiently using the QuickSelect method.

On an odd length, it will return the lower element.

Note: the array is modified by this.

Parameters:

data - Data to process

begin - Begin of valid values

end - End of valid values (exclusive!)

Returns:

Median position

quantile

public static int quantile(ModifiableDoubleDBIDList data,
                           double quant)

Compute the median of an array efficiently using the QuickSelect method.

Note: the array is modified by this.

Parameters:

data - Data to process

quant - Quantile to compute

Returns:

Quantile position

quantile

public static int quantile(ModifiableDoubleDBIDList data,
                           int begin,
                           int end,
                           double quant)

Compute the median of an array efficiently using the QuickSelect method.

It will prefer the lower element.

Note: the array is modified by this.

Parameters:

data - Data to process

begin - Begin of valid values

end - End of valid values (exclusive)

quant - Quantile to compute

Returns:

Quantile position

quickSelect

public static void quickSelect(ModifiableDoubleDBIDList data,
                               int start,
                               int end,
                               int rank)

QuickSelect is essentially quicksort, except that we only "sort" that half of the array that we are interested in.

Parameters:

data - Data to process

start - Interval start

end - Interval end (exclusive)

rank - rank position we are interested in (starting at 0)

insertionSort

private static void insertionSort(ModifiableDoubleDBIDList data,
                                  int start,
                                  int end,
                                  DoubleDBIDListIter iter1,
                                  DoubleDBIDListIter iter2)

Sort a small array using repetitive insertion sort.

Parameters:

data - Data to sort

start - Interval start

end - Interval end