Thursday, June 12, 2014

A gentle touch of functional programming with Java 8 - prime numbers

    'Functional programming' are buzz words nowadays. Let's try to play a little bit with that. The only assumption of this post is... to have some fun :).
The problem is as follows: "Find prime numbers in the given interval". The algorithm is not that important. I came up with:
public class Prime {
 
 public static void main(String[] args) throws Exception {  
  final int threshold = 50_000_000;
  
  final long start = System.currentTimeMillis();
  
  final List candidates = IntStream.range(2, threshold).boxed().collect(Collectors.toList());
  final List primeNumbers = candidates.stream().filter(Prime::isPrime).collect(Collectors.toList());

  System.out.println("Execution time: " + System.currentTimeMillis() - start);
  
  System.out.println("Size: " + primeNumbers.size());
 }
 
 private static boolean isPrime(final int candidate) {
  for (int i = 2; i * i <= candidate; ++i) {
   if (candidate % i == 0) {
    return false;
   }
  }
  return true;
 }
}
Printed result:
Execution time: 55166
Size: 3001134
The code is quite clean. However, it is executed sequentially and I have 4-cores (4.5 GHz each) - Core i5 Sandy Bridge - under the hood. Can we improve something? Of course we can! There is a new stream() API in Java 8 that allows for parallel processing. Just a small change to the code and we are set:
final List primeNumbers = candidates.parallelStream().filter(Prime::isPrime).collect(Collectors.toList());
The output was:
Execution time: 16950
Size: 3001134
Not so bad. parallelStream() uses default ForkJoin pool. Let's check the state of the threads:
4 threads are engaged in the computations: main thread and 3 workers. Can we obtain the result faster? How about using custom ForkJoin pool with 5 threads:
final ForkJoinPool forkJoinPool = new ForkJoinPool(5);
final List primeNumbers = forkJoinPool.submit(() -> candidates.parallelStream().filter(Prime::isPrime).
                                                    collect(Collectors.toList())).get();

The output:
Execution time: 15504
Size: 3001134
The state of the threads:

Main thread does not participate in the computations. As you can see it is really easy to make some operations in parallel with Java 8. As Josh Long during his talk on 33rd Degree conference said: "Switch to Java 8 and you will feel so much better" :).

No comments :

Post a Comment