7

Использую алгоритм решето Эратосфена. Поиск в диапазоне от 2 до 10000 выполняется 280 мс. Мне нужно найти все простые числа в диапазоне от 2 до максимального значения переменной INT. Использовать многопоточное программирование? Оптимизировать алгоритм?

import java.util.LinkedList;
import java.util.concurrent.LinkedBlockingDeque;

public class Primes {
private long timeout = System.nanoTime();
LinkedList<Integer> lprimes = new LinkedList<Integer>();
LinkedList<Integer> lnums = new LinkedList<Integer>();
public long getTimeout() {
    return timeout;
}

public void setTimeout(long timeout) {
    this.timeout = timeout;
}

public int getCountPrimes(){
    return this.lprimes.size();
}
public void timeRun() {
    System.out.println(System.nanoTime());
    System.out.println(timeout);
    System.out.println("Время выполнения равно " + String.valueOf(System.nanoTime() - this.timeout)+" ns или " + String.valueOf((System.nanoTime() - this.timeout)/1000000));
}

public void keepPrimes() {
    lnums.add(2);
    for(int i = 3;i <= 10000;i += 2){
           lnums.add(i);
    }
    /*for (int i = 2; i <= 10000; i++) {
        lnums.add(i);
    }*/
    while(lnums.size()>0){
        int nextPrime = lnums.remove();
        for (int i = nextPrime*nextPrime; i <=10000; i+=nextPrime) {
            lnums.removeFirstOccurrence(i);
        }
        lprimes.add(nextPrime);
        System.out.println(nextPrime);
    }
}

public static void main(String[] args) {
    // TODO Auto-generated method stub
    System.out.println("Максимальное значение INT: "+Integer.MAX_VALUE);
    Primes primes = new Primes();
    primes.keepPrimes();
    System.out.println("Формирование коллекции закончено!");
    primes.timeRun();
    System.out.println(primes.getCountPrimes());
}

}

3
  • 3
    А вы среди четных чисел тоже простые ищете, я смотрю? Commented 18 сент. 2016 в 14:12
  • перепишите всё на С и будет быстрее параллельной явы
    – sercxjo
    Commented 18 сент. 2016 в 15:43
  • 1
    нужно искать только среди чисел вида 6n+1 и 6n+5. Это дает ускорение в три раза.
    – KoVadim
    Commented 18 сент. 2016 в 16:14

3 ответа 3

10

Увы, я в Java не силен, разве что читать чужой код. Но...

Да, есть алгоритм решета Эратосфена O(n), но тут выигрыш по сравнению с хорошей реализацией - O(n lg lg n) - очень небольшой.

А вот оптимизировать ваш код не то что можно - нужно! Вы зачем-то собираете все нечетные числа в связанный список, а потом проверяете и убираете их из него. Зачем? Просто проходите по всем нечетным числам в списке. И проходите не до последнего числа (10000), а до квадратного корня! Этого достаточно. Смотрите, любое составное число, большее корня, должно иметь делитель, меньше корня - а значит, оно уже будет вычеркнуто. Все проверки для чисел от 100 и до 10000 просто не нужны...

И еще тоже очень большой минус - вы используете связанный список с постоянным динамическим выделением памяти, косвенными обращениями, долгим доступом к элементам и т.п. - что еще и не дает использовать кэш данных - решение, как по мне, нехорошее. Если бы это был C++, я бы использовал компактный vector<bool>, заранее зарезервировав необходимое количество памяти.

P.S. На C++ набросал - на моей домашней просчитало до 10000 за 16 мкс, до 100000000 - за 557 мс (без вывода на экран).

2
  • Спасибо за дельные советы! Использовать в программе связанный список было огромной ошибкой. Я решил от него отказаться и поступить как Вы указали. Commented 18 сент. 2016 в 17:53
  • 1
    @user2263662 Пожалуйста :) Если ответ решил проблему, можете пометить его галочкой :)
    – Harry
    Commented 19 сент. 2016 в 10:54
5

Вывод простых чисел от 2 до 2**31-1 на C

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#define lim INT32_MAX
#define BITS 32
int main()
{
    uint32_t *x= calloc(sizeof*x, ((unsigned)lim-3+BITS*2-1)/(BITS*2));
    fputs("2\n", stdout);
    for(unsigned i=3;i<=lim;i+=2) {
        unsigned b= i-3 >> 1;
        if(x[b/BITS] & 1<<b%BITS) continue;
        printf("%d\n", i);
        while( (b+=i) <= (lim-3>>1) ) x[b/BITS] |= 1<<b%BITS;
    }
}

