java - 幸运数字筛

Question

我正在解决一个问题，它包含生成第一个 n<1000000 个幸运数字，但问题是它必须在不到 2 秒的时间内生成它们，我尝试了不同的方法，但我总是超过时间限制，我也在考虑使用 boolean 值更改此算法但没有结果。

在这里你可以找到幸运数字筛作为引用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 秒，100 万，但仍然很慢

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[] 1000 万个元素并向每个元素写入一个值在我的系统上需要 50 毫秒，但对 Integer 的数组执行相同操作对象需要 1100 毫秒，这是设置目标时间的一半以上!

创建和填充 10M 元素 ArrayList<Integer>需要 1500 毫秒，即使你预先调整它的大小，一个 LinkedList<Integer>需要 3200 毫秒，所以您甚至在开始筛分之前就没时间了。

更新:尝试过这个(没有 btilly 建议的特殊外壳)它确实快得多，在 8.6 秒内筛选 1M 输入数字，而原始的 32.5 秒和 1000 万个输入数字在 35 秒内，而原始数据为 137 秒。

我还尝试使用位数组而不是 int数组，这显然可以节省大量内存，但速度只有一半左右。

另外一个想法——SO上有很多关于素数筛的问题，可能也会讨论类似的性能技术？