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

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

В данный момент мой алгоритм следующие:

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

Установите целое число, s равный самому низкому началу, (т.е. 2)

В то время как s <= sqrt (N)

Установите все кратные числа s (запускающийся в s^2) к истинному в array/bitarray.

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

Endwhile.

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

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

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

Править: Хорошо, вот мой фактический код (для 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;

Выполнения приблизительно в 350 мс на моей машине на 2.0 ГГц.

6
задан Rob 22 June 2010 в 16:09
поделиться

7 ответов

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

while (s <= sqrt(N)) {

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

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

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

update Хорошо, теперь о вашем коде.

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

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

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

update2
That's easy. Вы просто заменяете каждое присваивание 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 в этом. Не говоря уже о том, что этот парень использует много других хитрых оптимизаций, и я согласен, что его could стоил бы гораздо больше, если бы он сделал комментарии.

6
ответ дан 8 December 2019 в 15:59
поделиться

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

3
ответ дан 8 December 2019 в 15:59
поделиться

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

1
ответ дан 8 December 2019 в 15:59
поделиться

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

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;
} 
2
ответ дан 8 December 2019 в 15:59
поделиться

Готов поспорить, что производительность java ужасна при работе с битами... Алгоритмически, указанная вами ссылка должна быть достаточной

0
ответ дан 8 December 2019 в 15:59
поделиться

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

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

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

0
ответ дан 8 December 2019 в 15:59
поделиться

Вы также уменьшили массив, пропустив числа не в форме 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;
}
2
ответ дан 8 December 2019 в 15:59
поделиться
Другие вопросы по тегам:

Похожие вопросы: