Повышение эффективности кода Sieve of Eratosthenes в Java - PullRequest
Новая
       1

Повышение эффективности кода Sieve of Eratosthenes в Java

3 голосов
/ 22 февраля 2012

Я работал над кодом для Сито Эратосфена в Java, но у меня возникли некоторые проблемы с эффективностью времени и пространства. Вот код: 

import java.util.*;

class EratosthenesSeive
{

    public static void main(String args[])
    {

        ArrayList<Long> myPrimeList = new ArrayList<Long>();
        ArrayList<Long> myTempPrimeList = new ArrayList<Long>();
        ArrayList<Boolean> isPrimeNumber = new ArrayList<Boolean>();
        int index = 0;

        long ul = 1500l;
        long ll = 2;

        do
        {
            myTempPrimeList.add(ll);
            isPrimeNumber.add(true);
            ll++;
        }while( ll != (ul+1));

        for(long i : myTempPrimeList)
        {
            if(isPrimeNumber.get(index))
            {
                myPrimeList.add(i);
                for(long j = i ; j*i <= ul; j++)
                {
                    isPrimeNumber.set(myTempPrimeList.indexOf(j*i),false);
                }
            }
            index++;
        }

        System.out.println(myPrimeList);
    }
}

Кажется, что он работает нормально для ввода до 10 ^ 3, при 10 ^ 4 просто зависает, а при 10 ^ 5 и выше я получаю OutOfMemoryError . И код, кажется, работает нормально, но я бы хотел еще немного его ускорить. Есть предложения?

Ответы [ 5 ]

4 голосов
/ 22 февраля 2012

Вы упаковываете / распаковываете тонну в этом коде.Вы можете попробовать заменить ArrayList<> на прямые массивы примитивного типа.

3 голосов
/ 22 февраля 2012

Одной из возможных оптимизаций будет замена списков массивов массивами примитивных типов, учитывая, что вы заранее знаете размер необходимых массивов. Это предотвратит ненужную упаковку / распаковку значений, присутствующих в вашем коде.

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

Для решения ошибки OutOfMemoryError вы можете поиграться с параметрами конфигурации JVM при запуске, предоставив больше места для кучи для приложения.

3 голосов
/ 22 февраля 2012

Удвойте скорость, не работая с четными числами.

1 голос
/ 23 февраля 2012

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

public void printPrimes(int max) {

    // declare a single array of booleans
    boolean[] primeFlags = new boolean[max + 1];

    // double loop sieve-style and mark non-primes as true
    for (int m = 2; m <= (int)Math.sqrt(max); m++) 
        for (int k = m*m; k <= max; k += m) primeFlags[k] = true;

    // loop over bool array and print indexes with false values 
    // which will be the prime numbers
    for (int m = 2; m <= max; m++)
        if (!primeFlags[m]) System.out.print(m + " ");
}
0 голосов
/ 30 декабря 2016 
import java.util.Scanner;

//Sieve Of Erastothenes

public class SieveOfErastothenes {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a range n : ");
        int n = sc.nextInt();

        boolean ar[] = new boolean[n+1];
        for (int i=2;i<=n;i++)
        ar[i] = true;

        for(int i = 2;i*i<=n;i++)
        {
            if(ar[i])
            {
                for(int j=i;i*j<=n;j++)
                    ar[i*j]=false;
            }
        }

        for(int i=2;i<=n;i++)
        {
            if(ar[i])
                System.out.print(i+" ");
        }
        sc.close();

    }

}

/*This code is contributed by Asish Samantaray*/
...