Улучшение алгоритма простого сита

Question

Я пытаюсь создать приличную Java-программу, которая генерирует простые числа от 1 до N (в основном для задач Project Euler).

На данный момент мой алгоритм выглядит следующим образом:

Инициализируйте массив логических значений (или битовый массив, если N достаточно большой), чтобы они все были ложными, и массив целых чисел для хранения найденных простых чисел.

Установить целое число, равное наименьшему простому числу (т. Е. 2)

Пока s =

Установить для всех кратных s (начиная с s ^ 2) значение true в массиве / bitarray.

Найдите следующий наименьший индекс в массиве / bitarray, который равен false, используйте его в качестве нового значения s.

ENDWHILE.

Просмотрите массив / bitarray и для каждого значения, равного false, поместите соответствующий индекс в массив простых чисел.

Теперь я попытался пропустить числа не в форме 6k + 1 или 6k + 5, но это дает мне увеличение скорости примерно в 2 раза, хотя я видел, что программы работают на несколько порядков быстрее, чем моя (хотя с очень запутанным кодом), например, один здесь

Что я могу сделать, чтобы улучшить?

Редактировать: Хорошо, вот мой фактический код (для N 1E7):

int l = 10000000, n = 2, sqrt = (int) Math.sqrt(l);
boolean[] nums = new boolean[l + 1];
int[] primes = new int[664579];

while(n <= sqrt){
    for(int i = 2 * n; i <= l; nums[i] = true, i += n);
    for(n++; nums[n]; n++);
}

for(int i = 2, k = 0; i < nums.length; i++) if(!nums[i]) primes[k++] = i;

На моей машине с частотой 2,0 ГГц работает около 350 мс.

Answer 1

Пока s <<sqrt (N) </em>
Одна ошибка, которую люди часто делают в таких алгоритмах, это не предварительный расчет квадратного корня.

while (s <= sqrt(N)) {

намного, намного медленнее, чем

int limit = sqrt(N);
while (s <= limit) {

Но, вообще говоря, Eiko прав в своем комментарии. Если вы хотите, чтобы люди предлагали низкоуровневую оптимизацию, вы должны предоставить код.

обновление Хорошо, теперь о вашем коде.

Вы можете заметить, что количество итераций в вашем коде чуть больше, чем 'l'. (вы можете поместить счетчик внутри первого цикла for, он будет в 2-3 раза больше) И, очевидно, сложность вашего решения не может быть меньше, чем O (l) (вы не можете иметь меньше, чем 'l итераций).

Что может реально изменить, так это эффективный доступ к памяти. Обратите внимание, что парень, который написал эту статью, пытается уменьшить размер хранилища не только потому, что он жаден до памяти Создание компактных массивов позволяет лучше использовать кэш и, следовательно, увеличить скорость.

Я только что заменил логическое [] на int [] и добился немедленного увеличения скорости в 2 раза. (и 8x памяти) И я даже не пытался сделать это эффективно.

Update2
Это легко. Вы просто заменяете каждое присвоение a[i] = true на a[i/32] |= 1 << (i%32) и каждую операцию чтения a[i] на (a[i/32] & (1 << (i%32))) != 0. И boolean[] a с int[] a, очевидно.

Из первой замены должно быть понятно, как это работает: если f(i) истинно, то в целом числе a[i/32] есть бит 1, в позиции i%32 (int в Java точно 32 бита, как вы знаете).

Вы можете пойти дальше и заменить i/32 на i >> 5, i%32 на i&31. Вы также можете предварительно вычислить все 1 << j для каждого j в диапазоне от 0 до 31 в массиве.

Но, к сожалению, я не думаю, что в Java вы могли бы приблизиться к C в этом. Не говоря уже о том, что этот парень использует много других хитрых оптимизаций, и я согласен, что он мог бы стоить намного больше, если бы он сделал комментарии.

Answer 2

Использование BitSet будет занимать меньше памяти.Алгоритм Sieve довольно тривиален, поэтому вы можете просто «установить» позиции битов в BitSet , а затем выполнить итерацию для определения простых чисел.

Answer 3

Это из моей Библиотеки Проекта Эйлера ... Это небольшое изменение сита Эратосфена ... Я не уверен, но я думаю, что это называется Сито Эйлера.

1) Он использует BitSet (таким образом, 1/8 памяти) 2) Использует только набор битов для нечетных чисел ... (еще 1/2-й, следовательно, 1/16-й)

Примечание: Внутренний цикл (для кратных) начинается с "n * n", а не с "2 * n", а также кратные приращения "2 * n" только вычеркнуты .... следовательно, скорость увеличивается.

private void beginSieve(int mLimit) 
{ 
    primeList = new BitSet(mLimit>>1); 
    primeList.set(0,primeList.size(),true); 

    int sqroot = (int) Math.sqrt(mLimit); 
    primeList.clear(0); 
    for(int num = 3; num <= sqroot; num+=2) 
    { 
        if( primeList.get(num >> 1) ) 
        { 
            int inc = num << 1;
            for(int factor = num * num; factor < mLimit; factor += inc) 
            { 
                //if( ((factor) & 1) == 1) 
                //{ 
                    primeList.clear(factor >> 1); 
                //} 
            } 
        } 
    } 
} 

и вот функция для проверки, является ли число простым ...

public boolean isPrime(int num) 
{ 
    if( num < maxLimit)
    {
        if( (num & 1) == 0) 
            return ( num == 2); 
        else 
            return primeList.get(num>>1);
    }
    return false;
} 

Answer 4

Вы также сделали массив меньше, пропуская числа не в форме 6k + 1 и 6k + 5?Я тестировал только с игнорированием чисел в форме 2k, и это дало мне ~ 4-кратное ускорение (440 мс -> 120 мс):

int l = 10000000, n = 1, sqrt = (int) Math.sqrt(l);
int m = l/2;
boolean[] nums = new boolean[m + 1];
int[] primes = new int[664579];
int i, k;

while (n <= sqrt) {
  int x = (n<<1)+1;
  for (i = n+x; i <= m; nums[i] = true, i+=x);
  for (n++; nums[n]; n++);
}

primes[0] = 2;
for (i = 1, k = 1; i < nums.length; i++) {
  if (!nums[i])
    primes[k++] = (i<<1)+1;
}

Answer 5

Недавно я написал простую реализацию сита для удовольствия, используя BitSet (все говорят, что нет, но это лучший из готовых способов эффективного хранения огромных данных).Производительность мне кажется довольно хорошей, но я все еще работаю над ее улучшением.

public class HelloWorld {
    private static int LIMIT = 2140000000;//Integer.MAX_VALUE broke things.
    private static BitSet marked;

    public static void main(String[] args) {
         long startTime = System.nanoTime();
        init();
        sieve();
         long estimatedTime = System.nanoTime() - startTime;
        System.out.println((float)estimatedTime/1000000000); //23.835363 seconds
        System.out.println(marked.size()); //1070000000 ~= 127MB
    }

    private static void init()
    {
        double size = LIMIT * 0.5 - 1;
        marked = new BitSet();
        marked.set(0,(int)size, true);
    }

    private static void sieve()
    {
        int i = 0;
        int cur = 0; 
        int add = 0;
        int pos = 0;

        while(((i<<1)+1)*((i<<1)+1) < LIMIT)
        {
            pos = i;
            if(marked.get(pos++))
            {
                cur = pos;
                add = (cur<<1);
                pos += add*cur + cur - 1;
                while(pos < marked.length() && pos > 0)
                {
                    marked.clear(pos++);
                    pos += add;
                }
            }
            i++;
        }
    }

    private static void readPrimes()
    {
        int pos = 0;
        while(pos < marked.length())
        {
            if(marked.get(pos++))
            {
                System.out.print((pos<<1)+1);
                System.out.print("-");
            }
        }
    }
}

При меньших значениях LIMIT (скажем, 10 000 000, на которые ушло 0,077479 с) мы получаем гораздо более быстрые результаты, чем OP.

Answer 6

Вы могли бы сделать шаг «поместить соответствующий индекс в массив простых чисел», пока вы их обнаруживаете, выполняя пробежку по массиву, но это все, что я могу думать прямо сейчас.

Answer 7

Вот мой код для Sieve of Erastothenes, и это на самом деле самый эффективный из всех, что я мог сделать:

final int MAX = 1000000;
int p[]= new int[MAX];
p[0]=p[1]=1;
int prime[] = new int[MAX/10];
prime[0]=2;
void sieve()
{
    int i,j,k=1;
    for(i=3;i*i<=MAX;i+=2)
    {
        if(p[i])
            continue;
        for(j=i*i;j<MAX;j+=2*i)
            p[j]=1;
    }
    for(i=3;i<MAX;i+=2)
    {
        if(p[i]==0)
            prime[k++]=i;
    }
    return;
}

Answer 8

Вы пробовали гуглить, например для "простых чисел Java". Я сделал и выкопал это простое улучшение:

http://www.anyexample.com/programming/java/java_prime_number_check_%28primality_test%29.xml

Конечно, вы можете найти больше на Google.

Answer 9

Бьюсь об заклад, производительность Java ужасна при работе с битами ... С точки зрения алгоритма, указанная вами ссылка должна быть достаточной