use of nextAfter(double start, double direction); in Android

Question

I am in need of assistance. I will be computing a measured variable, then taking the top 100 values of these and averaging them. Please remember, I have been teaching myself only for the past 6 weeks and what is obvious to some, will not necessarily be obvious to me.

In essence, say 'double x' is the variable, that I have many close values for. What I need is a way to compute the sum (then average) of the top 100 of these values.

In my research, the closest thing I can see that would suit what I need is 'nextAfter(double start, double direction); and before this, using 'max' to determine the maximum value, would this be the correct starting point:

double xm = max(x); static double (xm, x < xm);

My question is how to get the sum of the top 100 values (the maximum and 99 nextAfter's) - averaging would be easy - just dividing by 100.

Answer 1

To compute the average of the largest n values you read from the source, you need to store at least these values. Since at any given point before the end you don't know whether some of the largest n values overall will come later, you need to keep track the largest n values seen so far.

A simple way to do that is to store the largest values in a heap or priority queue, since that allows easy adding of new values and finding (and removing) of the smallest of the stored values. The default PriorityQueue is well-suited for this task, since it uses the natural ordering of the elements, and thus polling removes the smallest of the stored elements. If one wanted to compute the average of the n smallest elements, one would need to use a PriorityQueue with a custom Comparator (or in this special case, simply negating all values and using the natural ordering would work too).

The lazy way (less code) to achieve the desired is to simply add each incoming value to the queue, and if the queue's size exceeds n [then it must be n+1] remove the smallest element from the queue:

// vp is the value provider
while(vp.hasNext()) {
    // read the next value and add it to the queue
    pq.add(vp.nextValue());
    if (pq.size() > topSize) {
        pq.poll();
    }

A slightly more involved way is to first check whether the new value needs to be added, and only modify the queue when that is the case,

double newValue = vp.nextValue();
// Check if we have to put the new value in the queue
// that is the case when the queue is not yet full, or the smallest
// stored value is smaller than the new
if (pq.size() < topSize || pq.peek() < newValue) {
    // remove the smallest value from the queue only if it is full
    if (pq.size() == topSize()) {
        pq.poll();
    }
    pq.add(newValue);
}

This way is potentially more efficient, since adding a value to the queue and removing the smallest are both O(log size) operations, while comparing to the smallest stored value is O(1). So if there are many values smaller than the n largest seen before, the second way saves some work.

If performance is critical, be aware that a PriorityQueue cannot store primitive types like double, so the storing (and retrieving for the average computation) involves boxing (wrapping a double value in a Double object) resp. unboxing (pulling the double value from a Double object), and consequently an indirection from the underlying array of the queue to the actual values. Those costs could be avoided by implementing a heap-based priority queue using a raw double[] yourself. (But that should rarely be necessary, usually, the cost of the boxing and indirections would constitute only a minute part of the overall processing.)

A simple-minded complete working example:

import java.util.PriorityQueue;

/**
 * Example class to collect the largest values from a stream and compute their
 * average.
 */
public class Average {
    // number of values we want to save
    private int topSize;
    // number of values read so far
    private long count = 0;
    // priority queue to save the largest topSize values
    private PriorityQueue<Double> pq;
    // source of read values, could be a file reader, a device reader, or whatever
    private ValueProvider vp;

    /**
     * Construct an <code>Average</code> to sample the largest <code>n</code>
     * values from the source.
     *
     * @param tops Number of values to save for averaging.
     * @param v Source of the values to sample.
     *
     * @throws IllegalArgumentException when the specified number of values is less than one.
     */
    public Average(int tops, ValueProvider v) throws IllegalArgumentException {
        if (tops < 1) {
            throw new IllegalArgumentException("Can't get average of fewer than one values.");
        }
        topSize = tops;
        vp = v;
        // Initialise queue to needed capacity; topSize + 1, since we first add
        // and then poll. Thus no resizing should ever be necessary.
        pq = new PriorityQueue<Double>(topSize+1);
    }

    /**
     * Compute the average of the values stored in the <code>PriorityQueue<Double></code>
     *
     * @param prio The queue to average.
     * @return the average of the values stored in the queue.
     */
    public static double average(PriorityQueue<Double> prio) throws IllegalArgumentException {
        if (prio == null || prio.size() == 0) {
            throw new IllegalArgumentException("Priority queue argument is null or empty.");
        }
        double sum = 0;
        for(Double d : prio) {
            sum += d;
        }
        return sum/prio.size();
    }

    /**
     * Reads values from the provider until exhausted, reporting the average
     * of the largest <code>topSize</code> values read so far from time to time
     * and when the source is exhausted.
     */
    public void collectAverage() {
        while(vp.hasNext()) {
            // read the next value and add it to the queue
            pq.add(vp.nextValue());
            ++count;
            // If the queue was already full, we now have
            // topSize + 1 values in it, so we remove the smallest.
            // That is, conveniently, what the default PriorityQueue<Double>
            // gives us. If we wanted for example the smallest, we'd need
            // to use a PriorityQueue with a custom Comparator (or negate
            // the values).
            if (pq.size() > topSize) {
                pq.poll();
            }
            // Occasionally report the running average of the largest topSize
            // values read so far. This may not be desired.
            if (count % (topSize*25) == 0 || count < 11) {
                System.out.printf("Average of top %d values after collecting %d is %f\n",
                                   pq.size(), count, average(pq));
            }
        }
        // Report final average. Returning the average would be a natural choice too.
        System.out.printf("Average of top %d values of %d total is %f\n",
                           pq.size(), count, average(pq));
    }

    public static void main(String[] args) {
        Average a = new Average(100, new SimpleProvider(123456));
        a.collectAverage();
    }
}

using the interface

/**
 * Interface for a source of <code>double</code>s.
 */
public interface ValueProvider {
    /**
     * Gets the next value from the source.
     *
     * @return The next value if there is one.
     * @throws RuntimeException if the source is exhausted.
     */
    public double nextValue() throws RuntimeException;

    /**
     * Checks whether the source has more values to deliver.
     *
     * @return whether there is at least one more value to be obtained from the source.
     */
    public boolean hasNext();
}

and implementing class

/**
 * Simple provider of a stream of <code>double</code>s.
 */
public class SimpleProvider implements ValueProvider {
    // State determining which value to return next.
    private long state = 0;
    // Last allowed state.
    private final long end;

    /**
     * Construct a provider of <code>e</code> values.
     *
     * @param e the number of values to yield.
     */
    public SimpleProvider(long e) {
        end = e > 0 ? e : 0;
    }

    /**
     * Default constructor to provide 10000 values.
     */
    public SimpleProvider() {
        this(10000);
    }

    public double nextValue() {
        ++state;
        return Math.log(state)*Math.sin(state) + Math.cos(state/2.0);
    }

    public boolean hasNext() {
        return state < end;
    }
}