Oszukać czas!

Tutaj możesz podyskutować na tematy nie kwalifikujące się do żadnego z pozostałych forów

Oszukać czas!

Postautor: narbej » 03 lut 2015, 21:48

Nie, chyba nie da się ;-(

Nie wiem, czy dotknęła Cię kiedykolwiek taka sytuacja. Wysyłasz program na SPOJ'a, dostajesz AC z jakimś czasem. Po jakimś dłuższym lub krótszym czasie, czasami nawet parę dni, wysyłasz ponownie, dokładnie ten sam program [bez żadnej zmiany] i uzyskuje on o 0.01 sek czas lepszy. Możliwe, że to tylko mnie spotykało i spotyka. Możliwe, że Ciebie nie interesuje tak mała poprawka czasu. Dobierając dobry algorytm, można osiągnąć dużo większe przyśpieszenie, w stosunku do algorytmu gorszego.
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Re: Oszukać czas!

Postautor: zaro » 04 lut 2015, 13:01

Ja zauważyłem coś nieco innego i jestem ciekaw czy inni też tak mają.
Otóż wysyłając program za pierwszym AC mam czas załóżmy 0.26. Poprawiam nieco kod, a przynajmniej tak mi się wydaje np. zamieniam i++ na ++i, usunę jakieś jedno drobne sprawdzenie warunku itd. Dostaje czas 0.27. Cofam moje zmiany - wciąż 0.27 a czasem nawet 0.28.
Uznałbym to za wyjątkowe szczęście przy pierwszym wysłaniu gdyby taka sytuacja nie spotkała mnie już 3 razy, za każdym razem gdy próbowałem nieco przyśpieszyć w ten sposób kod.
Pamiętam że w którymś programie zamieniłem dwie pętle for, wywoływane jedna po drugiej na jedną robiącą to samo. Myślałem, że obsługa drugiej pętli zabiera jakieś tam niewielkie zasoby (sprawdzenie warunku końcowego, inkremetacja licznika).
Czas oczywiście +0.01 i nie mogę już zejść do starego czasu nawet pierwotnym programem. Możliwe przyczyny:

1. Spoj nalicza karę do czasu przy kolejnych wysyłaniach (możliwe, że to się też resetuje po pewnym czasie)
2. Nie wszystko jest takie oczywiste jak się wydaje - czasem dwie pętle 1..n mogą działać szybciej niż jedna 1..n, nawet jeśli robią dokładnie to samo.
3. Mam cholerne szczęście do dobrego czasu przy pierwszym AC :)
Obrazek
zaro
 
Posty: 6
Rejestracja: 30 mar 2014, 22:30

Re: Oszukać czas!

Postautor: arekbulski » 04 lut 2015, 15:18

Ewidentnie czasy się wachają ale to nie jest nic niespodziewanego. Wiele zjawisk ma na to wpływ. Nawet zawirowania powietrza wewnątrz dysku mają losowy wpływ na opóźnienia dysku (nie mówiąc o obracaniu talerza). Stworzono nawet generator prawdziwie losowy oparty na tym zjawisku. Nawet jeśli sędzia za każdym razem czyta pliki od początku, pomijając buffercache to dysk i tak będzie czasem szybszy. Jeśli inne procesy skaczą po pamięci (zamiast liczyć ciągle na tych samych zmiennych) to będą nasycać cache procesora nowymi cachelinami wydłużając czas dostępu do pamięci sędziemu. Wymieniać można bez końca. Chyba jedyne co pozostaje to wysłać kilka razy i może się trafi. Nie mamy kontroli nad tymi zjawiskami.
arekbulski
 
Posty: 3
Rejestracja: 04 lut 2015, 15:11

Re: Oszukać czas!

Postautor: spectral_ » 05 lut 2015, 19:28

zaro pisze:Ja zauważyłem coś nieco innego i jestem ciekaw czy inni też tak mają.
Otóż wysyłając program za pierwszym AC mam czas załóżmy 0.26. Poprawiam nieco kod, a przynajmniej tak mi się wydaje np. zamieniam i++ na ++i, usunę jakieś jedno drobne sprawdzenie warunku itd. Dostaje czas 0.27. Cofam moje zmiany - wciąż 0.27 a czasem nawet 0.28.
Uznałbym to za wyjątkowe szczęście przy pierwszym wysłaniu gdyby taka sytuacja nie spotkała mnie już 3 razy, za każdym razem gdy próbowałem nieco przyśpieszyć w ten sposób kod.

Mam nawet tak u siebie na komputerze. Jak mierzę czas wykonania jakiejś operacji, to zazwyczaj nie zadowalam się jednym pomiarem, a robię ich. np. 10 i wyciągam średnią. To co dziwne, to fakt, że zazwyczaj pierwsze uruchomienie programu wykonuje się najszybciej, a kolejne uruchamiane w bardzo krótkim odstępie czasu potrafią wykonywać się relatywnie dłużej i to znacznie dłużej. Oczywiście jestem świadom, że czynniki losowe wpływają na mierzony czas. Ale to zdarza się prawie zawsze i wybija się ponad losowość. Przypuszczam, że wytłumaczenie leży w działaniu procesora i pamięci. W takich sytuacjach pomiędzy kolejnymi uruchomieniami programu uruchamiam jeszcze coś innego(albo odczekuję dłuższą chwilę) i to o dziwo pomaga (przynamniej wyniki są bardziej zbliżone do tego pierwszego pomiaru).
spectral_
Organizator AlgoLigi
 
Posty: 18
Rejestracja: 15 lip 2014, 15:27

Re: Oszukać czas!

Postautor: kokosek » 06 lut 2015, 21:09

Dodatkowo, na nowym klastrze Cube, różne zgłoszenia wykonują się na różnych końcówkach w chmurze, więc również dają inne czasy. Ja mam dodatkową kolumnę która pokazuje na jakiej końcówce dane zgłoszenie zostało uruchomione, więc jak mi bardzo zależy to sobie submituję aż program wskoczy na najszybszą (wg moich testów) końcówkę.
kokosek
Koordynator AlgoLigi
 
Posty: 107
Rejestracja: 20 wrz 2012, 16:04


Wróć do Forum ogólne

Kto jest online

Użytkownicy przeglądający to forum: Google [Bot] i 1 gość

cron