Jump to: Navigation
Performance costs of Dynamic Typing (Groovy vs Java)
Recently, someone at work introduced me to Project Euler, which is a web site that posts logic/math problems and asks users to solve them using code.
The web site is weirdly addictive, and the only requirement is that the solution arrived should run in under a minute (which is a rather arbitrary limit).
I begun solving the problems in Groovy until I arrived at a problem that asked the user to compute the 10001th Prime number. My initial solution, written in Groovy using a very simple Prime number function (code snippet below)
def getPrimesTo(start,upperLimit){
def nums = start..upperLimit
for(int i=2;i<=nums.last();i++){
nums = remove(nums,i)
if(nums.size()==0){
break
}
}
return nums
}
My initial solution iterated through all numbers beginning at 2, adding those that were determined to be Prime to a List and checking the size of the list. I realized this solution would be a no go when after 4 minutes it was still runnning on my machine which is an Intel i7 with 8 Gig of RAM. Obviously this was a no go.
I then made a modification and used a Sieve of Erastothenes approach (get a List of numbers from 2 -x, and then starting at 2, remove numbers from the List that are not that number and multiples of that number). So for example, to find all the prime numbers between 2 and 10, start with
[2,3,4,5,6,7,8,9,10]
remove all numbers that are multiples of 2
[2,3,5,7,9]
remove all numbers that are multiples of 3
[2,3,5,7]
and so on. The relevant methods in Groovy looks like
def getPrimesTo(start,upperLimit){
def nums = start..upperLimit
for(int i=2;i<=nums.last();i++){
nums = remove(nums,i)
if(nums.size()==0){
break
}
}
return nums
}
def remove(nums,n){
return nums.findAll{it==n || it%n!=0}
}
Much better, but computing the 10001th Prime on my machine still took 90 seconds, meaning it would be much slower on an average machine. The solution above can be tweaked (if you’re removed the multiples of 2, there is no need to test for the multiples of 4 or 8 etc). However, I didn’t think that even that change would get me to 60 seconds, and in reality, it needed to be much less than 60 seconds to be considered an optimal solution. I begun to wonder how much Groovy’s dynamic Typing was costing me in performance.
The answer was, a lot. I re-wrote the the solution in Java (Java does not have Groovys awesome findall method/closure used in the remove method above, so it is a bit more verbose. In Java, the solution using Sieve of Erastothenes takes 4 seconds. The full solution is below (I doubt this is the optimal solution, but I think a run time of 4 seconds fulfills the ‘run under a minute’ requirement.
import java.util.ArrayList;
import java.util.Date;
public class MainApp {
import java.util.List;
/**
* @param args
*/
public static void main(String[] args) {
Date start = new Date();
Integer n = getNthPrime(10001);
Date end = new Date();
long totalTime = (end.getTime()-start.getTime())/1000;
System.out.println("Result = " + n);
System.out.println("Calculation took " + totalTime + " seconds");
}
static Integer getNthPrime(Integer n){
Integer stepSize = n;
Integer start = n*2;
Integer bottom = 2;
List<Integer> existingPrimes = new ArrayList<>();
List<Integer> primes = new ArrayList<>();
while(primes.size()<n){
existingPrimes = getPrimesTo(bottom,start);
if(existingPrimes.size()>0){
primes.addAll(existingPrimes);
}
bottom = start + 1;
start = bottom + stepSize -1;
}
return primes.get(n-1);
}
static List<Integer> getPrimesTo(Integer start,Integer upperLimit){
List<Integer>nums = new ArrayList<>();
for(int i=start;i<=upperLimit;i++){
nums.add(i);
}
for(int i=2;i<=nums.get(nums.size()-1);i++){
nums = remove(nums,i);
if(nums.size()==0){return nums;}
}
return nums;
}
static List<Integer> remove(List<Integer> nums,Integer n){
for(int i=0;i<nums.size();i++){
if(!nums.get(i).equals(n)){
if(nums.get(i).intValue()%n==0){
nums.remove(i);
}
}
}
return nums;
}
}