2
\$\begingroup\$

(See the next iteration.)

This question is an elaboration of my question. Just like the previous implementation, all operations (except clear) run in exact or amortized constant time.

I have taken into account all points made by @Emily L., and my data structure looks like this:

StatisticsNumberSet.java

package net.coderodde.stat;

import java.util.HashMap;
import java.util.Map;

/**
 * This class aims for providing the user insertion, removal and statistics 
 * query operations, all in exact or amortized constant time. While adding a
 * number runs in amortized constant time, deletion and query operations run in
 * exact constant time. The query operations are size of the set, its average 
 * value, and its standard deviation.
 * <p>
 * The name <i>set</i> is a bit misleading: this data structure allows
 * duplicate values and keeps track of them via a histogram (this is a 
 * multiset).
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.61 (Mar 27, 2017)
 */
public class StatisticsNumberSet {

    private double sum;
    private double squareSum;
    private int numberOfElements;
    private final Map<Double, Integer> histogramMap = new HashMap<>();

    /**
     * Adds a new {@code double} value to this set.
     * 
     * @param number the value to add to this set.
     */
    public void add(double number) {
        checkNumberIsNotNaN(number);
        checkNumberIsNotInfinite(number);
        histogramMap.put(number, histogramMap.getOrDefault(number, 0) + 1);
        sum += number;
        squareSum += number * number;
        numberOfElements++;
    }

    /**
     * Adds a new arbitrary number to this set.
     * 
     * @param number the number to add to this set. 
     */
    public void add(Number number) {
        add(number.doubleValue());
    }

    /**
     * Attempts to remove the input {@code double} number, and does so if it is 
     * present in this set.
     * 
     * @param number the value to remove.
     * @return {@code true} only if the input value is present in this set prior
     *         to this operation, {@code false} otherwise.
     */
    public boolean remove(double number) {
        if (histogramMap.containsKey(number)) {
            int oldCount = histogramMap.put(number, 
                                            histogramMap.get(number) - 1);

            if (oldCount == 1) {
                histogramMap.remove(number);
            }

            sum -= number;
            squareSum -= number * number;
            numberOfElements--;
            return true;
        } else {
            return false;
        }
    }

    /**
     * Attempts to remove the input number, and does so if it is present in this
     * set.
     * 
     * @param number the number to remove.
     * @return {@code true} only if the input number is present in this set 
     *         prior to this operation, {@code false} otherwise.
     */
    public boolean remove(Number number) {
        return remove(number.doubleValue());
    }

    /**
     * Removes all the values from this set.
     */
    public void clear() {
        histogramMap.clear();
        sum = 0.0;
        squareSum = 0.0;
        numberOfElements = 0;
    }

    /**
     * Returns the number of values stored in this set.
     * 
     * @return the number of values stored.
     */
    public int size() {
        return numberOfElements;
    }

    /**
     * Returns the current average value of this set.
     * 
     * @return the average of this set.
     */
    public double getAverage() {
        if (numberOfElements == 0) {
            return Double.NaN;
        }

        return sum / numberOfElements;
    }

    /**
     * Returns the current standard deviation of this set.
     * 
     * @return the standard deviation of this set.
     */
    public double getStandardDeviation() {
        switch (numberOfElements) {
            case 1:
            case 0:
                return Double.NaN;
        }

        double step1 = squareSum - sum * sum / numberOfElements;
        double step2 = step1 / (numberOfElements - 1);
        return Math.sqrt(step2);
    }

    /**
     * Returns a textual representation of this set.
     * 
     * @return a textual representation.
     */
    @Override
    public String toString() {
        return "[Size = " + numberOfElements + ", average = " + getAverage() +
               ", s.d. = " + getStandardDeviation() + "]";
    }

    public static void main(String[] args) {
        StatisticsNumberSet set = new StatisticsNumberSet();

        set.add(1);
        set.add(1);
        set.add(3);

        System.out.println(set);

        set.remove(1);

        System.out.println(set);
    }

    private void checkNumberIsNotNaN(double number) {
        if (Double.isNaN(number)) {
            throw new IllegalArgumentException("The input number is NaN.");
        }
    }

    private void checkNumberIsNotInfinite(double number) {
        if (Double.isInfinite(number)) {
            throw new IllegalArgumentException(
                    "The input number is infite: " + number);
        }
    }
}

StatisticsNumberSetTest.java

package net.coderodde.stat;

import org.junit.After;
import org.junit.AfterClass;
import org.junit.Before;
import org.junit.BeforeClass;
import org.junit.Test;
import static org.junit.Assert.*;

public class StatisticsNumberSetTest {

    private static final double DELTA = 0.001;

    private final StatisticsNumberSet set = new StatisticsNumberSet();

    @Before
    public void setUp() {
        set.clear();
    }

