Algorithms to find statistical information of an array

Question

I was working on a program that creates an array, then gives statistical information about that array such as std dev, median, mode average etc.

I have written a method for each statistical value, however I am not too sure that they are efficient, particularly the getMode() method.

I would be really happy if you helped me to make these methods memory efficient and fast as possible. Thanks, here are my methods:

private static int getMode(int[] x) {

    int max_mode = 0;
    int count = 0, count_max = 0;
    for (int i = 0; i < x.length; i++) {
        for (int j = 0; j < x.length; j++) {
            if (x[i] == x[j]) {
                count++;
            }
        }
        if (count >= count_max) {
            count_max = count;
            max_mode = x[i];
        }
        count = 0;
    }
    return max_mode;
}

private static double getMedian(int[] x) {
    int[] sorted = x;
    sort(sorted);
    double median;
    if (sorted.length % 2 == 0) {
        median = sorted[(sorted.length / 2 - 1 + sorted.length / 2) / 2];
        median += 0.5;
    } else {
        median = sorted[sorted.length / 2];
    }

    return median;

}

private static int[] sort(int[] x) {
    int temp;
    int[] sorted = x;
    for (int i = 1; i < sorted.length; i++) {
        for (int j = 0; j < sorted.length; j++) {
            if (sorted[i] < sorted[j]) {
                temp = sorted[i];
                sorted[i] = sorted[j];
                sorted[j] = temp;
            }
        }
    }
    return sorted;
}

private static double getAverage(int[] x) {
    double sum = 0;
    double avg;
    for (int i = 0; i < x.length; i++) {
        sum += x[i];
    }
    avg = sum / x.length;
    return avg;

}

private static int getSum(int[] x) {
    int sum = 0;
    for (int i = 0; i < x.length; i++) {
        sum += x[i];
    }
    return sum;
}

private static int getMax(int[] x) {
    int tempmax = 0, realmax = 0;
    for (int i = 0; i < x.length; i++) {
        for (int j = 0; j < x.length; j++) {
            if (x[i] > x[j]) {
                tempmax = x[i];
            }

        }
        if (tempmax > realmax) {
            realmax = tempmax;
        }
        tempmax = 0;
    }
    return realmax;
}

private static int getMin(int[] x) {
    int templow = 0, reallow = 0;
    for (int i = 0; i < x.length; i++) {
        for (int j = 0; j < x.length; j++) {
            if (x[i] < x[j]) {
                templow = x[i];
            }
        }
        if (templow <= reallow) {
            reallow = templow;
        }
        templow = 0;
    }
    return reallow;
}

private static double getStdDev(int[] x) {
    double sum = 0;
    double avg = getAverage(x);
    for (int i = 0; i < x.length; i++) {
        sum += (x[i] - avg) * (x[i] - avg);
    }
    return Math.sqrt(sum / (x.length - 1));
}

Answer 1

Glaring Deficiencies

1. Let me venture here that your getMedian method is slower than your getMode method. Thanks to your sort. You use a naive bubble-sort, which is \$O(n^2)\$. It can be done using \$O(n\log(n))\$ using quicksort (for practical input), mergesort, heapsort, etc. However, you can get the best of all worlds by just using the static method sort() from java.util.Arrays. It will get you an implementation of mergesort or Timsort, both very fast compared to bubble sort.

2. About getAverage. You recalculate the sum in a loop where you already have a getSum method. Use that.

3. You have really inconsistent return types in some places, especially getSum and getMedian.

4. In getMedian, int[] sorted = x; probably doesn't do what you want it to do, which is create a copy of the argument array which you can sort. Try using int[] sorted = Arrays.copyOf(x, x.length); instead, which will do the required deep copy instead of a reference assignment.

I disagree with @coderodde's approach. You should get what you ask for when computing statistics. You should not incur costs which you do not deserve. That is, if you want to get the average of all the elements in an array, you should not have to pay the overhead of sorting it and calculating the median.

Algorithmic improvements

1. In getMin and getMax, set the default value of the accumulator variable to the first element of the array, i.e., arr[0], and start the loop at 1 instead of 0. It makes more sense. Or, better, use Streams, they have these methods in-built.

