[baalder363]

#java #spoj #algorytmy #pytanie #programowanie #informatyka

http://pl.spoj.com/problems/PZPI3/ robię sobie to zadanko ze spoja i jest chyba ok, ale wywala "przekroczono limit czasu". Ma ktoś jakiś pomysł w jakim kierunku mógłbym to zoptymalizować? Nie chodzi mi o gotowca, ale wskazówki, gdzie się zastanowić. https://pastebin.com/SrYjZFdt otoż mój kod.

[ppawel]

@baalder363:
Nie wczytywałem się w treść zadania, ale często w tego typu zadaniach chodzi o znalezienie sposobu na rozwiązanie problemu przy mniejszej złożoności obliczeniowej - przykładowo w Twoim rozwiązaniu jest pętla w pętli co może skutkować złożonością obliczeniową typu O(n^2) (nie analizowałem skąd się biorą numerek... ale pesymistycznie zakładam że może być ich nawet n, no chyba że jest jeszcze gorzej)...
Czasem pełne rozwiązanie takich zadań polega na zauważeniu

[mudzo]

@baalder363: Spróbowałbym zacząć od czytania wejścia. Może lepiej przeczytać całe od razu następnie podzielić na linie (split('\n')) i dopiero iterować po kolekcji linii.

potem odpuściłbym ze zbieraniem dzielników do kolekcji tylko od razu je sumował w zmiennej i inkrementował jakiś licznik.

[A.....t]

@baalder363 słaby algorytm obliczania dzielników

[A.....t]

@baalder363 jeśli jakaś liczba n dzieli się przez 2, to dzieli się też przez n/2, nie trzeba sprawdzać dzielników >sqrt (n)

[Patres]

@baalder363: Nie czytałem polecenia, ale w Twoim kodzie widzę duże Integery i Double. Może warto by je zamienić na int i double a Listy na tablice, choć wątpię żeby dało to znaczący skok na szybkości.

[baalder363]

@Patres: @AwizisieAkat: @mudzo: @ppawel: Dzięki, pokombinuję

[Minemaniak1]

@baalder363: Masz przekroczenie limitu, bo to nie jest prawidlowe rozwiazanie. Nawet jak bedziesz sprawdzal tylko do sqrt(n), to i tak masz zlozonosc O(t*sqrt(n)*(b-a)). Zdecydowanie za duzo. Nie myslalem nad rozwiazaniem, ale tutaj musi chodzic o policzenie wczesniej dla kazdej liczby czy jest znaczaca, stablicowanie tego (sumy prefiksowe) i odpowiadanie na zapytania w O(1). Ale tablicowanie do 10^9 moze byc za wolne, nawet jak uzyjesz sita liniowego a nie erastotenesa. Byc

[63274682374]

@baalder363: w metodzie isSignificant() niepotrzebnie zbierasz te liczby do kolekcji, żeby je potem sumować. Sumuj od razu w jednej zmiennej a w drugiej zapisuj ich liczbę. Na koniec podziel jedno przez drugie i masz średnią.
Ta jedna zmiana przyspieszy twój kod co najmniej o rząd wielkości.

Z takich drobnostek, które nie mają w tym wypadku dużego wpływu na wydajność ale jednak rzucają się w oczy:
- integer.valueOf zwraca Integer, Integer.parseInt()

[GotoFinal]

@Patres: w javie to daje całkiem spory skok wydajności, nawet kilkukrotny jak się operuje tylko na obiektowych.

[63274682374]

obiektowych

@GotoFinal: *prymitywnych

[GotoFinal]

@63274682374: dobrze było, tylko może ogólnie słabo zapisane i się myli. Bo chodziło o to że jest znaczący skok wydajnościowy kiedy używa się prymitywów niż kiedy operuje się tylko na typach obiektowych.