Sep 2017
1 / 7
Sep 2017
Sep 2017
onwroclaw
Sep '17

Robie to zadanie po raz N ty i nigdy nie udało mi sie zmieścić w czasie.
Piszę w języku java . Jest wzór na obliczanie liczb pierwszych w przedziale ale nie jest on dokładny . A wydaje mi sie że zoptymalizowałem swój program do maximum . Wyszukuje liczby pierwsze tylko raz do konca przedziału który ma największy koniec . Liczby pierwsze obliczam przez dzielenie przez liczby pierwsze mniejsze od kwadratu sprawdzanej liczby . Potem gdy mam liczby pierwsze w tablicy prosto je segreguje do przedziałów . Czy da sie szybciej ?

  • created

    Sep '17

  • last reply

    Sep '17
  • 6

    replies

  • 604

    views

  • 3

    users

  • 2

    links

tarpauwatratar
Sep '17

Ja robię to w C++ w czasie O(1) + preprocessing. Ściślej, na każde zapytanie o przedział odpowiadam w czasie stałym. Poza tym w moim kodzie nie ma dzielenia. Czas 0.00. Zadanie da się zrobić w Javie. Nie wiem co to znaczy “segreguję do przedziałów”, ale brzmi to jak coś o złożoności mocno przekraczającej O(1).

Ponieważ temat jest założony niezgodnie z zasadami to jak coś mówię o zadaniu http://pl.spoj.com/problems/DYZIO2/17

mariusz193
Sep '17
1

zadałeś pytanie i otrzymałeś na nie odpowiedź

nie pytałeś jak to zrobić - zresztą na takie pytanie prawdopodobnie nikt ci nie odpowie, a w każdym razie nie powinien - to ty masz rozwiązać problem (ale mam wrażenie że gdzieś na forum jest już odpowiedź)

onwroclaw
Sep '17

Wczytanie danyh juz zajmuje mi 0,33 s a dodanie jednej petli to juz 0,35 ;/ to normalne ?

tarpauwatratar
Sep '17

Jedyne co mogę powiedzieć to że z pewnością jest to normalne dla metod(y?), które(ą?) stosujesz :wink:

Tutaj masz wyniki różnych ludzi w Javie. Jeżeli jesteś w stanie choć oszacować ile czasu zajmuje Ci wczytanie wejścia (a z tego co widzę to jesteś w stanie) to z łatwością oszacujesz ile czasu masz na obliczenia i wyplucie outputu.

Nie wiem jak mogę Ci pomóc, aby nie zostać ponownie oskarżonym o prawienie nieużytecznych truizmów i banałów. Jeżeli w kodzie faktycznie coś dzielisz to może zastanów się nad metodą pozwalającą usunąć tą kosztowną operację? Wszak do rozwiązania tego zadania operacja ta jest zupełnie zbędna. Może następnie warto zrobić jakieś fast IO?

Oczywiście zakładam (być może zbyt optymistycznie), że ogarniasz Javę i SPOJa w takim stopniu, iż nie robisz jakiejś krytycznej głupoty typu zbędna pętla albo pięć, tablicowanie czegoś zupełnie niepotrzebnego itd.

onwroclaw
Sep '17
1

Może ktoś jeszcze podpowiedzieć czy używanie scaner jest dobrym pomysłem czy jest zbyt powolne? (nie aktualne poprawiłem wczytywanie rezygnując ze skanera)