2. Use @coderodde's idea for calculating mode, as that is \$O(n+n\log(n)) = O(n\log(n))\$, whereas yours is currently \$O(n^2)\$ in the worst case. That is, his way is faster.

   Note, however, that your mode calculation algorithm is a bit problematic; for an input set {1, 1, 2, 4, 4}, your code will return 4, though for a multimodal set it would be mathematically appropriate to return the first mode, i.e., 1 here.

   I have managed to fashion a faster approach to the problem, involving only partially sorting and partitioning the array, however, this works correctly only for unimodal sets (and works in a mathematically correct fashion for multimodal sets). I use the naive approach to get all the modes of a multimodal set.

   In my code it appears that I need \$O(n)\$ additional space due to the Set<Mode> used for maintaining multimodal data, but for unimodal data, this is unnecessary and it can be made to work in \$O(n\log(n))\$ time and \$O(1)\$ additional space.

   I make both pieces of code return a double[] (in the former case, a single-element array even for multimodal sets), for API consistency.

3. Use a selection algorithm, such as the Floyd-Rivest Algorithm for calculating the median in linear time, instead of the best-case \$O(n\log(n))\$ when using sorting.

4. Use a numerically stable one-pass algorithm like Welford's Method to get the variance / standard deviation.

Ideas

1. You should name getAverage to getArithmeticMean, as that is the more appropriate statistical term here.

2. As regards the above, you could try implementing a getGeometricMean, which would be calculated as follows:

   \$GM = \sqrt[n]{\prod\limits_{i=1}^n x_i}\$

   Or, the \$n\$th root of the product of \$n\$ numbers.

Suggestions

1. Java 8's Streams would help a lot here.