    @Test
    public void testAdd_double() {
        set.add(1.0);
        set.add(2.0);

        assertEquals(2, set.size());

        set.add(1.0);

        assertEquals(3, set.size());

        set.add(2.0);

        assertEquals(4, set.size());
        assertEquals(1.5, set.getAverage(), DELTA);
    }

    @Test
    public void testAdd_Number() {
        set.add(1);
        set.add(2.0f);

        assertEquals(2, set.size());

        set.add(1L);

        assertEquals(3, set.size());

        set.add((short) 2);

        assertEquals(4, set.size());
        assertEquals(1.5, set.getAverage(), DELTA);
    }

    @Test
    public void testRemove_double() {
        set.add(10.0);
        set.remove(10.0);

        set.add(11);
        set.remove(11.0);

        assertEquals(0, set.size());
    }

    @Test
    public void testRemove_Number() {
        set.add(10.0);
        set.remove(10);

        set.add((short) 11);
        set.remove(11L);

        assertEquals(0, set.size());
    }

    @Test
    public void testSize() {
        for (int i = 0; i < 10; ++i) {
            assertEquals(i, set.size());
            set.add(i);
            assertEquals(i + 1, set.size());
        }

        for (int i = 9; i > -3; --i) {
            assertEquals(Math.max(i + 1, 0), set.size());
            set.remove(i);
            assertEquals(Math.max(i, 0), set.size());
        }
    }

    @Test
    public void testGetAverage() {
        set.add(1);
        set.add(2L);
        set.add((short) 3);
        set.add((byte) 4);
        set.add(5.0f);
        set.add(6.0);

        assertEquals(3.5, set.getAverage(), DELTA);
    }

    @Test
    public void testGetStandardDeviation() {
        set.add(1);
        set.add(2L);
        set.add((short) 3);
        set.add((byte) 4);
        set.add(5.0f);
        set.add(6.0);

        assertEquals(1.8708, set.getStandardDeviation(), DELTA);
    }    
}

As always, any critique is much appreciated.

\$\endgroup\$
1
\$\begingroup\$

The class StatisticsNumberSet looks very good, the only thing I would change is that ugly switch-case in getStandardDeviation, you could replace it by a single and more readable if:

   if (numberOfElements < 2) {
    return Double.NAN;
    }

Now in my opinion you should improve your test suit.
First of all there sould be one assertion per test, you should test only one logical thing. In this way, when a test fail it will be easier for you to locate the code that caused the failure. Try to keep your tests as small and fast as possible:

@Test
public void testEmptySet() {
    assertEquals(0, set.size());  
}

@Test
public void testAdd_double() {
    int elementsBefore = set.size();
    set.add(1.0);
    assertEquals(elementsBefore + 1, set.size());
}

@Test
public void testRemove_Number() {
    set.add(10.0);
    int sizeBefore = set.size();
    set.remove(10.0);
    assertEquals(sizeBefore - 1, set.size());
}

You could write more tests, for example you could test your exceptions:

@Test(expected = IllegalArgumentException.class)
public void testAddingNaN() {
    set.add(Double.NaN);
}

Try to use a code coverage tool to see how much code your test cover and try to get a good percentage of coverage.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

You don't need the methods checkNumberIsNotNaN or checkNumberIsNotInfinite, since they're just thin wrappers around Double.isNaN and Double.isInfinite.

One thing you can do is combine them into a single static helper method that takes a Number, converts it into a Double, and throws exceptions if the value isn't finite.

private static double toFiniteDouble(Number num) {
    double d = num.doubleValue();
    if (Double.isNaN(d)) {
        throw new IllegalArgumentException("NaN");
        // please use a better exception message
    }
    if (Double.isInfinite(d)) {
        throw new IllegalArgumentException("+Inf or -Inf");
    }
    return d;
}

getAverage should not return NaN if the set is empty. I would recommend throwing a dedicated exception here or doing nothing and allowing the divide by zero to be caught elsewhere. Most consumers of your API will not be expecting to encounter a NaN for this operation.

 public double getAverage() {
        if (numberOfElements == 0) {
            return Double.NaN;
        }

The logic for how to compute the standard deviation and mean looks correct, I haven't really checked it closely.

One thing you might want to do is expose the variance as a public instance method and define the standard deviation in terms of that. That way the user of your library can calculate the population or sample standard deviation as their needs require.

On another note, I'm trying to figure out why you're keeping track of values that have been stored in the container at all. I think the only reason histogramMap exists is to make sure that only items that were present in the collection at one point in time are allowed to be removed. I don't think it's necessary to do that. You can simplify your code by allowing the user to remove ANY number, and decrement the sum, squareSum, and numberOfElements appropriately, without bothering to determine whether the set contained that number at one point in time.

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.