Napisałem "ostatnio" rozwiązanie do zadania MPOWER i z wielkim rozczarowaniem zobaczyłem czas 6.72, a tabelce są rozwiązania z czasem 0.00 Moglibyście mnie trochę nakierować na jakieś materiały lub dać jakieś drobne wskazówki jak można zmodyfikować mój program, żeby chociaż zbliżył się do takiego czasu?
Obecny kod: Było, ale już nie ma, Najwięcej czasu zajmuje w nim zamiana decimal -> binary, lecz nie wiem jak można to wyeliminować / przyspieszyć. Wątpię, żeby scalenie pojedynczych cyfr oryginalnego y w 32bit inty dało x100 przyspieszenie.
EDIT: Dobra, myliłem się. Wykorzystanie pełnych intów daje mi wynik 0.81, czyli około x8.3 przyspieszenie. Jednak dalej nie jest to 0.00 Nowy shitcode: Było, ale już nie ma.
EDIT: long long podwoiło prędkość (0.40), a unsigned long long dało jedynie niewielkie przyspieszenie (0.38). Jak mogę to jeszcze bardziej przyspieszyć? Obecny kod: [już nieobecny]
Moim skromnym zdanie należy [powinieneś] zrezygnować z binarnej reprezentacji wykładnika. Do szybkiego potęgowania, potrzebujesz tylko informacji o parzystości wykładnika i czy wykładnik jest jeszcze większy od zera, po podzieleniu przez 2. Do tego wystarczy reprezentacja wykładnika w prostych BIGnumber - tylko dzielenie przez dwa, [oraz bBIGnumber & 1/// <-- sprawdzanie parzystości, a to masz prawie z automatu].
W tym momencie mam coś takiego: [kiedyś był tu link, ale już go ni mo] Wyszło na to, że to jest wolniejsze (0.39) niż konwertowanie do reprezentacji binarnej, chociaż omijam trochę operacji na vectorze...
Z reguły, nie umieszczamy tu kodów AC. W takim razie, jak masz się pytać, o to o co pytasz? Nie wiem, nie mam pojęcia i mało mnie to obchodzi. Sam pomyśl. Może pokazując tylko samą klasę lub jakiś inny fragment swojego kodu, z odpowiednim wyjaśnieniem i pytaniem?
Pomagający powinien mieć zaliczone zadanie pytającego [w tym samym języku i tu z wynikiem co najmniej 0.00 ]. Możesz sam sprawdzić, że mam tylko 0.06 w pythonie.
Jeżeli twoim priorytetem jest 0.00 i z uwagi na pkt 2 i 3, i mimo, że twój kod nie podoba mi się, umywam ręce od dalszego wytykania Ci błędów w kodzie i wskazywania poprawek stylu - które mogą ale nie muszą, przyczynić się do "zbliżenia" do 0.00. W końcu masz AC, a kiedyś na pewno sam dostrzeżesz te drobiazgi.
Mój kod Ci się nie podoba? Pomijając fakt, że ten kod nie był pisany po to, żeby był częścią jakiegoś frameworka, to zamiast pisać, że Ci się nie podoba, mogłeś napisać konstruktywną krytykę, co jest w nim według Ciebie nieładne i w jaki sposób to można zmienić.
Słabym byłbyś nauczycielem, bo wymagasz za dużo perfekcji od kogoś, kto nawet nie wie o co ma zapytać, żeby znaleźć odpowiedź, wszakże gdybym wiedział, to bym nie pytał. Kiedyś na pewno sam zrozumiesz na czym polega pomaganie
Zamiast mnie [konstruktywnie?] krytykować, mogłeś o to zapytać, a przecież, wypowiedź zacytowana powyżej nie jest pytaniem.
Możliwe, że masz rację, ale zauważ, że czymś innym jest ["lekkie"] pomaganie, podpowiadanie i naprowadzanie [na SPOJU], a zupełnie czymś innym uczenie i nauczanie.
Rzeczywiście masz rację. Nie można mieć pewności, że to co wyżej, a także, że "...sam dostrzeżesz te drobiazgi", kiedykolwiek, na pewno, się sprawdzi
PS Oczywiście nie muszę odpowiadać na taką krytykę mojej osoby, ale tak czy siak drastycznie uszczupla to moje [i tak coraz marniejsze] zasoby i chęci na udzielanie jakichkolwiek [p]odpowiedzi. Satysfakcja z pomagania plus krytyka, zamiast prostego podziękowania, to w tym momencie trochę [za]mało.
PS 2
De gustibus non disputandum est. [O gustach się nie dyskutuje].
dawno, dawno temu (czyli lat 10) napisałem wersję siłową - wynik 2 punkty, trudniejsze testy miały TLE obecnie ta sama wersja dostała 10 w czasie 4 sekund
już wtedy wiedziałem, jakie powinno być poprawne rozwiązanie, ale nie chciało mi się poświęcić 3 godzin czasu - ja wolno piszę
obecnie zdopingowany tą dyskusją napisałem rozwiązanie prawdopodobnie zgodnie z intencjami autora - czas 0.00
Witam. Chciałbym się podpiąć pod powyższy temat. Nad zadaniem MPOWER siedzę już dość długo (chyba wybrałem sobie za trudne zadanie, jak na moje niewielkie póki co doświadczenie) i najlepszy czas jaki uzyskałem dotychczas to 5,79s (język: C++).
Ale po kolei: nie chcę, żeby wyszło, że jestem leniem, który szuka prostej metody na wymasterowanie czasu w zadanku. Nic z tych rzeczy - chcę po prostu zgłębić tajniki algorytmiki, które musiały mi umknąć (różnica 5,79s a 0,00s raczej nie wynika z prostej jakiejś optymalizacji...).
Zacząłem od kombinowania nad algorytmem, który podołałby wyzwaniu. Wyprowadziłem sobie nawet wzorki, żeby mieć podparcie od strony matematycznej. Wyszedł mi taki kodzik: http://ideone.com/2q10Db12 - kod trochę niezbyt czytelny dla osoby postronnej, bo jest tu masa własnej arytmetyki. Kod ten nieźle się spocił podczas próby siły: 5,92s.
Dwa dni wytężonej pracy później przeszedłem już chyba przez wszystkie możliwe podejścia do tego zadania... Ale dotarłem trochę okrężną drogą na skraj "hiperoptymalizacji" wcześniejszego kodu. Czas? 5,79s. Załamałem się w tym momencie.
Czytając tutaj wątek ucieszyłem się nawet, zwłaszcza poniższą wypowiedzią:
W sumie to byłem blisko, nawet bardzo blisko A jednocześnie tak daleko.
Doszedłem do wniosku, że najwięcej problemu w programie sprawia funkcja dzieląca liczbę (zapisaną w stringu) przez 2. void DzielPrzezDwa(string& my) { int a, b=0; for(int i=0; i<my.length(); i++) { a = (int)my[i] - 48 + b; b = 0; my[i] = (a/2) + 48; if(a%2==1) b = 10; } if(my[0]==48) my.erase(0, 1); } A sprawia tyle kłopotu dlatego, że musi być wywoływana niesamowicie dużą ilość razy... a to marnuje zasoby, dużo, bardzo dużo zasobów.
Dlatego też próbowałem bawić się w przekształcenie liczby od razu na system binarny. Wczytywać każdą cyfrę wykładnika osobno; razy 10; wczytaj następną i dodaj ją do liczby, którą masz w pamięci; razy 10; wczytaj następną i dodaj ją do liczby, którą masz w pamięci; i tak aż do napotkania chara odpowiadającego spacji. Kodzik: http://ideone.com/ZfRM6a - uwaga! kod strasznie bije po oczach, zwłaszcza, że liczbę w systemie binarnym trzymam tu w stringu. Ale i tutaj także spotkał mnie zawód. time limit exceeded ;/ Chciałem się pozbyć dzielenia przez dwa, a tymczasem zmieniłem go po prostu na inny problem, tyle że gorszy.
Lista rzeczy, których próbowałem: - własna arytmetyka - póki co na drodze ewolucji kodu dało mi to najlepszy czas - konwersja dec -> bin - zbyt czasochłonna - arytmetyka modularna - w sumie sam doszedłem do podobnego algorytmu, zanim się jeszcze dowiedziałem, że jest coś takiego - twierdzenie eulera - liczby muszą być względnie pierwsze... - chińskie twierdzenie o resztach - niestety nie potrafię dojść do tego jak to może mi pomóc.
Ah. Podsumujmy to może trochę, bo już ta wypowiedź urosła do pokaźnych rozmiarów. Co ja tu robię nie tak? Czy czegoś nie dostrzegam? Czego mi brakuje?
Co w nim złego? Maks punktów przy niewielkim doświadczeniu to spory sukces. Sekunda wte czy wewete...
Tajnikiem algorytmiki może być informacja o algorytmach służących do potęgowania liczb. Chociaż czy w dobie internetów to taki tajnik?
Optymalizacja nie dotyczy algorytmu a jego implementacji i siłą rzeczy wybiega poza algorytmikę. Co innego napisać rozwiązanie w assemblerze, a co innego w Pythonie. Co innego zastosować obiektówkę uwzględniajacą dziedziczenie i metody wirtualne, a co innego napisać rozwiązanie w sposób proceduralny. W przypadku takiego C++ istnieje spora (w sensie czasu na SPOJu oraz znaczenia tych operacji) różnica między ++x a x++.
Ja rozwiązałem to zadanie dawno temu w 1.00 s, co wg mnie nie jest dobrym czasem, ale po prostu nie chce mi się śrubować czasów Mój kod kończy się klamrą w linii 1040, a Twój w linii 72. Ja oparłem rozwiązanie na własnego pomysłu klasie do arytmetyki wielkoliczbowej (a właściwie jej fragmencie o takiej długości), a Ty stworzyłeś proste i ciekawe rozwiązanie.
Kiedy nie ma czym Częścią profesjonalnego tworzenia optymalnych rozwiązań są właśnie eksperymenty, które na ogół kończą się jak wszystkie eksperymenty Nie ma jakiejś uniwersalnej recepty czy też naukowej teorii na podkręcanie czasów albo tworzenie prostych implementacji złożonych rzeczy.
Dzielenie jest z różnych względów wolne, podobnie jak operacje na stringach. Nie mam niestety czasu wgryźć się w kod, ale samo erase ma złożoność "Unspecified, but generally up to linear in the new string length.".
Jeżeli już czegoś Ci brakuje to dystansu do czasów innych userów
brakuje ci uważnego czytania odpowiedzi - bo przecież napisałem jaki algorytm ma decydujący wpływ na czas obliczeń - zbyt szybko go odrzuciłeś, więc jeszcze poświęć trochę czasu i pomyśl jak go zastosować
Gdy chcemy uzyskać lepszy [krótszy] czas wykonannia programu [tu na SPOJ'u] najczęściej robimy to metodą prób i błędów. I często przynosi to dobre efekty. Gdy mamy wieksze doświadczenie jest to o wiele łatwiejsze, ale mimo wszystko nie jest to łatwe. Najlepsze efekty przynosi ulepszenie czy zmiana algorytmu. Jeżeli poprawiamy kod, to powinniśmy zacząć od znalezienia "wąskiego gardła" i poprawienia tego miejsca. Do takich poszukiwań potrzebujemy programu [profilera] i odpowiednio dużego testu: https://pl.wikipedia.org/wiki/Profilowanie_%28in%C5%BCynieria_oprogramowania%292, http://www.is.umk.pl/~grochu/wiki/doku.php?id=zajecia:npr_2013_2:wyklad:plan3
Nawet bez profilera [z doświadczenia] wiem, że często wąskim gardłem jest na SPOJ'u i/o.
Przyśpieszanie i/o: 1. cin/cout <-- dodanie do programu instrukcji ios::sync_with_stdio(0); 2. zastąpienie cin/cout szybszymi scanf/printf 3. użycie "fast i/o" np getchar_unlocked() 4. [szybkie] wczytanie od razu całego wejścia
Poprawienie algorytmu: Jeżeli wiesz, że funkcja dziel przez dwa jest problemem, to musisz ją koniecznie poprawić, a tu jest jeszcze bardzo duże [DUUŻE] pole do popisu [może później coś napiszę]?.
No czasu nie marnuję Kombinuję nad tym cały czas - zmieniłem nieco algorytm, więc uwolniłem się od funkcji dziel przez dwa na dobre. Wykorzystuję okresowość reszty z dzielenia celem szybszego uzyskania odpowiedzi. Nieco ulepszone twierdzenie eulera. Ulepszone tak by działało dla całej podanej dziedziny.
Mam teraz jednak trochę inny problem... błędna odpowiedź. Dla podanych przykładów działa bez zarzutu. Ba, sam wymyślam cały czas różne przykłady, głównie tak przekombinowane jak tylko można, i to poskutkowało tym, że odkryłem kilka błędów w kodzie. Drobnych, ale istotnych. Dalej kombinuję nad kolejnymi możliwie trudnymi przykładami, ale kod za każdym razem zwraca prawidłowy wynik.
Mógłby ktoś podrzucić jakąś listę przykładowych testów? Chcę sam dojść do tego gdzie ukrywa się ten ostatni(?) błąd. Oczywiście sam także popróbuję jakichś testów.
PS. Błąd, o którym wspomniałem wynikał z błędu w kodzie przez który dla liczb n (dzielnik), które w swoim rozkładzie na czynniki pierwsze miały czynnik będący liczbą pierwszą większą od sqrt(2^30), czyli 2^15 (tj. około 32 tysiące) zaczynał wariować. Błąd znaleziony i poprawiony zanim jeszcze wysłałem zadanie na spoja. Spoj jednak w dalszym ciągu daje teraz 0 pkt.
EDIT: Teraz to już się porobiło... Memory: 0k Jaka jest maksymalna ilość razy jaką można wrzucać zadania? Jest jakiś limit? Prośba o testy nadal aktualna.
Coś mi się wydaje, że idziesz w złym kierunku. Przeczytaj dokładnie i uważnie dziedzinę wejścia zadania.
Nic mi o tym nie wiadomo, więc pewnie nie ma [mam dużo! więcej zgłoszeń].
Masz AC. Wiesz na czym się wykłada ta wersja więc po co ci testy? Testy przykładowe w treści w tym zadaniu powinny wystarczyć a jeżeli nie, to łatwo zrobić prosty generator i twój program AC może wygenerować prawidłowy output.,
Nie wiem, do czego CI to w ogóle potrzebne? Przecież n <= 2^30
Kliknij w kolumnie RESULT w 0 w napisie 0 (limit: 2) i będziesz wiedział jaki [jakiego rodzaju] masz problem.
Za chwilę napiszę sobie ten generator testów, żeby liczył wartości dla nowego algorytmu oraz starego, a w przypadku niezgodności tych wyników powiadamiał o problemie.
Ehh... Dziwna sprawa. Może w ten sposób przynajmniej sprawa się wyklaruje. Dla około 100 testów jakie wrzuciłem do tej pory wszystkie wyniki się zgadzały. Połowa to były losowe liczby, a reszta to misternie uknute liczby, które specjalnie miały sprowokować program do wysypania się... Ale tego nie zrobił. Może generator coś interesującego znajdzie.
Jeśli chodzi o wynik jaki podaje mi spoj, to cóż, ale moim oczom ukazuje się następująca sytuacja: "1) 2.0 ptswrong answer (0.00s : 1s) 2) 8.0 ptswrong answer (0.00s : 15s) Score: 0" BTW: O co chodzi z tym, że niby zużycie pamięci wyniosło 0k? To jest jakiś bug sprawdzajki, tak?
No właśnie rzecz w tym, że nie mam zielonego pojęcia na czym on się wykłada...
Pewnie tak, chociaż i tak masz przecież w tym wypadku 0 pkt to jakie to ma znaczenie?
Komuś z "zewnątrz" możliwe, że łatwiej byłoby znaleźć buga w twoim kodzie i wtedy przygotować "perfidny" [obnażający ten błąd] test, niż wymyślać go od zera. Chyba, że przypadkiem ktoś natknął się już na podobny problem i faktycznie ma taki test. Oczywiście możliwe, że po prostu dużo łatwiej naprawić bug nawet bez własnych testów i wysłać kolejny raz zmieniony [poprawiony] kod do sprawdzenia na SPOJ'a.
Generator pomógł. Znaczy się wiem już przynajmniej na czym program się wykłada. To już postęp. Teraz pozostaje tylko znaleźć fragment kodu odpowiedzialny za taki stan rzeczy i lecimy z tym koksem. Ale to już chyba zostawię sobie na jutro.
EDIT: Ok, dzięki wielkie. To byłoby na tyle. Program chodzi gorzej niż się spodziewałem, ale wszystko wyszło na plus. Przy okazji sporo się nauczyłem. Może kiedyś wrócę do tego zadania, żeby wyśrubować ten czas i osiągnąć 0,00s.
May '17
Sep '17
- warto przeczytać o pewnym chińskim twierdzeniu
]. Możesz sam sprawdzić, że mam tylko 0.06 w pythonie. 
A jednocześnie tak daleko.
Jeszcze raz dzięki za poradę!