Я пытаюсь сделать достойную программу 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 ГГц.
Пока 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 стоил бы гораздо больше, если бы он сделал комментарии.
Использование BitSet потребует меньше памяти. Алгоритм Sieve довольно тривиален, поэтому вы можете просто «установить» битовые позиции в BitSet , а затем выполнить итерацию для определения простых чисел.
Вы могли бы сделать шаг «поместить соответствующий индекс в массив простых чисел», пока вы их обнаруживаете, выполняя пробег по массиву, но это почти все, о чем я могу думать прямо сейчас .
Следующее взято из моей библиотеки проекта Эйлера ... Это небольшая вариация сита Эратосфена ... Я не уверен, но Я думаю, это называется Решетом Эйлера.
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;
}
Готов поспорить, что производительность java ужасна при работе с битами... Алгоритмически, указанная вами ссылка должна быть достаточной
Вы пробовали гуглить, например для "простых чисел Java". Я сделал и откопал это простое улучшение:
http://www.anyexample.com/programming/java/java_prime_number_check_%28primality_test%29.xml
Конечно, вы можете найти больше в Google.
Вы также уменьшили массив, пропустив числа не в форме 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;
}