19
\$\begingroup\$

Challenge

The recent question The 3n + 1 algorithm for a range inspired me to investigate a Java-8 dependent streaming mechanism for solving the programming challenge:

For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j (inclusive).

The cycle length of a number is defined as the count of values in the Collatz Sequence for that number.

Input

The input is given as multiple low and high bounds in an input file, each line contains one low and high bound. The programming challenge limits the high bound to 1,000,000 but I found that I was able to handle much larger bounds. The input I used is:

-1 0
0 0
0 1
22 22
27 27
1 100
99 100
100 100
1000 1000000
1 10000000
1 10000000

Output

The output should consist of the two input values followed by the length of the longest sequence from those bounds. For example, the input sequence 22 22 should produce the output:

22 22 16

I have elected to add additional timing data to the output for my tests, but this can be removed easily....

Review Request

I am particularly interested in any ways I could be using the new Java 8 functionality more effectively, while still maintaining a high level of performance. Additionally, I am curious to know if there are faster ways to do this....

Solution

I have split the code in two classes, one which is a factory mechanism to supply an IntStream of the sequence. The second class is just the one which implements the challenge.

(The code in revision 1 is obsolete.)

The following is the Sequence factory:

import java.util.Spliterator;
import java.util.Spliterators;
import java.util.function.IntConsumer;
import java.util.function.IntUnaryOperator;
import java.util.stream.IntStream;
import java.util.stream.StreamSupport;

/**
 * A Factory class which supplies a Stream of int that follow the <a
 * href="http://en.wikipedia.org/wiki/Collatz_conjecture">Collatz Conjecture</a>
 * sequence:
 * <ol>
 * <li>1 value of 1 terminates the stream
 * <li>even values are halved
 * <li>odd values are trippled and 1 is added
 * </ol>
 * 
 * @author rolf
 *
 */
public class CollatzSequence extends Spliterators.AbstractIntSpliterator {

    private static final IntUnaryOperator NEXT_COLLATZ = seq -> seq <= 1 
            ? 0 : ((seq % 2 == 0) ? (seq / 2) : (3 * seq + 1));

    private int next;

    private CollatzSequence(int seed) {
        super(Long.MAX_VALUE, Spliterator.IMMUTABLE);
        this.next = seed;
    }

    @Override
    public boolean tryAdvance(IntConsumer action) {
        if (next < 1) {
            return false;
        }

        action.accept(next);
        next = NEXT_COLLATZ.applyAsInt(next);
        return true;
    }

    /**
     * Factory method that supplies an IntStream containing the Collatz
     * sequence.
     * 
     * @param seed
     *            The initial seed to sequence through.
     * @return an IntStream supplying the sequence, starting from the seed,
     *         through to the value 1, whenever that happens.
     */
    public static IntStream stream(int seed) {
        return StreamSupport.intStream(new CollatzSequence(seed), false);
    }

}

Her is the implementation of the actual challenge-solving code (note, I use a parallel stream for the ranges):

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class CollatzChallenge {

    public static final int countCollatz(int seed) {
        return (int) CollatzSequence.stream(seed).count();
    }

    public static final int maxCollatz(int from, int to) {
        return IntStream.rangeClosed(from, to)
                .parallel()
                .map(s -> countCollatz(s))
                .max()
                .orElse(0);
    }

    public static final void processChallenge(Path input, BufferedWriter output) throws IOException {
        for (String line : Files.readAllLines(input)) {

            int[] parts = Stream.of(line.split("\\s+", 2))
                    .mapToInt(Integer::parseInt)
                    .toArray();

            long start = System.nanoTime();
            int max = maxCollatz(parts[0], parts[1]);
            long nanos = System.nanoTime() - start;

            int count = Math.max(parts[1] - parts[0] + 1, 1);
            output.write(String.format("%d %d %d  (total %.3fms each %.3fus)\n",
                    parts[0], parts[1], max,
                    nanos / 1000000.0, (nanos / 1000.0) / count));
        }
    }

    public static void main(String[] args) throws IOException {
        if (args.length < 1) {
            throw new IllegalArgumentException("No source specified");
        }
        Path source = Paths.get(args[0]).toAbsolutePath();
        try (BufferedWriter bw = args.length > 1
                ? Files.newBufferedWriter(Paths.get(args[1]))
                : new BufferedWriter(new OutputStreamWriter(System.out))) {

            processChallenge(source, bw);

        }

    }

}

Results

For me, the results I get are (Intel(R) Core(TM) i7-4770K CPU @ 3.50GHz - 4 core with HT running linux):

-1 0 0  (total 6.917ms each 3458.511us)
0 0 0  (total 0.050ms each 49.685us)
0 1 1  (total 0.128ms each 64.044us)
22 22 16  (total 0.042ms each 42.104us)
27 27 112  (total 0.128ms each 127.835us)
1 100 119  (total 2.240ms each 22.399us)
99 100 26  (total 0.079ms each 39.291us)
100 100 26  (total 0.029ms each 28.728us)
1000 1000000 476  (total 211.695ms each 0.212us)
1 10000000 616  (total 1273.127ms each 0.127us)
1 10000000 616  (total 1227.744ms each 0.123us)
\$\endgroup\$
4
\$\begingroup\$

This problem of counting lengths of Collatz sequences benefits greatly from memoization. Memoizing results for just the first 2000 seeds cuts the computation time for the 1-to-107 problem in half — and if only searching up to 106, the effect is even more dramatic.

Here's a quick-and-dirty hack that does the job; I'm sure that countCollatz() could be made more elegant. (Even with the nasty repetition, it's still shorter than writing a CollatzSequence class. A Spliterator to create a stream that you can .count() seems like overkill.)

public class CollatzWithMemo {

    private final int[] collatzCounts;

    public CollatzWithMemo(int memoizationLimit) {
        this.collatzCounts = new int[memoizationLimit];
    }

    public final int countCollatz(int n) {
        if (n <= 1) {
            return 1;
        } else if (n >= this.collatzCounts.length) {
            // Unmemoizable
            return 1 + this.countCollatz(n % 2 == 0 ? n / 2 : 3 * n + 1);
        } else if (this.collatzCounts[n] != 0) {
            // Result is already memoized
            return this.collatzCounts[n];
        } else {
            // Need to memoize new result
            return this.collatzCounts[n] = 1 + this.countCollatz(n % 2 == 0 ? n / 2 : 3 * n + 1);
        }
    }

    public final int maxCollatz(int from, int to) {
        …
    }

    public final void processChallenge(Path input, BufferedWriter output) throws IOException {
        …
    }

    public static void main(String[] args) throws IOException {
        if (args.length < 1) {
            throw new IllegalArgumentException("No source specified");
        }
        Path source = Paths.get(args[0]).toAbsolutePath();
        CollatzWithMemo collatz = new CollatzWithMemo(2000);
        try (BufferedWriter bw = args.length > 1
                ? Files.newBufferedWriter(Paths.get(args[1]))
                : new BufferedWriter(new OutputStreamWriter(System.out))) {

            collatz.processChallenge(source, bw);

        }

    }

}
\$\endgroup\$
  • 1
    \$\begingroup\$ I like the memoization thought, which was my first thought as well as I read this question, but I also like the CollatzSequence class in the original question. Also, your code here could benefit from the IntUnaryOperator NEXT_COLLATZ operator. \$\endgroup\$ – Simon Forsberg Mar 25 '15 at 11:07

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.