Tuesday, May 05, 2009

JavaOne Talk: Being Less Efficient

See previous post if you have not already. I was getting ready to post some of implementations of the prime sieve in other languages, when I realized I had probably unfairly over-optimized the Java solution by using arrays. This kind of optimization is available in some languages, but not others. So it would be hard to do a fair comparison if this optimization was used at all. So here is the Java prime sieve, but using resizable lists instead of primitive arrays:

import java.util.List;
import java.util.ArrayList;

public class Primes {
final private List<Integer> primes;
private final int size;

public Primes(int n){
size = n;
primes = new ArrayList<Integer>(n);
init();
}

private void init(){
int i=2;
int max = calcSize();
List<Boolean> nums =
new ArrayList<Boolean>(max);
for (int j=0;j<max;j++){
nums.add(true);
}
while (i < max && primes.size() < size){
int p = i;
if (nums.get(i)){
primes.add(p);
int j = 2*p;
while (j < max - p){
nums.set(j,false);
j += p;
}
}
i += 1;
}
}

public int last(){
return primes.get(primes.size()-1);
}

private int calcSize(){
int max = 2;
while ((max/Math.log(max)) < size &&
max < Integer.MAX_VALUE && max > 0){
max *=2;
}
return max;
}
}

No comments: