• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Sito Eratostenesa - przyspieszenie algorytmu

VPS Starter Arubacloud
0 głosów
1,226 wizyt
pytanie zadane 14 października 2016 w Java przez Wilier Bywalec (2,570 p.)

Hej, 

program ze strony SPOJ wyszukujący liczy pierwsze z zadanego przedziału. Wydaje mi się, że działa OK, problemem jest szybkość jego działania. Na stronie SPOJ dostaję info": time limit exeeded. Będę wdzięczny gdyby ktoś mógł rzucić okiem i dać jakąś wskazówkę jak go przyśpieszyć. 

p.s - przeraszam za brak konsekwencji w nazewnictwie 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * Created by Tomek on 10/13/2016.
 */

class Sieve
{
    private int[] tab;
    private int sqrt;
    int range=0;
    int down=0;

    Sieve(int down, int up)
    {
        this.down=down;
        range=up-down+1;
        sqrt = (int)Math.sqrt(up);
        tab = new int[range];
        for(int i=0; i<range; i++)
        {
            tab[i]=i+down;
        }
    }

    public void odsiew()
    {
        int index=2;
        while(index<=sqrt)
        {
            for(int i=0; i<tab.length; i++)
            {
                if(tab[i]==1)
                    tab[i]=0;
                if (tab[i] % index == 0 && tab[i]!= index)
                    tab[i] = 0;
            }
            index++;
        }
    }

    public void print()
    {
        for(int i=0; i<tab.length; i++)
        {
            if(tab[i]!=0)
                System.out.print(tab[i]+ " ");
        }
    }
}

public class PrimesNumbers
{
    public static void main(String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        int tests_cases = in.nextInt();
        int index=0;
        int num1;
        int num2;

        while(index<tests_cases)
        {
            num1=in.nextInt();
            num2=in.nextInt();

            Sieve sieve = new Sieve(num1, num2);
            sieve.odsiew();
            sieve.print();

            index++;
        }

        System.exit(0);
    }
}

 

2 odpowiedzi

+3 głosów
odpowiedź 17 października 2016 przez Benek Szeryf (90,690 p.)

Wydaje mi się, że działa OK, problemem jest szybkość jego działania.

Tak, działa OK, choć jest wolny z racji zastosowanego algorytmu. Wystarczy wejść na Wikipedię, przeczytać o algorytmie Eratostenesa i go zaimplementować. Przepisałem sobie Twój kod na Pythona i porównałem z moim własnym (wkleję je, bo mogą posłużyć jako pseudokody). Twój kod:

def sieve(down,up):
        sup = sqrt(up)
        tab = range(down,up+1)
        
        idx = 2
        while idx <= sup:
                for i in tab:
                        if i == 1:
                                tab[tab.index(i)] = 0
                        if not i % idx and i != idx:
                                tab[tab.index(i)] = 0
                idx += 1

sieve(2,1000000)

Mój kod:

koniec = 1000000
pierwsze = range(koniec + 1)
n = 1
while n < sqrt(koniec):
        n += 1
        m = n * 2
        while m <= koniec:
                pierwsze[m] = 0
                m += n

Dla N = 1000000 mój kod wykonał się w 2 sekundy, a na Twój mi się nie chciało czekać więcej niż minutę, więc przerwałem program. Zasoby są pożerane przez instrukcje warunkowe. U Ciebie za każdym razem sprawdzane są warunki, u mnie nie ma to miejsca. Po prostu wykreślam wielokrotności kolejnych liczb pierwszych, maskując je zerami. Ty robisz to samo, ale sprawdzasz warunki. A bierze się to stąd, że wprowadziłeś sobie zakres dolny i górny i ograniczasz się tylko do tego zbioru liczb pierwszych. Prościej byłoby iterować od 2 do N, na sam koniec ucinając początek listy.

komentarz 20 października 2016 przez Wilier Bywalec (2,570 p.)
edycja 20 października 2016 przez Wilier
dzięki, zaimplementowałem Twój kod w Javie i co ciekawe teraz dostaję Run Time Error więc coś jeszcze musze usprawnić
komentarz 20 października 2016 przez manjaro Nałogowiec (37,390 p.)
Chodzi może o to zadanie? http://pl.spoj.com/problems/DYZIO2/

Mój program w C++ liczy to w 0.06 sekundy a mimo to na spoju jest jednym z wolniejszych ;)
komentarz 20 października 2016 przez Wilier Bywalec (2,570 p.)
nie,

2 zadanie z listy, czyli Prime Generator

http://www.spoj.com/problems/PRIME1/
0 głosów
odpowiedź 17 października 2016 przez mbabane Szeryf (79,280 p.)
jesli chodzi o szybkosc to im mniej wywolan funkcji/metod/tworzenia_klas tym lepiej, wiec najprostszym przyspieszeniem bedzie wrzucenie wszystkiego w jedna metode (najlepiej main), nie tworzyc zadnych dodatkowych klas wszystko na zmiennych lokalnych wtedy nie bedzie narzutu zwiazanego z odkladaniem na stosie po zalaczeniu kolejnej metody i powrocie z niej (owszem kod bedzie wygladal duzo gorzej ale w tym wypadku nie ma to znaczenia).
komentarz 17 października 2016 przez Ehlert Ekspert (212,630 p.)
Szczerze wątpię, czy obiektowa implementacja ma wpływ na działanie programu.
komentarz 17 października 2016 przez mbabane Szeryf (79,280 p.)
Na samo dzialnie na pewno nie, no bo dzialac bedzie tak samo, ale na szybkosc juz bardziej,  nie zajmowalem sie nigdy sitem Eratostenesa wiec podalem co wiedzialem.

Podobne pytania

0 głosów
1 odpowiedź 6,236 wizyt
pytanie zadane 10 kwietnia 2017 w C i C++ przez Jakub 0 Pasjonat (23,120 p.)
0 głosów
0 odpowiedzi 229 wizyt
pytanie zadane 20 stycznia 2018 w SPOJ przez niezalogowany
0 głosów
0 odpowiedzi 205 wizyt
pytanie zadane 1 września 2022 w C i C++ przez Noizz00 Użytkownik (910 p.)

92,454 zapytań

141,262 odpowiedzi

319,089 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...