5
\$\begingroup\$

This is a BitSet wrapper class to act as a Sieve abstraction for a prime calculator. Review for performance and Java/Java 8/Guava best practices.

package info.simpll.immense.prime;

import com.google.common.base.MoreObjects;

import java.math.BigInteger;
import java.util.BitSet;
import java.util.Objects;
import java.util.stream.IntStream;

/**
 * Sieve holds a BitSet that is used to cross out numbers,
 * However unlike BitSet, sieve uses different indexing scheme
 * Which is more suitable for prime number calculation
 *
 * @author Bhathiya
 */
public class Sieve {

    public static int MAX_SIZE = 8 * 1024 * 1024;

    private final int size;
    private BigInteger startIndex;
    private BigInteger endIndex;
    private final BitSet bitSet;

    /**
     * Constructor for the bitSet
     *
     * @param size       count of the bitSet
     * @param startIndex starting index of the bitSet
     */
    public Sieve(int size, BigInteger startIndex) {

        if (size > MAX_SIZE || size < 10) {
            throw new IllegalArgumentException("Size is larger than "
                    + "the allowed maximum or smaller than 10");
        }
        this.size = size;
        this.startIndex = startIndex;
        endIndex = startIndex.add(BigInteger.valueOf(size));
        bitSet = new BitSet(size);
    }

    public Sieve(int size, long startIndex) {
        this(size, BigInteger.valueOf(startIndex));
    }

    public boolean get(BigInteger index) {
        return bitSet.get(calculateIndex(index));
    }

    public void set(BigInteger index) {
        bitSet.set(calculateIndex(index), true);
    }

    public boolean get(long index) {
        return get(BigInteger.valueOf(index));
    }

    public void set(long index) {
        set(BigInteger.valueOf(index));
    }

    private int calculateIndex(BigInteger index) {

        if (getEndIndex().compareTo(index) <= 0
                || getStartIndex().compareTo(index) == 1) {
            throw new IndexOutOfBoundsException("Invalid position");
        }
        // This should not be a problem since we are ensuring that the count
        // Is less than MAX_SIZE, which is an integer
        return (int) (index.subtract(getStartIndex()).longValue());
    }

    public void clear() {
        bitSet.clear();
    }

    public int getSize() {
        return size;
    }

    public BigInteger getStartIndex() {
        return startIndex;
    }

    public BigInteger getEndIndex() {
        return endIndex;
    }

    public BigInteger getMaxIndex() {
        return endIndex.subtract(BigInteger.ONE);
    }


    public Sieve increment() {
        return increment(true);
    }

    /**
     * Increment the bitSet, use this method once the bitSet is exhausted.
     * If count is 100 and start is 2, then endIndex is 102
     * After increment startIndex is 102
     *
     * @param performClear if true this will clear the BitSet
     * @return this
     */
    public Sieve increment(boolean performClear) {
        if (performClear) clear();
        startIndex = endIndex;
        endIndex = startIndex.add(BigInteger.valueOf(size));
        return this;
    }

    @Override
    public String toString() {
        return MoreObjects.toStringHelper(this.getClass())
                .add("count", size)
                .add("startIndex", startIndex)
                .add("endIndex", endIndex)
                .add("bitSet", bitSet)
                .toString();
    }

    @Override
    public int hashCode() {
        int hash = 5;
        hash = 71 * hash + this.size;
        hash = 71 * hash + Objects.hashCode(this.startIndex);
        hash = 71 * hash + Objects.hashCode(this.endIndex);
        hash = 71 * hash + Objects.hashCode(this.bitSet);
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final Sieve other = (Sieve) obj;
        if (this.size != other.size) {
            return false;
        }
        if (!Objects.equals(this.startIndex, other.startIndex)) {
            return false;
        }
        if (!Objects.equals(this.endIndex, other.endIndex)) {
            return false;
        }
        return Objects.equals(this.bitSet, other.bitSet);
    }

    public void debugPrint(String prepend) {
        StringBuilder probablePrimeList = new StringBuilder();
        IntStream.rangeClosed(0, size - 1).forEach(i -> {
            BigInteger index = startIndex.add(BigInteger.valueOf(i));
            if (!get(index)) {
                probablePrimeList.append(" ");
                probablePrimeList.append(index.toString(10));
            }
        });
        System.out.printf("SIEVE: %s %s: Unset {%s }\n",
                prepend, this.toString(), probablePrimeList);
    }
}

Test Cases

package info.simpll.immense.prime;

import org.junit.Test;

import java.math.BigInteger;

import static org.junit.Assert.*;

/**
 * @author Bhathiya
 */
public class SieveTest {

    @Test
    public void testApi() {
        Sieve instance = new Sieve(10, 2);
        boolean result = instance.get(10);
        instance.debugPrint("testApi");
        assertFalse(result);
        assertTrue(instance.getMaxIndex()
                .compareTo(BigInteger.valueOf(11)) == 0);
    }

    @Test
    public void testSetAndGet() {
        Sieve instance = new Sieve(10, 2);
        for (int i = 2; i < (int) instance.getEndIndex().longValue(); i++) {
            instance.set(BigInteger.valueOf(i));
        }
        instance.debugPrint("testSetAndGet");
        for (int i = 2; i < (int) instance.getEndIndex().longValue(); i++) {
            assertTrue(instance.get(BigInteger.valueOf(i)));
        }
    }

    @Test
    public void testSetAndGetEdge() {
        Sieve instance = new Sieve(10, 2);
        instance.set(11);
        instance.set(2);

        assertTrue(instance.get(11));
        assertTrue(instance.get(2));
        instance.debugPrint("testSetAndGetEdge");
    }

    @Test(expected = IndexOutOfBoundsException.class)
    public void testLowerEdgeOut() {
        Sieve instance = new Sieve(10, 2);
        instance.set(1);
    }

    @Test(expected = IndexOutOfBoundsException.class)
    public void testUpperEdgeOut() {
        Sieve instance = new Sieve(10, 2);
        instance.set(12);
    }

    @Test
    public void testIncrement() {
        Sieve instance = new Sieve(10, 2);
        for (int i = 2; i < (int) instance.getEndIndex().longValue(); i++) {
            instance.set(BigInteger.valueOf(i));
        }
        instance.increment();
        assertEquals(instance.getStartIndex(), BigInteger.valueOf(12));
        assertEquals(instance.getEndIndex(), BigInteger.valueOf(22));
        assertEquals(instance.getMaxIndex(), BigInteger.valueOf(21));
        instance.debugPrint("testIncrement");
    }

}
\$\endgroup\$
3
\$\begingroup\$

Improvements

Right now, you lose a lot of performance due to the use of BigInteger and all the conversions you need to make. There are two things that I think could help a lot:

  1. I would like to see a function that returns a list of BigIntegers, which represent the primes in your sieve. Right now, to get that information, you have to manually make a lot of calls to get(), which is pretty slow because of all the conversions from long <-> BigInteger. But if you wrote this function, you could internally loop through the bitset using an int and only convert the primes you find to BigInteger.

  2. Similarly, I would like to see a sieving function that takes a prime number argument. This function would automatically set all bits that should be set for that prime number. If the prime is less than size, you can use a local int variable in a loop to set bits in the bitset. If the prime is larger than size, then at most one bit will be set.

\$\endgroup\$
3
\$\begingroup\$

A few things that jump to my eye, here and there:

    if (size > MAX_SIZE || size < 10) {
        throw new IllegalArgumentException("Size is larger than "
                + "the allowed maximum or smaller than 10");
    }

this will come out somewhat... strange to me as a developer using your class... Why can't I sieve for things smaller than 10?? And what is the allowed maximum size?

When this gets thrown to me, I may know what I did wrong, but the upper bound is just found by trial and error. Be more descriptive. (and if you really need to keep it, extract 10 into a named constant)

    if (getEndIndex().compareTo(index) <= 0
            || getStartIndex().compareTo(index) == 1) {
        throw new IndexOutOfBoundsException("Invalid position");
    }

Same problem applies here. Usually I'd expect to be told two things when there's an IndexOutOfBoundsException (and yes, in the exception message)

  1. What index did I try to access?
  2. What size does the Collection I try to access have?

Both of these are missing here. These messages need some work...


public void debugPrint(String prepend) {
    StringBuilder probablePrimeList = new StringBuilder();
    IntStream.rangeClosed(0, size - 1).forEach(i -> {
        BigInteger index = startIndex.add(BigInteger.valueOf(i));
        if (!get(index)) {
            probablePrimeList.append(" ");
            probablePrimeList.append(index.toString(10));
        }
    });
    System.out.printf("SIEVE: %s %s: Unset {%s }\n",
            prepend, this.toString(), probablePrimeList);
}

debug... print..These two words are too often placed together in the same sentence. Debugging is not randomly printing out variables and object internals with some strings in front. Debugging is stepping through code with a debugger.

Everything else is info-logging. and that should probably not happen in a class like this. This method is a problem, in that it's effectively useless for the functionality of the class. It doesn't belong there, move it somewhere else.


Last but not least: Test setup.

Unit tests in my sideprojects usually have a standard setup. There's this one thing getting tested. Simplest name: "class under test" or short cut.

Before every test, this class under test will be put into a clean state, so the test doesn't have to concern with that. JUnit provides a nice annotation for that: @Before

I'd change your unit tests to look a little more like this:

public class SieveTest {

    private Sieve cut;

    @Before
    public void setup() {
        cut = new Sieve(10,2);
    }

    // test cases go here, access cut
}
\$\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.