2. Declare your method parameters final. That way, the caller will not have to worry about you changing their data out from under their feet (it's not especially helpful with arrays, but even so).

3. Try using the for-each loop where you don't need explicit indexing, rather just the elements in sequence, e.g. in getMode.

4. Try to fail-fast: throw exceptions when you encounter exceptional conditions, like being supplied an empty array (java.util.NoSuchElementException seems to be a good fit for this use case).

New Code:

Note that this is not one of the best examples when it comes to coding in Java, but take a look at it anyway (there are comments when the going gets tough). There are usually 2 versions of each method, one utilizing your original idea, the other utilizing a faster algorithm. The naive versions have UnOpt suffixed to their names. Except in the case of getMode as noted above, both versions are semantically equivalent. In case of the Floyd-Rivest algorithm used in select, there are some magic numbers, you can look at the linked Wikipedia article for details.

import java.util.*;
import java.util.stream.*;
import static java.lang.Math.*;
public class Stats{
    private static double[] unbox(Collection<Double> collection){
        return collection.stream().mapToDouble(Double::doubleValue).toArray();
    }

    public static double[] getModesUnOpt(final double[] x) {
        Set<Double> modes = new HashSet<>(x.length);
        long count = 0, countMax = 0;
        for (final double v : x) {
            count = Arrays.stream(x).filter(y -> y == v).count();
            if (count >= countMax) {
                if(count > countMax){
                    countMax = count;
                    modes.clear();
                }
                modes.add(v);
            }
            count = 0;
        }
        return unbox(modes);
    }

    public static double getModeUnOpt(final double[] x) {
        return getModes(x)[0];
    }

    private static class Mode{
        public double Value = 0.0;
        public int Count = 0;
    }

    public static class Pair<L, R>{
        public final L left;
        public final R right;
        public Pair(L left, R right){
            this.left = left;
            this.right = right;
        }
    }

    public static double getMode(final double[] x){
        return getModes(x)[0];
    }

    public static double[] getModes(final double[] x){
        return findModePartialSortRecursive(x, 0, x.length, new Mode(), new HashSet<>()).right.stream().mapToDouble(y -> y.Value).toArray();
    }

    private static Pair<Mode, Set<Mode>> findModePartialSortRecursive(final double[] array, int begin, int end, Mode best, Set<Mode> modes){
        int pivotIndex = (int) (begin + (random() * (end - begin)));
        Mode mode = best;
        double pivot = array[pivotIndex];
        int left = begin, right = end - 1, pos = left;
        Pair<Mode, Set<Mode>> data = new Pair<>(best, modes);
        while (pos <= right){
            if (array[pos] < pivot){
                array[left++] = array[pos++];
            }
            else if (array[pos] > pivot){
                swap(array, right, pos);
                --right;
            }
            else{
                ++pos;
            }
        }
        int pivotCount = right - left + 1;
        for (int i = left; i <= right; i++){
            array[i] = pivot;
        }
        if (pivotCount >= mode.Count){
            if(pivotCount > mode.Count){
                mode.Value = pivot;
                mode.Count = pivotCount;
            }
            modes.add(mode);
            data.left = mode;
            data.right = modes;
        }      
        int leftCount = left - begin;
        if (leftCount > mode.Count){
            data = findModePartialSortRecursive(array, begin, left, mode, modes);
        }
        int rightCount = end - right - 1;
        if (rightCount > mode.Count){
            data = findModePartialSortRecursive(array, right + 1, end, mode, modes);
        }
        return data;
    }

    public static void swap(double[] array, int i, int j){
        double temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * Uses the Floyd-Rivest Algorithm for a quickselect with median-optimized pivot selection.
     * Modifies the input array such that <code>array[k]</code> is the (k - left + 1)th smallest element in the array.
     */
    public static double select(double[] array, int left, int right, int k){
        while(right > left){
            // use select recursively to sample a smaller set of size s
            // the arbitrary constants 600 and 0.5 are used in the original
            // version to minimize execution time
            if(right - left > 600){
                double n = right - left + 1;
                double i = k - left + 1;
                double z = log(n);
                double s = 0.5 * exp(2.0 * z/3.0);
                double sd = 0.5 * sqrt(z * s * (n - s)/n) * signum(i - n/2);
                int newLeft = (int)max(left, k - i * s/n + sd);
                int newRight = (int)min(right, k + (n - i) * s/n + sd);
                select(array, newLeft, newRight, k);
            }
            // partition the elements between left and right around t
            double t = array[k];
            int i = left;
            int j = right;
            swap(array, left, k);
            if(array[right] > t){
                swap(array, right, left);
            }
            while(i < j){
                swap(array, i, j);
                ++i;
                --j;
                while(array[i] < t){
                    ++i;
                }
                while(array[j] > t){
                    --j;
                }
            }
            if(array[left] == t){
                swap(array, left, j);
            }
            else{
                ++j;
                swap(array, j, right);
            }
            // adjust left and right towards the boundaries of the subset
            // containing the (k - left + 1)th smallest element
            if(j <= k){
                left = j + 1;
            }
            if(k <= j){
                right = j - 1;
            }
        }
        return array[k];
    }

    public static double getMedian(final double[] x){
        if(x.length == 0){
            throw new NoSuchElementException("Median of an empty array cannot be found");
        }
        int halfLength = x.length / 2, endIndex = x.length - 1;
        //calculate a generic median
        double median = select(Arrays.copyOf(x, x.length), 0, endIndex, halfLength);
        if((x.length % 2) == 1){
            //length is odd, only 1 middle element to consider
            return median;
        }
        //length is even, 2 median elemnts to consider.
        return (median + select(Arrays.copyOf(x, x.length), 0, endIndex, halfLength - 1)) / 2.0;
    }

    public static double getMedianUnOpt(final double[] x) {
        if(x.length == 0){
            throw new NoSuchElementException("Median of an empty array cannot be found");
        }
        double[] sorted = Arrays.copyOf(x, x.length);
        Arrays.sort(sorted);
        double median;
        if (sorted.length % 2 == 0) {
            //length is even, 2 median elemnts to consider.
            median = sorted[(sorted.length / 2 - 1 + sorted.length / 2) / 2] + 0.5;
        } else {
            //length is odd, only 1 middle element to consider
            median = sorted[sorted.length / 2];
        }
        return median;
    }

    public static double getArithmeticMean(final double[] x) {
        return Arrays.stream(x).average().getAsDouble();
    }

    public static double getGeometricMean(final double[] x) {
        return Arrays.stream(x).reduce((a, b) -> a * b).getAsDouble();
    }

    public static double getSum(final double[] x) {
        return Arrays.stream(x).sum();
    }

    public static double getMin(final double[] x){
        return Arrays.stream(x).min().getAsDouble();
    }

    public static double getMax(final double[] x){
        return Arrays.stream(x).max().getAsDouble();
    }

    /**
     * Uses Welford's method for calculating variance in 1 pass.
     */
    public static double getVariance(final double[] x){
        if(x.length == 0){
            throw new NoSuchElementException("Variance of an empty array cannot be found");
        }
        int n = 0;
        double mean = 0.0, M2 = 0.0;
        for(double y : x){
            ++n;
            double delta = y - mean;
            mean += delta / n;
            M2 += delta * (y - mean);
        } 
        return M2 / (n - 1);
    }

    public static double getStandardDeviation(final double[] x){
        if(x.length == 0){
            throw new NoSuchElementException("Standard Deviation of an empty array cannot be found");
        }
        return sqrt(getVariance(x));
    }

    public static double getStandardDeviationUnOpt(final double[] x) {
        if(x.length == 0){
            throw new NoSuchElementException("Standard Deviation of an empty array cannot be found");
        }
        double sumDiffs = 0;
        double avg = getArithmeticMean(x);
        for (int i = 0; i < x.length; i++) {
            sumDiffs += (x[i] - avg) * (x[i] - avg);
        }
        return sqrt(sumDiffs / (x.length - 1));
    }
}

Answer 2

Advice 1

You sort the array in any case since you use it to find the median. Since the data is sorted eventually, you can find mode in \$\Theta(N)\$.

Advice 2

I would define a class that holds all the statistics (minimum, average, sum, mode, median, average, standard deviation). Also, note that it is possible to compute the s.d. without explicitly computing the average first (see comments in my code).

Summa summarum

All in all, I had this in mind:

import java.util.Arrays;

public class Statistics {

    private final int min;
    private final int max;
    private final int sum;
    private final int mode;
    private final double median;
    private final double average;
    private final double standardDeviation;

    private Statistics(int min, 
                       int max,
                       int sum,
                       int mode,
                       double median,
                       double average,
                       double standardDeviation) {
        this.min = min;
        this.max = max;
        this.sum = sum;
        this.mode = mode;
        this.median = median;
        this.average = average;
        this.standardDeviation = standardDeviation;
    }

    // Perhaps getters here.

    @Override
    public String toString() {
        return "(min=" + min + ", max=" + max + ", sum=" + sum + 
               ", mode=" + mode + ", median=" + median +
               ", average=" + average + ", s.d.=" + standardDeviation + ")";
    }

    public static Statistics process(int[] data) {
        if (data.length == 0) {
            throw new IllegalArgumentException("The input array is empty.");
        }

        int[] copy = data.clone(); // Copy, keep 'data' intact.
        Arrays.sort(copy);

        int min = copy[0];
        int max = copy[copy.length - 1];
        double median;

        if (copy.length % 2 == 0) {
            int index = copy.length / 2;
            median = 0.5 * (copy[index] + copy[index - 1]);
        } else {
            median = copy[copy.length / 2];
        }

        int sum = 0;
        int sumSquared = 0;

        for (int element : copy) {
            sum += element;
            sumSquared += element * element;
        }

        double average = 1.0 * sum / copy.length;
        double standardDeviation = computeStandardDeviation(sum,
                                                            sumSquared,
                                                            copy.length);
        int mode = computeMode(copy);
        return new Statistics(min,
                              max,
                              sum,
                              mode,
                              median,
                              average,
                              standardDeviation);
    }

    private static double computeStandardDeviation(int sum, 
                                                   int sumSquared,
                                                   int length) {
        // This trickery is described here:
        // https://coderodde.wordpress.com/2016/04/12/computing-standard-deviation-in-one-pass/
        double body = sumSquared - 1.0 * sum * sum / length;
        return Math.sqrt(body / (length - 1.0));
    }

    private static int computeMode(int[] array) {
        int tentativeMode = array[0];
        int tentativeModeLength = 1;
        int mode = array[0];
        int modeLength = 1;

        for (int i = 1; i < array.length; ++i) {
            int element = array[i];

            if (tentativeMode == element) {
                tentativeModeLength++;

                if (modeLength < tentativeModeLength) {
                    modeLength = tentativeModeLength;
                    mode = tentativeMode;
                }
            } else {
                tentativeMode = element;
                tentativeModeLength = 1;
            }
        }

        return mode;
    }

    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 5, 2 };
        System.out.println(process(arr));
    }
}

Hope that helps.