5
\$\begingroup\$

I'm writing a neural net which uses a genetic algorithm to adjust the weights. To represent the possible range of "genes" for the GA, I'm passing in a list of bases. Unfortunately, I realized after the fact that there will be a huge possible range of weights for the net, and storing a list of all possible weights would be inefficient (it could potentially get huge).

This sounded like a job for a Range, but apparently Java doesn't have one that implements the List interface.

I decided to write one as an exercise, and because I will actually need it unless I can find a better way to represent an arbitrary amount of bases of an arbitrary type.

Problems that I'd like help with:

  • A lot (most) of the methods from the interface are currently throwing an UnsupportedOperationException, either because the operation doesn't make sense (adding to the range), or because I couldn't figure out how to properly implement it. Any suggestions on how to implement one of the methods would be appreciated.
  • Originally, I allowed for deletions by maintaining a Set of deleted elements. While iterating, the iterator would just skip over any elements in the set. This worked until I realized that get doesn't take it into consideration. I'd like suggestions how how get could be written to allow for a Set of deleted elements.
  • Any general comments on how to improve anything.

Range.java:

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;

public class Range
        implements  List<Double>,
                    Iterable<Double> {

    private double min;
    private double step;
    private double max;


    public Range(double min, double step, double max) {
        this.min = min;
        this.step = step;
        this.max = max;
    }

    private void unsupportedOperation(String operationName) {
        throw new UnsupportedOperationException(
            "Range: Unsupported Operation: " + operationName + "." );
    }

    //Calculates the number at the given index.
    @Override
    public Double get(int index) {
        double val = min + step * index;

        if (val > max) throw new IndexOutOfBoundsException(
            "Index (" + index + ") out of range: " + this );

        return val;
    }

    @Override
    public boolean add(Double n) {
        unsupportedOperation("add");
        return false;
    }


    @Override
    public void add(int index, Double n) {
        unsupportedOperation("add");
    }

    @Override
    public boolean addAll(Collection<? extends Double> ns) {
        unsupportedOperation("addAll");
        return false;
    }

    @Override
    public boolean addAll(int index, Collection<? extends Double> ns) {
        unsupportedOperation("addAll");
        return false;
    }

    //This and the next method are slightly ambiguous.
    @Override
    public Double remove(int index) {
        unsupportedOperation("remove");
        return 0D;
    }

    @Override
    public boolean remove(Object o) {
        unsupportedOperation("remove");
        return false;
    }

    @Override
    public boolean removeAll(Collection<?> ns) {
        unsupportedOperation("removalAll");
        return false;
    }

    @Override
    public Double set(int index, Double n) {
        unsupportedOperation("set");
        return 0D;
    }

    @Override
    public int indexOf(Object o) {
        Double n = min;
        for (int i = 0; n <= max; n += step, i++) {
            if (n.equals(o)) return i;
        }

        return -1;
    }

    @Override
    public boolean retainAll(Collection<?> ns) {
        unsupportedOperation("retainAll");
        return false;
    }

    @Override
    public void clear() {
        unsupportedOperation("clear");
    }

    @Override
    public boolean contains(Object o) {
        for (Double n : this) {
            if (n.equals(o)) return true;
        }

        return false;
    }

    @Override
    public boolean containsAll(Collection<?> ns) {
        for (Object n : ns) {
            if (!contains(n)) return false;
        }

        return true;
    }

    @Override
    public int size() {
        return (int)Math.ceil( (max - min) / step );
    }

    @Override
    public Object[] toArray() {
        List<Double> arr = new ArrayList<Double>();
        for (Double n : this) {
            arr.add(n);
        }

        return arr.toArray();
    }

    @Override
    public <T> T[] toArray(T[] arr) {
        unsupportedOperation("Generic toArray");
        return arr;
    }

    @Override
    @SuppressWarnings("unused")
    public boolean isEmpty() {
        for (Double n : this) {
            return false;
        }

        return true;
    }

    @Override
    public List<Double> subList(int fromIndex, int toIndex) {
        return new Range(get(fromIndex), step, get(toIndex) - 1);
    }

    @Override
    public int lastIndexOf(Object o) {
        Double n = min;
        for (int i = 0; n <= max; n += step, i++) {
            if (n.equals(o)) return i;
        }

        return -1;
    }

    @Override
    public ListIterator<Double> listIterator() {
        unsupportedOperation("listIterator");
        return null;
    }

    @Override
    public ListIterator<Double> listIterator(int index) {
        unsupportedOperation("listIterator");
        return null;
    }

    @Override
    public Iterator<Double> iterator() {
        class RangeIterator
                implements Iterator<Double> {

            double curN = min;

            private double nextNonRemoved() {
                return curN += step;
            }

            @Override
            public boolean hasNext() {
                return curN <= max;
            }

            @Override
            public Double next() {
                double last = curN;

                if (curN > max) throw new NoSuchElementException(
                    "Iterator out of range.");

                curN = nextNonRemoved();

                return last;
            }
        }

        return new RangeIterator();
    }

    @Override
    public String toString() {
        return "(" + min + "," + step + "," + max + ")";
    }

    public static void main(String[] args) {
        List<Double> range = new Range(1, 2, 20);

        for (double n : range) System.out.print(n + ", ");

        System.out.println("\nSize: " + range.size());

        //Should be "4".
        System.out.println(range.lastIndexOf(9D));

        List<Double> sub = range.subList(3, 8);

        for (double n : sub) System.out.print(n + ", ");

        System.out.println("\nSize: " + sub.size());

    }

}
\$\endgroup\$
3
  • \$\begingroup\$ I just realized that since a Range won't have duplicates, it should really be Set instead of a List. I'll change that later, but it doesn't affect the question. \$\endgroup\$ Jul 12, 2015 at 17:33
  • \$\begingroup\$ While Set doesn't have duplicates, it also doesn't have indexable positions (which you appear to be using). It either contains a value, or it doesn't. \$\endgroup\$
    – user22048
    Jul 12, 2015 at 18:29
  • \$\begingroup\$ @MichaelT Good point, I will need to use the List interface then get is the main use method. \$\endgroup\$ Jul 12, 2015 at 18:30

1 Answer 1

7
\$\begingroup\$

A lot (most) of the methods from the interface are currently throwing an UnsupportedOperationException, either because the operation doesn't make sense (adding to the range),

Start with an AbstractList, it already throws UnsupportedOperationException on any mutating operation. Implementing an immutable list is fine, there's one general purpose ImmutableList in Guava and yours will be a specialized one.

Originally, I allowed for deletions by maintaining a Set of deleted elements.

Why? YAGNI. Immutability is a virtue.

I'd like suggestions how how get could be written to allow for a Set of deleted elements.

The most efficient implementation would probably use some tree nodes keeping track of the sizes of the subtrees. Pretty complicated.

Something like a BitSet to keep track of the non-removed elements would be simpler. Now, I can't find any efficient operation to find out the n-th non-removed element, but it's doable (using a Long.bitCount you can check 64 candidates at once.

Any general comments on how to improve anything.

Keep it immutable, it's a virtue.

I just realized that since a Range won't have duplicates, it should really be Set instead of a List. I'll change that later, but it doesn't affect the question

Not necessarily. If the order is important, then it's a List. If there are no duplicates, then it may be a Set. The two concepts are incompatible w.r.t. equals (which you forgot).

Review

public class Range
        implements  List<Double>,
                    Iterable<Double> {

As a List is already an Iterable, you can remove it.

Collections containing Double are a bad idea as testing two doubles for equality is already a bad idea. Due to round-off errors, you'll get tons of strange behavior. Not worth the pain. I'd either work with Integer, or trash the whole idea.

private double min;
private double step;
private double max;

They should be final.

private void unsupportedOperation(String operationName) {
    throw new UnsupportedOperationException(
        "Range: Unsupported Operation: " + operationName + "." );
}

The classical idiom is

private UnsupportedOperationException unsupportedOperation(String operationName) {
   ... the same code, no return
}

so you can "throw" it like

public boolean add(Double n) {
    throw unsupportedOperation("add");
}

and save yourself the dummy return.

@Override
public Double get(int index) {
    double val = min + step * index;

    if (val > max) throw new IndexOutOfBoundsException(
        "Index (" + index + ") out of range: " + this );

    return val;
}

This is the first method which will fall pray to round-off errors. For something like

new Range(0.0, 0.1, 1.0)

you may get that it contains 10 or 11 elements. It's deterministic, but from the user's POV it looks random. A representation using min, step, and size` would be better.

Skipped many throwing methods which can be inherited from AbstractList.

public boolean contains(Object o) {
    for (Double n : this) {
        if (n.equals(o)) return true;
    }

    return false;
}

This is correct but slow. Something like

public boolean contains(Object o) {
    if (o instanceof Double) {
         double d = (Double) o;
         if (min <= d && d <= max) {
             if (((d - min) / step) % 1 == 0) return true;
         }
    }
    return false;
}

would be much faster for huge ranges, however it'd suffer from other rounding issues and therefore be worse. Your contains is obviously consistent with iterator, but most probably inconsistent with get. With floating point, it's not always true that

min + 3 * step equals to min + step + step + step.

@Override
public int size() {
    return (int)Math.ceil( (max - min) / step );
}

That's inconsistent with get, even without any rounding. Try it with new new Range(0, 3, 10).

@Override
public Object[] toArray() {
    List<Double> arr = new ArrayList<Double>();
    for (Double n : this) {
        arr.add(n);
    }

    return arr.toArray();
}

You know size, so you need no ArrayList.

public <T> T[] toArray(T[] arr) {
    unsupportedOperation("Generic toArray");
    return arr;
}

This is wrong. Throwing UnsupportedOperationException is allowed for optional operations only, not this one. It can be implemented easily using Arrays.copyOf(T[] original, int newLength).

@SuppressWarnings("unused")
public boolean isEmpty() {
    for (Double n : this) {
        return false;
    }

    return true;
}

Correct, but rather inefficient. Returning size() == 0 would be simpler.

You're missing equals and hashCode. Note that they're non-trivial because of the List interface. For example, new Range(10, 1, 1) and new Range(10, 1, 2) must be equal as both are empty. They must also be equal to new ArrayList().

Summary

All in all, it's not bad, it's just that a collection of floating-point values is tricky and -- even if done perfectly -- hardly ever does what's wanted.

\$\endgroup\$
6
  • \$\begingroup\$ Excellent, thank you. I need my weights to be non-integral though. Can you think of any changes that would allow this to work to circumvent the errors? Is BigDecimal subject to floating-point errors? \$\endgroup\$ Jul 12, 2015 at 18:37
  • \$\begingroup\$ Maybe I'll store them as Integers, and scale them somehow to make them floating-point if needed. \$\endgroup\$ Jul 12, 2015 at 18:43
  • \$\begingroup\$ @Carcigenicate Is BigDecimal subject to floating-point errors? - It can exactly represent some decimal numbers, but you can't feed it with an arbitrary number. +++ Yes, a scaled Integer will work just fine. \$\endgroup\$
    – maaartinus
    Jul 12, 2015 at 19:00
  • \$\begingroup\$ Thanks, and what did you mean "A representation using min , step, and size would be better"? Instead of using max, have the user specify the size? \$\endgroup\$ Jul 12, 2015 at 19:09
  • 1
    \$\begingroup\$ Also, the index that is passed can be negative, so you should check that side of the range as well. \$\endgroup\$ Jul 13, 2015 at 11:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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