Rozmowy na temat prac konkursowych |
Rozmowy na temat prac konkursowych |
6.11.2010, 14:52:50
Post
#81
|
|
Grupa: Moderatorzy Postów: 6 070 Pomógł: 860 Dołączył: 10.12.2003 Skąd: Dąbrowa Górnicza |
Zatem można wliczyć na zdrowo rozsądkowe podejście do Waszych prac. No i jakaś iskierka nadziei pozostaje. Ja osobiście nie upieram się, że prace typu jak moja muszą (nawet złe słowo!) być wzięte pod uwagę, ale zdrowo rozsądkowe podejście byłoby oczywiście mile widziane. Cóż - pozostaje nam czekać. Jakby nie było to konkurs był super pomysłem i mnie osobiście nauczył bardzo wiele. Coprawda w pracy codziennej nadal będę używał strlen zamiast while ale jednak sporo do głowy weszło. |
|
|
6.11.2010, 17:05:17
Post
#82
|
|
Grupa: Zarejestrowani Postów: 812 Pomógł: 117 Dołączył: 2.12.2008 Ostrzeżenie: (10%) |
No i jakaś iskierka nadziei pozostaje. Ja osobiście nie upieram się, że prace typu jak moja muszą (nawet złe słowo!) być wzięte pod uwagę, ale zdrowo rozsądkowe podejście byłoby oczywiście mile widziane. Cóż - pozostaje nam czekać. Trzymam kciuki, żeby tak było. Jakby nie było to konkurs był super pomysłem i mnie osobiście nauczył bardzo wiele. Coprawda w pracy codziennej nadal będę używał strlen zamiast while ale jednak sporo do głowy weszło. Co do strlen, czytam to co piszesz i nie mogąc w to uwierzyć robie własne testy, których wyniki prezentuję poniżej. Testowałem 8 skryptów, 6 z nich analogicznych do 2 poniższych:
założenia: $n = 1e6; Każdy z kodów uruchomiony 10 razy. Wyniki to średnia i odchylenie. wyniki pomiarów: Kod av: 0.423 [s] sd: 0.012 [s] _strlen 1e1.php av: 0.426 [s] sd: 0.027 [s] _strlen 1e2.php av: 0.425 [s] sd: 0.014 [s] _strlen 1e3.php av: 0.433 [s] sd: 0.019 [s] _strlen 1e4.php av: 1.208 [s] sd: 0.010 [s] _while strlen 1e1.php av: 11.386 [s] sd: 0.253 [s] _while strlen 1e2.php av: 113.773 [s] sd: 1.262 [s] _while strlen 1e3.php av: 1178.517 [s] sd: 26.398 [s] _while strlen 1e4.php Wniosków można było się spodziewać: - strlen cechuje się praktycznie zerowym (pomijalnie małym do wykonania funkcji itd.) wpływem długości ciągu wejściowego na czas wykonywania, - czas wykonania zliczania przy pomocy while jest liniowo zależny od długości ciągu, - pętla while ma szanse wygrać z strlen przy ciągach o długości około 5 i mniejszych. Przypominam jeszcze raz, że wyniki podawane tu na forum są tylko poglądowe a rzeczywiste wyniki mogą się sporo różnić, ponieważ nie znamy testów. Ten post edytował flashdev 6.11.2010, 20:58:30 -------------------- |
|
|
6.11.2010, 17:19:06
Post
#83
|
|
Grupa: Moderatorzy Postów: 6 070 Pomógł: 860 Dołączył: 10.12.2003 Skąd: Dąbrowa Górnicza |
Przyznam, że nie testowałem strlen vs while na długich ciągach znaków. Maksymalna długość to była ok. 30 znaków. Możliwe więc, że jest jak piszesz i wydajność while jest wprost proporcjonalna co długości ciągu, podczas gdy wydajność strlen jest bardziej stabilna. Gdzieś wyczytałem, że strlen po drodze dokonuje kilku dodatkowych operacji (m.in. zamienia znaki na małe) wobec czego szukałem alternatywnego rozwiązania.
Generalnie mój kod miał wiele odmian Przykładowo parametry KWAZ zapisywałem jako tablicę, później próbowałem utworzyć z nich stałe, jednak okazało się, że najlepiej wypada po prostu dynamiczne (poprzez $$) tworzenie zmiennych. Do tego cieszyłem się z obsługi 2 specyficznych sytuacji, w których mógłbym deklasować inne rozwiązania: 1. Zakończenie dekodowania ciągu w momencie zebrania wszystkich parametrów, czyli dla np. K3W3A3Z3XXXXXXXXXXXXXXXXXXX kończymy w momencie dotarcia do pierwszego X. 2. Osobne generowanie prostokątów dla min = max. Zobaczymy jak to będzie |
|
|
6.11.2010, 17:29:16
Post
#84
|
|
Grupa: Zarejestrowani Postów: 812 Pomógł: 117 Dołączył: 2.12.2008 Ostrzeżenie: (10%) |
Przyznam, że nie testowałem strlen vs while na długich ciągach znaków. Maksymalna długość to była ok. 30 znaków. Możliwe więc, że jest jak piszesz i wydajność while jest wprost proporcjonalna co długości ciągu, podczas gdy wydajność strlen jest bardziej stabilna. Gdzieś wyczytałem*, że strlen po drodze dokonuje kilku dodatkowych operacji (m.in. zamienia znaki na małe) wobec czego szukałem alternatywnego rozwiązania. Generalnie mój kod miał wiele odmian Przykładowo parametry KWAZ zapisywałem jako tablicę, później próbowałem utworzyć z nich stałe, jednak okazało się, że najlepiej wypada po prostu dynamiczne (poprzez $$) tworzenie zmiennych. Do tego cieszyłem się z obsługi 2 specyficznych sytuacji, w których mógłbym deklasować inne rozwiązania: 1. Zakończenie dekodowania ciągu w momencie zebrania wszystkich parametrów, czyli dla np. K3W3A3Z3XXXXXXXXXXXXXXXXXXX kończymy w momencie dotarcia do pierwszego X. 2. Osobne generowanie prostokątów dla min = max. Zobaczymy jak to będzie * - mam nadzieję, że nie w manualu Co do 1 i 2 punktu to prawda, że mogło to pomóc, ale nie wiadomo jakie są testy. Nie wiadomo, czy ten zysk będzie większy niż czas na wykonanie tych 1k if`ów. Żeby mieć jakieś wnioski trzebaby założyć, że np. - długość ciągu jest losowa od 1 do 10k (przy większych u mnie nie działa), - parametry w ciągu są rozmieszczone losowo, - rozkłąd prawdopodobieństwa wylosowania danej liczby jest równomierny. I z takimi założeniami można już robić jakieś obliczenia/symulacje. A powyższe założenia są w miarę sensowne, ponieważ zakładam, że te testy generował komputer a nie człowiek. Ten post edytował flashdev 6.11.2010, 17:35:30 -------------------- |
|
|
6.11.2010, 19:38:57
Post
#85
|
|
Grupa: Moderatorzy Postów: 6 070 Pomógł: 860 Dołączył: 10.12.2003 Skąd: Dąbrowa Górnicza |
* - mam nadzieję, że nie w manualu Nie, nie był to manual. Nie wiem również ile w tym jest prawdy. Jeśli chodzi o ciąg wejściowy, to nie będzie on raczej generowany losowo. Przynajmniej ja będąc na miejscu organizatorów ułożyłbym kilka różnych ciągów sprawdzając reakcję programu w różnych warunkach. Takie 3 sztandarowe przykłady to właśnie: - K3W3A1Z5XXXXXXXXXXX - czyli parametry podane na samym początku (można optymalizować poprzez przerwanie wyszukiwania), - XXXXXK3W3A1Z1XXXXXX - czyli min = max (nie ma potrzeby odpalania całego algorytmu budowania prostokątów), - no i jakiś "normalny" zestaw parametrów dla wygenerowania prostokątów. Ja przyjąłem, że tego typu zestawy otrzymamy |
|
|
6.11.2010, 23:25:18
Post
#86
|
|
Grupa: Zarejestrowani Postów: 24 Pomógł: 3 Dołączył: 2.02.2009 Ostrzeżenie: (0%) |
Cóż, powili zaczynam żałować, że zupełnie nie miałem czas na optymalizację skryptu. Można pewnie dużo się nauczyć. O np. to:
Wniosków można było się spodziewać: - strlen cechuje się praktycznie zerowym (pomijalnie małym do wykonania funkcji itd.) wpływem długości ciągu wejściowego na czas wykonywania, - czas wykonania zliczania przy pomocy while jest liniowo zależny od długości ciągu, - pętla while ma szanse wygrać z strlen przy ciągach o długości około 5 i mniejszych. Dziękuję za umieszczenie tego tutaj, byłem tego bardzo ciekaw. Gdy wcześniej usłyszałem, że użycie while może być szybsze niż strlen to pomyślałem sobie, że z PHP chyba musi być coś poważnie nie tak. A teraz wszystko jasne, według mnie, wyniki są logiczne. Ten post edytował ernie242 6.11.2010, 23:26:30 |
|
|
7.11.2010, 21:38:43
Post
#87
|
|
Grupa: Zarejestrowani Postów: 1 387 Pomógł: 273 Dołączył: 18.02.2008 Ostrzeżenie: (0%) |
@phpion, mógłbyś spróbować przeprowadzić te testy prędkości jeszcze raz, tym razem bez xdebug? Przetestowałem kilka kodów za pomocą zwykłej pętli (100000 iteracji) i buforowania wyjścia, a Twój kod, choć w czołówce - wcale nie wyszedł najszybszy.
-------------------- XMPP: l0ud@chrome.pl
|
|
|
8.11.2010, 00:16:37
Post
#88
|
|
Grupa: Zarejestrowani Postów: 592 Pomógł: 62 Dołączył: 3.08.2006 Ostrzeżenie: (0%) |
możesz zamieścic wyniki
-------------------- :]
|
|
|
8.11.2010, 23:35:09
Post
#89
|
|
Grupa: Zarejestrowani Postów: 3 Pomógł: 0 Dołączył: 26.10.2010 Ostrzeżenie: (0%) |
Witam wszystkich!!!!
Jestem tu nowy, ale też wysłałem pracę na konkurs. Niestety też jest błąd - zrozumiałem, że kody KWAZ mogą być tylko wielkimi literami, a szum różnie - stąd skrypt nie robi toUpper - i pewnie na tym polegnie. Ale może ktoś z kolegów będzie umiał ocenić szybkość tego skryptu
|
|
|
8.11.2010, 23:40:49
Post
#90
|
|
Grupa: Zarejestrowani Postów: 1 387 Pomógł: 273 Dołączył: 18.02.2008 Ostrzeżenie: (0%) |
Wyników nie dam, ale kod którym sprawdziłem 2 pierwsze prace i swoją z ciekawości:
http://wklej.org/id/415396/ Czyżbym źle mierzył, czy to xdebug powoduje narzut i związane z tym przekłamania? [edit] chrix, po teście - Twój kod działa przeciętnie szybko Inna sprawa, że aby to sprawdzić musiałem wywalić tą całą funkcję z globalem. Ten post edytował l0ud 8.11.2010, 23:51:49 -------------------- XMPP: l0ud@chrome.pl
|
|
|
9.11.2010, 00:46:26
Post
#91
|
|
Grupa: Zarejestrowani Postów: 3 Pomógł: 0 Dołączył: 26.10.2010 Ostrzeżenie: (0%) |
Wielkie dzięki!!!
no to chyba nie najgorzej. Założenie zawarcia skryptu w funkcji to przyjęcie ryzyka, że jej wywołanie zajmie mniej czasu parserowi php, niż sprawdzanie każdej zmiennej w tablicy globali, jak to ma podobno miejsce w kodzie na zewnątrz funkcji. Z regulaminu wynika, że program będzie wywoływany w testach z konsoli samodzielnie Kod php.exe -f test.php COSTAMKOD > itd
|
|
|
9.11.2010, 18:13:55
Post
#92
|
|
Grupa: Zarejestrowani Postów: 5 Pomógł: 0 Dołączył: 3.11.2010 Ostrzeżenie: (0%) |
Jak dla mnie sposób pomiaru zaproponowany w regulaminie jest niezbyt dobry. Zakładając, że kod będzie w stylu:
to: 1. Czas wykonania fork() z php zajmuje ponad 95% całości czasu! 2. Pomiar czasu jest obarczonym dużym błędem sięgającym 5% na moim systemie (Ubuntu 10.10, Core i5-720). 3. Przykładowo mój program wykonuje się w 12.8s a zwykły "Hello World" 12.4s. 4. Porównuję czas wykonania dwóch programów w którym każdy w środku ma pętlę 1000 razy to różnica między nimi wynosi 25%, tj. jeden 0.4s a drugi 0.5s. I teraz proponowanym sposobem pomiaru program pierwszy wykonuję się w czasie 12.8s a drugi 12.9s. Rożnica wynosi 0.75%! Ponadto pamiętajmy o punkcie drugim! Podsumowując, czas pierwszego programu mieści się w przedziale [12.5, 13.1], a drugiego [12.6, 13.2]. Więc który wygra? Mam nadzieję, że popełniłem błąd w tym wywodzie, bo jeśli nie, to Jury będzie wybierać najładniejszy kod i na nic zdadzą się nasze wyrafinowane optymalizacje. |
|
|
9.11.2010, 18:54:41
Post
#93
|
|
Grupa: Przyjaciele php.pl Postów: 5 724 Pomógł: 259 Dołączył: 13.04.2004 Skąd: N/A Ostrzeżenie: (0%) |
@kaliberx: całkowicie sie z toba zgadzam. W regulaminie pisze ze program (jako calosc) bedzie odpalana 1000 razy, a nie sama "funkcja". I to niweluje kompletnie roznice miedzy rozwiazaniami.
Z tego powodu dałem sobie spokój z optymalizacjami po kilku godzinach. -------------------- Nie lubię jednorożców.
|
|
|
10.11.2010, 21:12:02
Post
#94
|
|
Grupa: Zarejestrowani Postów: 24 Pomógł: 3 Dołączył: 2.02.2009 Ostrzeżenie: (0%) |
Jak dla mnie sposób pomiaru zaproponowany w regulaminie jest niezbyt dobry. Zakładając, że kod będzie w stylu: Ok, ale jest napisane tylko, że będzie uruchamiany 1000 razy. Nic nie ma o tym JAK to będzie wykonane. Mogą użyć skryptu w Bash. Make. Rakefile. Cokolwiek innego... |
|
|
10.11.2010, 21:15:09
Post
#95
|
|
Grupa: Przyjaciele php.pl Postów: 5 724 Pomógł: 259 Dołączył: 13.04.2004 Skąd: N/A Ostrzeżenie: (0%) |
Cytat Mogą użyć skryptu w Bash. Make. Rakefile. Cokolwiek innego... To juz bez roznicy - najwieksza roznica jest miedzy odpalaniem skryptu 1000x jako "php -r plik.php" lub jako funkcja w petli odpalana 1000x. AFAIR to w dokumentacji pisali ze czytac mamy z $argv, i odpalane bedzie jako "php -r plik.php CIAG_ZNAKOW" -------------------- Nie lubię jednorożców.
|
|
|
17.11.2010, 20:23:24
Post
#96
|
|
Grupa: Zarząd Postów: 2 277 Pomógł: 6 Dołączył: 27.12.2002 Skąd: Wołów/Wrocław |
Wyniki zostały ogłoszone. http://wortal.php.pl/Wortal/Aktualnosci/Wy...ien-2010-wyniki
Serdeczne gratulacje dla nagrodzonych, i gorące podziękowania wszystkim, którzy wzięli udział. Pozdrawiam serdecznie -------------------- "Niezależnie od tego, jakie masz osiągnięcia, ktoś Ci pomaga..."
|
|
|
18.11.2010, 17:58:27
Post
#97
|
|
Grupa: Zarejestrowani Postów: 23 Pomógł: 0 Dołączył: 9.02.2004 Skąd: Toruń Ostrzeżenie: (0%) |
Po cichutku, bez dużego udzielania się na tym forum znalazłem się na 5. miejscu.
Wynik OK bez fail'ów. Kod zwarty i cały czas miałem zgryz bo go skracałem zamiast optymalizować. Pewnie wymiana jakiegoś drobniutkiego rozwiązania w moim kodzie pozwoliłaby na przyspieszenie go o te pół sekundy jakie mi zabrakło przy 1000 wywołań Wklejam całość tutaj oraz przez link: http://wklej.org/id/421468/ 5. miejsce i kusi mnie strasznie chęć chwalenia się - ajajaj Pozdrawiam!! Gratulacje!! dla zwycięzców oraz dla 4. miejsca --- także zamieść swój kod Jesteś lepszy ode mnie o 0.16 sekundy, hehehe
-------------------- pauluZ
|
|
|
18.11.2010, 18:05:45
Post
#98
|
|
Grupa: Przyjaciele php.pl Postów: 5 724 Pomógł: 259 Dołączył: 13.04.2004 Skąd: N/A Ostrzeżenie: (0%) |
Masz calkiem sexi kod
Kod $sek_s .= $i;
-------------------- Nie lubię jednorożców.
|
|
|
18.11.2010, 19:39:16
Post
#99
|
|
Grupa: Moderatorzy Postów: 6 070 Pomógł: 860 Dołączył: 10.12.2003 Skąd: Dąbrowa Górnicza |
Masz calkiem sexi kod Kod $sek_s .= $i; Hehehe, dobre Na spokojnie w domu postanowiłem jeszcze raz odpalić testy. Sprawdziłem tylko te prace, które były przede mną i które zostały upublicznione. Oto wyniki. 1. Sumaryczne czasy dla każdego wejścia (1000 wywołań): Kod +-----------------------------------------------------+------------------+ | script | sum_ti | +-----------------------------------------------------+------------------+ | phpion.php?in=Y5LU61ZGYAKM9C6Y6IWU3ZPC95LDGM0MT3V | 1.50808167457590 | | phpion.php?in=ZPPUXLMR2S93NEBWCIXOCKWFM | 1.96194171905514 | | ogaws.php?in=Y5LU61ZGYAKM9C6Y6IWU3ZPC95LDGM0MT3V | 1.97012424469003 | | pauluZ.php?in=Y5LU61ZGYAKM9C6Y6IWU3ZPC95LDGM0MT3V | 2.07399821281427 | | kaliberx.php?in=Y5LU61ZGYAKM9C6Y6IWU3ZPC95LDGM0MT3V | 2.16468429565446 | | ogaws.php?in=ZPPUXLMR2S93NEBWCIXOCKWFM | 2.24561262130736 | | pauluZ.php?in=ZPPUXLMR2S93NEBWCIXOCKWFM | 2.44730377197269 | | kaliberx.php?in=ZPPUXLMR2S93NEBWCIXOCKWFM | 2.50407171249373 | | phpion.php?in=C0DNQDYNZOKH4T2PU57682QKFH8C3 | 2.59955668449399 | | ogaws.php?in=C0DNQDYNZOKH4T2PU57682QKFH8C3 | 2.78515815734878 | | kaliberx.php?in=C0DNQDYNZOKH4T2PU57682QKFH8C3 | 2.95505619049084 | | pauluZ.php?in=C0DNQDYNZOKH4T2PU57682QKFH8C3 | 3.51078677177436 | +-----------------------------------------------------+------------------+ 2. Już widać, że dla każdego zestawu jestem na czele, ale podsumowanie totalne: Kod +--------------+------------------+ | script | sum_ti | +--------------+------------------+ | phpion.php | 6.06958007812503 | | ogaws.php | 7.00089502334617 | | kaliberx.php | 7.62381219863903 | | pauluZ.php | 8.03208875656132 | +--------------+------------------+ Oczywiście przy tych testach nic nie kombinowałem żeby "przyspieszyć" swój kod. Jak widać co test (część z Was podawała wyniki własnych testów) to inne dane :/ |
|
|
18.11.2010, 19:47:11
Post
#100
|
|
Grupa: Zarejestrowani Postów: 1 319 Pomógł: 118 Dołączył: 26.11.2003 Skąd: Lublin Ostrzeżenie: (0%) |
Hehehe, dobre Na spokojnie w domu postanowiłem jeszcze raz odpalić testy. Sprawdziłem tylko te prace, które były przede mną i które zostały upublicznione. Oto wyniki. 1. Sumaryczne czasy dla każdego wejścia (1000 wywołań): Kod +-----------------------------------------------------+------------------+ | script | sum_ti | +-----------------------------------------------------+------------------+ | phpion.php?in=Y5LU61ZGYAKM9C6Y6IWU3ZPC95LDGM0MT3V | 1.50808167457590 | | phpion.php?in=ZPPUXLMR2S93NEBWCIXOCKWFM | 1.96194171905514 | | ogaws.php?in=Y5LU61ZGYAKM9C6Y6IWU3ZPC95LDGM0MT3V | 1.97012424469003 | | pauluZ.php?in=Y5LU61ZGYAKM9C6Y6IWU3ZPC95LDGM0MT3V | 2.07399821281427 | | kaliberx.php?in=Y5LU61ZGYAKM9C6Y6IWU3ZPC95LDGM0MT3V | 2.16468429565446 | | ogaws.php?in=ZPPUXLMR2S93NEBWCIXOCKWFM | 2.24561262130736 | | pauluZ.php?in=ZPPUXLMR2S93NEBWCIXOCKWFM | 2.44730377197269 | | kaliberx.php?in=ZPPUXLMR2S93NEBWCIXOCKWFM | 2.50407171249373 | | phpion.php?in=C0DNQDYNZOKH4T2PU57682QKFH8C3 | 2.59955668449399 | | ogaws.php?in=C0DNQDYNZOKH4T2PU57682QKFH8C3 | 2.78515815734878 | | kaliberx.php?in=C0DNQDYNZOKH4T2PU57682QKFH8C3 | 2.95505619049084 | | pauluZ.php?in=C0DNQDYNZOKH4T2PU57682QKFH8C3 | 3.51078677177436 | +-----------------------------------------------------+------------------+ 2. Już widać, że dla każdego zestawu jestem na czele, ale podsumowanie totalne: Kod +--------------+------------------+ | script | sum_ti | +--------------+------------------+ | phpion.php | 6.06958007812503 | | ogaws.php | 7.00089502334617 | | kaliberx.php | 7.62381219863903 | | pauluZ.php | 8.03208875656132 | +--------------+------------------+ Oczywiście przy tych testach nic nie kombinowałem żeby "przyspieszyć" swój kod. Jak widać co test (część z Was podawała wyniki własnych testów) to inne dane :/ a moj kod? tez dawalem, ale dam jeszcze raz, moze stworzymy jawna liste, jesli nikt nie ma nic przeciwko 12 miejsce, a kod: http://wklej.org/id/412341/ Ten post edytował Daimos 18.11.2010, 19:47:40 -------------------- scriptun.com. Startup z poradnikami do gier ttp.zone i ttpzone.pl
|
|
|
Wersja Lo-Fi | Aktualny czas: 28.04.2024 - 03:36 |