sieve of lucky numbers

Question

I'm solving a problem that consist in generate the first n<1000000 lucky numbers, but the problem is that it have to generete them in les than 2 seconds, I've tried different ways but I always have time limit exceeded, I was thinking also of changing this algorithm using Boolean but no results.

here you can find the sieve of lucky numbers as a reference http://en.wikipedia.org/wiki/Lucky_number

the lucky numbers sequence is the following 1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, 87, 93, 99...

this is the code I created using ArrayList the inefficient one, if you have any hint that I can use to solve it, in time, I would appreciate it.

public class Luckyumbers {
  public static void main(String[] args) {
    ArrayList<Integer> numbers = new ArrayList<Integer>();
    Integer max = 200000;
    int b;
    int c = 0;
    int p;

    for (int i = 1; i <= max; i += 2) {
      numbers.add(i);
    }

    // System.out.println(numbers);
    Integer bbb = 3;
    Integer j = numbers.size();
    int a = 3;
    while (bbb < j) {
      b = numbers.size();
      p = 1;

      for (int i = bbb; i < b; i += bbb) {
        numbers.remove(i-p);
        p = p + 1;
      }
      b = numbers.size() - 1;
      c = numbers.get(b);
      j = j - numbers.size() / bbb;
      bbb = numbers.get(a-1);
      a = a + 1;
      //  System.out.println(numbers);
    }

    for (int k = 0; k < numbers.size(); k++) {
      int z = numbers.get(k); 
      System.out.print(z + " ");
    }
  }
}

Improved version I changed the code with the suggestions that everyone gave me and I reduced the time of the algorithm to 13 seconds for 1 million but stills to slow

public static void main(String[] args) {
        int max= 1000000;
        boolean[] numbers = new boolean[max];
        for (int i = 2; i < numbers.length; i+=2) 
            numbers[i]=true;
        int k=2,j=0,l=0,ant=0;
        int p=0;
        for (int i = 2; (k+k) < numbers.length; i++) {

            k=which(numbers,i);
            l=0;
            p=0;
            int sw=0;
            boolean untrue=false;
            for (j = l; l < numbers.length; j++) {
                if((p==k)&&sw==1){
                    numbers[l]=true;
                    untrue=true;
                                        p=0;
                }
                l=Next(numbers,l);
                //if (sw ==1)
                    p++;
                sw=1;
            }
            if (!untrue)
                break;
        }
                System.out.println(counter(numbers));
    }

    static int which(boolean[] numbers,int i){
                int k=0;
        int l;
        for (l = 0; l < i; l++) {
            k=Next(numbers,k);
        }
        return k;
    }
    static int Next(boolean[] numbers,int i){
        for (int l = i+1; l < numbers.length; l++) {
            if (numbers[l]==false)
                return l;   
        }
        return numbers.length+1;
    }

    static int counter(boolean[] numbers){
        int c=0;
        for (int j = 1; j < numbers.length; j++)    
            if(numbers[j]==false)
                c++;
        return c;
    }
}

Answer 1

It will (probably) be much faster to use an array of flags and set each element to a special value when eliminated from the sieve. That way you don't need to create N Integer objects, add them to a collection, then remove them again.

The bit to be careful with will be determining the 'sieve' multiple for the next iteration...

Several other answers discuss the inefficiencies when removing elements from an ArrayList.

Note also that creating the objects in the first place takes time. Creating an int[] of 10M elements and writing a value to each element takes 50ms on my system, but doing the same with an array of Integer objects takes 1100ms, which is over half of your target time just for the set-up!

Creating and populating an 10M-element ArrayList<Integer> takes 1500ms, even when you pre-size it, and a LinkedList<Integer> takes 3200ms, so you're out of time before you even start sieving.

Update: having tried this (without the special casing suggested by btilly) it is indeed much faster, sieving 1M input numbers in 8.6s versus 32.5s for the original and 10M input numbers in 35s versus 137s for the original.

I also tried using a bit array rather than an int array, which obviously saves a lot of memory but was about half the speed.

