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
iandjyou are to determine the maximum cycle length over all numbers betweeniandj(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)
