2
\$\begingroup\$

Given an unsorted array of integers \$A\$, the \$i\$th order statistic of \$A\$ is the \$i\$th smallest element of \$A\$. For example, \$0\$th order statistics of \$A\$ is the minimum of \$A\$; \$(|A| - 1)\$th order statistics of \$A\$ is the maximum of \$A\$; \$1\$th order statistics is the second smallest element, and so on.

OrderStatistics.java

package net.coderodde.stat;

import java.util.Random;

public final class OrderStatistics {

    private OrderStatistics() {}

    /**
     * Returns the {@code order}th order statistics of the array {@code array}. 
     * If {@code order == 0}, returns the minimum element; if 
     * {@code order == 1}, returns the second smallest element, and so on.
     * 
     * @param array the array to search.
     * @param order the order of the element to search. 
     * @return the <code>order</code>th smallest element.
     */
    public static int randomizedSelect(int[] array, int order) {
        checkOrder(order, array);
        Random random = new Random();
        return randomizedSelect(array, 0, array.length - 1, order + 1, random);
    }

    /**
     * Checks that the requested order is within array bounds.
     * 
     * @param order the order to check.
     * @param array the array to search.
     */
    private static void checkOrder(int order, int[] array) {
        if (order < 0) {
            throw new IndexOutOfBoundsException("Negative order: " + order);
        }

        if (order >= array.length) {
            throw new IndexOutOfBoundsException(
                    "Order is too large (" + order + "). Must be at most " +
                    (array.length - 1) + ".");
        }
    }

    /**
     * Performs a randomized selection of an element with order {@code order}.
     * 
     * @param array      the array holding the range to search.
     * @param startIndex the index of the leftmost element of the array range.
     * @param endIndex   the index of the rightmost element of the array range.
     * @param order      the requested order.
     * @param random     the random number generator.
     * 
     * @return the <code>order</code>th smallest element.
     */
    private static int randomizedSelect(int[] array,
                                        int startIndex,
                                        int endIndex,
                                        int order,
                                        Random random) {
        if (startIndex == endIndex) {
            return array[startIndex];
        }

        int pivotIndex = randomizedPartition(array,
                                             startIndex, 
                                             endIndex, 
                                             random);
        int k = pivotIndex - startIndex + 1;

        if (order == k) {
            return array[pivotIndex];
        } else if (order < k) {
            return randomizedSelect(array, 
                                    startIndex, 
                                    pivotIndex - 1, 
                                    order, 
                                    random);
        } else {
            return randomizedSelect(array,
                                    pivotIndex + 1,
                                    endIndex,
                                    order - k,
                                    random);
        }
    }

    private static int randomizedPartition(int[] array,
                                           int startIndex,
                                           int endIndex,
                                           Random random) {
        int rangeLength = endIndex - startIndex + 1;
        int i = startIndex + random.nextInt(rangeLength);
        swap(array, endIndex, i);
        return partition(array, startIndex, endIndex);
    }

    private static int partition(int[] array, int startIndex, int endIndex) {
        int pivot = array[endIndex];
        int i = startIndex - 1;

        for (int j = startIndex; j < endIndex; ++j) {
            if (array[j] <= pivot) {
                i++;
                swap(array, i, j);
            }
        }

        swap(array, i + 1, endIndex);
        return i + 1;
    }

    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

Demo.java

package net.coderodde.stat;

import java.util.Arrays;
import java.util.Random;

public class Demo {

    private static final int WARMUP_LENGTH = 100_000;
    private static final int WARMUP_ITERATIONS = 500;
    private static final int ARRAY_LENGTH = 50_000_000;

    public static void main(String[] args) {
        long seed = System.currentTimeMillis();
        Random random = new Random(seed);

        warmup(random);

        int[] array = getRandomIntArray(ARRAY_LENGTH, random);
        System.out.println("Seed = " + seed);

        long startTime = System.currentTimeMillis();
        int median1 = OrderStatistics.randomizedSelect(array, ARRAY_LENGTH / 2);
        long endTime = System.currentTimeMillis();

        System.out.println("OrderStatistics.randomizedSelect() in " +
                           (endTime - startTime) + " milliseconds.");

        startTime = System.currentTimeMillis();
        Arrays.sort(array);
        int median2 = array[ARRAY_LENGTH / 2];
        endTime = System.currentTimeMillis();

        System.out.println("Selection via sorting in " + (endTime - startTime) +
                           " milliseconds.");

        if (median1 != median2) {
            System.err.println("Algorithms disagree: " + median1 + " vs. " +
                               median2);
        } else {
            System.out.println("Algorithms agree: " + median1);
        }
    }

    private static void warmup(Random random) {
        System.out.println("Warming up...");

        for (int iteration = 0; iteration < WARMUP_ITERATIONS; ++iteration) {
            int[] array = getRandomIntArray(WARMUP_LENGTH, random);
            OrderStatistics.randomizedSelect(array, 
                                             random.nextInt(WARMUP_LENGTH));
            Arrays.sort(array);
        }

        System.out.println("Warming up done!");
    }

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

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

        return array;
    }
}

Performance figures

Upon running the demonstration, I get something like:

Seed = 1483720011710
OrderStatistics.randomizedSelect() in 862 milliseconds.
Selection via sorting in 5292 milliseconds.
Algorithms agree: 500129

Critique request

Please tell me anything that comes to mind.

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

Your benchmarking code is inaccurate as it does not include a warmup phase to let the JIT compiler optimize the code prior to the benchmark.

You should use a benchmarking tool like µbench or at least abide by the guide lines in this question.

Also because your algorithm uses random numbers you need to multiple trials with different seeds to get a better idea of the average behaviour. And also look at the standard deviation of the timings.

I'll get back to the rest of the code later when I'm not dead tired. :)

\$\endgroup\$
2
  • \$\begingroup\$ I know how to warm up the JVM, but I am pretty sure that the randomized selector won't magically become less efficient than the trivial sorting algorithm. :) \$\endgroup\$
    – coderodde
    Jan 6, 2017 at 17:00
  • \$\begingroup\$ Added warming up the JVM, if you don't mind (yet). \$\endgroup\$
    – coderodde
    Jan 6, 2017 at 17:07

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.