Another thought - there are a lot of questions on SO about prime number sieves, which may also discuss similar performance techniques?

Answer 2

Nice sequence, these lucky numbers (+1). Since I was wondering whether a boolean array is optimal, I used an array that holds the index to the next element that has not yet been filtered out, see implementation below. With this, I do not have to iterate over the whole array for each number 2,3,7,9,... but can jump over segments of the array that have already been filtered out.

public class LuckyNumbers {

    List<Integer> result;
    int sieveSize = -1;

    public LuckyNumbers(final int length) {
        sieveSize = length;
        result = new ArrayList<Integer>();
        final int[] sieve = new int[sieveSize];
        int oldIndex = 1;
        //initialize: each array-element points to the next index; index corresponds to number (ignore sieve[0] for simplicity)
        for (int index = 2; index <= sieveSize; index++) {
            sieve[oldIndex] = index;
            oldIndex = index;
        }
    }

    private void computeWithSieve() {
        int oldIndex = 1;
        // filters are 2,3,7,9,...
        for (int filter = 2; filter < sieveSize; filter = sieve[filter]) {
//          System.out.println("Filter " + filter);
            int moduloCounter = 1;
            oldIndex = -1;
//          if outdated filter-indexes are not set to -1: use filter == 2 ? 3 : sieve[filter] instead
            for (int index = 1; index < sieveSize; index = sieve[index]) {
                assert moduloCounter <= filter;
                if (moduloCounter == filter) {
                    moduloCounter = 1;
                    assert oldIndex > 0;
                    sieve[oldIndex] = sieve[index];
                    //unnecessary: sieve[index] = -1;
                    //jump back to oldIndex, such that nextElement() in the loop finds the correct successor:
                    index = oldIndex;
                } else {
                    oldIndex = index;
                    moduloCounter++;
                }
            }
        }
//      for (int index = 1; index < sieveSize; index = sieve[index]) {
//          result.add(index);
//      }
    }


    public String toString() {
        return result.toString(); 
    }

    public static void main(String[] args) {
        int size = (args.length == 0 || args[0] == null ? 100000 : new Integer(args[0]));
        LuckyNumbers ln = new LuckyNumbers(size);
        long start = System.currentTimeMillis();
        ln.computeWithSieve();
        System.out.println(System.currentTimeMillis() - start + "milliseconds required for " + ln.result.size());
//      System.out.println("Sieve: "+ln);
    }
}

Unfortunately, I can only compute lucky numbers up to 100.000 within 2 seconds. But then again, just initializing an 1000000-elements array requires almost 1 second on my slow computer. So I don't think the time box of 2 seconds is feasible.

Answer 3

Using an ArrayList to do that is inefficient because each time you remove an element from the list, all the other numbers in the list must be copied to the previous position. Using a LinkedList could help, but it would be faster if you just used an array and put some marker value (-1 for example) at the indices that must be removed. If you try with a LinkedList, make sure to never call the get() method, though, but to use an iterator instead and remove the element using the Iterator's remove method.

Also, using a List forces to constantly transform from int to Integer and vice-versa.

You could also gain some time by setting the initial size of the ArrayList to the correct value. Otherwise, it forces it to make a copy of the internal array each time it has to expand.

Answer 4

Every time you call remove, you are invoking an O(n) operation, because all the elements after the one being removed need to be shifted, one by one, towards the beginning of the array. Try using a LinkedList to improve the performance of this. However, then, the get operation will be O(n). Try using iterators to remedy that. (You'd have to perform iterator.next() manually seven times to come to the seventh element from the current one, but it'll be worth it.)

Your performance is O(n^3) right now, with LinkedList it should be O(n^2). Rationale:

• For every removal, you have an O(n) operation.
• You perform n/k removals where k is the current number by which you are sieving, so you do the removal O(n) times.
• There are O(n) numbers by which to sieve, however, this number is much smaller than n, I'm not sure if their number is in O(log(n)) as well.

With a LinkedList the first operation is O(1).