筛选幸运数字

Question

我正在解决一个问题,即生成前n <1000000个幸运数字,但问题是它必须在2秒内生成它们,我尝试了不同的方法,但我总是超出时间限制,我是也考虑使用布尔但没有结果来改变这个算法.

在这里你可以找到幸运数字的筛子作为参考http://en.wikipedia.org/wiki/Lucky_number

幸运数字序列是以下1,3,7,9,13,15,21,25,31,33,37,43,49,51,63,67,69,73,75,79,87,93 ,99 ......

这是我使用ArrayList创建的低效的代码,如果你有任何提示我可以用来解决它,我会很感激.

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 + " ");
    }
  }
}

改进版本我改变了代码,每个人给了我的建议,我将算法的时间减少到13秒,但是仍然会减慢

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

使用标志数组(并且从筛子中消除时将每个元素设置为特殊值)将(可能)更快.这样您就不需要创建N个Integer对象,将它们添加到集合中,然后再次删除它们.

需要注意的一点是确定下一次迭代的"筛子"倍数......

其他几个答案讨论了从中删除元素时的低效率ArrayList.

另请注意,首先创建对象需要时间.创建一个int[]10M元素并为每个元素写一个值在我的系统上需要50ms,但对一个Integer对象数组做同样的操作需要1100ms,这只是你设置的目标时间的一半!

创建和填充10M元素ArrayList<Integer>需要1500毫秒,即使您预先调整大小,也LinkedList<Integer>需要3200毫秒,所以在您开始筛选之前就没时间了.

更新:尝试了这个(没有btilly建议的特殊外壳)它确实快得多,在8.6s中筛选1M输入数字,而35s中原始和10M输入数字的32.5s扫描,而原始数据为137s.

我也尝试使用位数组而不是int数组,这显然可以节省大量内存但速度只有一半.

另一个想法 - 关于质数筛子的SO有很多问题,也可能讨论类似的性能技术？