Время счёта (Celeron T3100 @ 1.90GHz) 1,5 минуты, память примерно 128МиБ. Без вывода информации 58с.

Найдено 105097565 чисел

Улучшенный алгоритм: по совету @KoVadim поиск только среди чисел вида 6n±1.

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#define lim INT32_MAX
#define BITS 32
int main()
{
    uint32_t *x= calloc(sizeof*x, ((unsigned)lim-5+BITS*3-3)/(BITS*3));
    fputs("2\n3\n", stdout);
    for(unsigned i=5, b0=0; i<=lim; i+=6, b0++) {
        unsigned b=b0;
        if(!( x[b/(BITS/2)] & 1<<b%(BITS/2)*2 )) {
            printf("%d\n", i);
            while( (b+=i) <= (lim-5)/6 ) x[b/(BITS/2)] |= 1<<b%(BITS/2)*2;
            for(b=b0+2*i/3; b <= (lim-5)/6; b+=i) x[b/(BITS/2)] |= 2<<b%(BITS/2)*2;
        }
        b=b0;
        if(!( x[b/(BITS/2)] & 2<<b%(BITS/2)*2 )) {
            printf("%d\n", i+2);
            while( (b+=i+2) <= (lim-5)/6 ) x[b/(BITS/2)] |= 2<<b%(BITS/2)*2;
            for(b=b0+2*i/3+2; b <= (lim-5)/6; b+=i+2) x[b/(BITS/2)] |= 1<<b%(BITS/2)*2;
        }
    }
}

Время счёта 73 секунды, память 86МиБ. Без вывода информации 43с.

Обе программы выдают одинаковый результат в виде текста размером чуть больше 1ГБ. Хранение чисел в виде битового множества оказывается компактнее, чем массив из 105 миллионов чисел. Может быть имеет смысл его в таком виде и использовать далее.

2
  • Вы уж извините, но вопрос по оптимизации на языке программирования Java. Commented 20 сент. 2016 в 13:36
  • @user2263662 перевести на java не сложно, или в jni обернуть
    – sercxjo
    Commented 20 сент. 2016 в 14:35
4

Заинтересовал ответ sercxjo. Поигрался немного. На моей машине его код, скомпилированный VC++ 2015, работает (без вывода) 12 с. Там же мой вариант

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

constexpr inline unsigned long pow2(unsigned long i) { return 1 << i; }

unsigned long isqrt(unsigned long a)
{
    unsigned long x = a;
    for(unsigned long z = 0; x != z; )
    {
        z = x;
        x = (x + a/x)/2;
    }
    return x;
}

constexpr unsigned long MAX_LIM = pow2(31) - 1;
constexpr unsigned long ARR_LIM = (MAX_LIM >> 6) + 1;
const     unsigned long SQR_LIM = isqrt(MAX_LIM);;

unsigned long primes[ARR_LIM] = { 0 }; // 0 - простое, 1 - составное

auto set_primes = [](unsigned long idx)
    { primes[idx >> 6] |= pow2((idx&0x0000003F)>>1); };
auto get_primes = [](unsigned long idx)
    { return primes[idx >> 6] &  pow2((idx&0x0000003F)>>1); };

int main(int argc, const char * argv[])
{
    for(unsigned long i = 3; i <= SQR_LIM; i += 2)
    {
        if (get_primes(i)) continue;
        for(unsigned long j = i * i; j <= MAX_LIM; j += 2*i)
        {
            set_primes(j);
        }
    }

    puts("2");
    for(unsigned long i = 3; i <= MAX_LIM; i+=2)
    {
        if (get_primes(i)) continue;
        printf("%lu\n",i);
    }
}

считает (опять же, без вывода) 7.82 с. Результаты совпадает :)

Интересно, что если перебирать простые вида введите сюда описание изображения, то намечается даже проигрыш по времени...

Лямбды использовал сознательно - компилятор их очень хорошо оптимизирует.

Следующим номером должно быть просеивание через решето Эратосфена с использованием шаблонов во время компиляции :) Кто готов взяться?

1

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.