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);

private void init(){
int i=2;
int max = calcSize();
List<Boolean> nums =
new ArrayList<Boolean>(max);
for (int j=0;j<max;j++){
while (i < max && primes.size() < size){
int p = i;
if (nums.get(i)){
int j = 2*p;
while (j < max - p){
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: