Pomoc - Szukaj - Użytkownicy - Kalendarz
Pełna wersja: Rozmowy na temat prac konkursowych
Forum PHP.pl > Inne > Opinie, ogłoszenia, pytania > Konkursy
Stron: 1, 2, 3
dr_bonzo
IMO

Dużo programów odpadnie na teście dokładnościowym.

Potem będzie loteria.

A na koniec wygra najladniejszy kod.
Pawel_W
Cytat(dr_bonzo @ 4.11.2010, 18:53:36 ) *
Jakis dowod?

to chyba akurat łatwo sprawdzić smile.gif gdzieś na forum nospor o tym napominał smile.gif
dr_bonzo
To czekam na kod. I wskazanie ile zyskam zamieniajac for -> while w tych programach.
qba10
Cytat(sever88 @ 4.11.2010, 15:21:35 ) *
Mój kod:
http://pastebin.com/AbQs4AjL

Nie mam żadnych specjalnych tricków.
Kolejne cyfry wrzucam na wybrane pozycje w stringu. Kod rozkodowuję na bieżąco sprawdzając czy jest interesujący znak. Tworzenie prostokątów jest dosyć sprawne, ale wynik w głównej mierze będzie zależał od rozszyfrowywania.
Pierwsza połowa kodu odpowiada za szyfr mimo że na to nie wygląda, po prostu są wykorzystywane te same nazwy zmiennych w obu częściach programu smile.gif

@phpion - fajne sztuczki wymyśliłeś, Twój kod wygląda mi na faworyta smile.gif

Twój kod dla kodu UMUAAM4G9Z zwraca mi :

Kod
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000

00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000

00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000

A powinien
Kod
01234567890123456789
56789012345678901230
43456789012345678941
32345678901234567052
21256789012345678163
10149012345678989274
09038567890123090385
98927434567894101496
87816323456705212507
76705212567816323618
65694101498927434729
54583090321038545830
43472989876549656941
32361876543210767052
21250765432109878163
10149876543210989274
09032109876543210385
98987654321098765496
87654321098765432107
76543210987654321098

90909090909090909090
81818181818181818181
72727272727272727272
63636363636363636363
54545454545454545454
45454545454545454545
36363636363636363636
27272727272727272727
18181818181818181818
09090909090909090909
90909090909090909090
81818181818181818181
72727272727272727272
63636363636363636363
54545454545454545454
45454545454545454545
36363636363636363636
27272727272727272727
18181818181818181818
09090909090909090909

98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
jasin
Wszyscy wrzucają to i ja smile.gif
Wiem, że nie jest to super kod ale nie miałem czasu by go "dopieszczać" więc wyszło co wyszło.
http://pastebin.com/b95U9DK9
flashdev
Cytat(dr_bonzo @ 4.11.2010, 19:37:17 ) *
To czekam na kod. I wskazanie ile zyskam zamieniajac for -> while w tych programach.


Kod
dane z 10 pomiarow
av:    1.389[s]    sd:    0.019[s]    _pusta petla for.php
av:    0.724[s]    sd:    0.017[s]    _pusta petla while.php

dane z 50 pomiarow
av:    1.443[s]    sd:    0.068[s]    _pusta petla for.php
av:    0.772[s]    sd:    0.058[s]    _pusta petla while.php


I jeszcze, żeby było widać co mierzyłem.

  1. <?php
  2. for( $i = 0; $i < $n; ++$i ){
  3. }


  1. <?php
  2. $i = $n;
  3. while( $i-- ){
  4. }


W obu przypadkach $n = 1e7;

jeszcze dane dla 200 pomiarów:
Kod
av:    1.428 [s]    sd:    0.051 [s]    _pusta petla for.php
av:    0.727 [s]    sd:    0.030 [s]    _pusta petla while.php


Już praktycznie nie widać, zeby coś się poprawiło. While zdecydowanie wygrywa z for`em i to prawie dwukrotnie.
Pawel_W
Cytat(flashdev @ 4.11.2010, 21:59:40 ) *
Już praktycznie nie widać, zeby coś się poprawiło. While zdecydowanie wygrywa z for`em i to prawie dwukrotnie.

no więc właśnie smile.gif

dzięki za wykonanie pomiarów, jestem aktualnie na laptopie i nie mam tutaj zainstalowanego serwera smile.gif
rzymek01
ciekawe skąd bierze się taka różnica...

o ile pamiętam w C/C++ nie ma takich róznic w działaniu tych pętli
Pawel_W
Cytat(rzymek01 @ 4.11.2010, 23:46:43 ) *
ciekawe skąd bierze się taka różnica...

o ile pamiętam w C/C++ nie ma takich róznic w działaniu tych pętli

są, ale tylko przy kompilacji, kod wynikowy jest sprowadzany do takiej samej postaci smile.gif
flashdev
Cytat(Pawel_W @ 4.11.2010, 23:53:12 ) *
są, ale tylko przy kompilacji, kod wynikowy jest sprowadzany do takiej samej postaci smile.gif


Dokładnie do 2 instrukcji
porównanie + ewentualny skok
inkrementacja/dekrementacja

W pętli for jeszcze jest ustawienie początkowej wartości na początku, ale w while też trzeba to zrobić, tylko poza pętlą.
rzymek01
no własnie, pamietam, że jak sprawdzalem instrukcje asm to w przypadku for jak i while kompilator sprowadzal do tego samego smile.gif
ernie242
Jestem pod wrażeniem Panowie blinksmiley.gif Niektóre kody są naprawdę sprytne! (co do innych - jestem zbyt głupi, żeby je rozszyfrować...)

Ja niestety nie miałem czasu za bardzo do tego przysiąść, a szkoda...

http://pastebin.com/7hts0LHU

Kod oparty na klasach byłby chyba jeszcze wolniejszy, za to opakowanie wszystkiego w funkcje pozwoliło mi na (jako tako) napisanie prostych testów podczas pisania skryptu:

http://pastebin.com/zR1Pe4LH

pozdrawiam
phpion
No i zadek. Ja również odpadłem z rywalizacji. Po ostatnim prostokącie brakuje mi jednego znaku nowej linii. Cóż, trudno. Życzę Wam ostrej rywalizacji i jak najmniejszego wpływu przypadku na uzyskane wyniki.

Mój pechowy kod:
http://wklej.org/id/412353/
W moich testach 1000 wywołań zajmowało łącznie ok. 1,6 sekundy... ehhh...
dr_bonzo
@phpion:

Cytat
W moich testach 1000 wywołań zajmowało łącznie ok. 1,6 sekundy... ehhh...


A jak odpalales program?

- za kazdym razem exec()? "... program zostanie wykonany 1000 razy..." - problemem jest to ze czas odpalenia programu chyba przewyzsza znacznie czas wykonania obliczen - wiec neiznaczne roznice w algorytmach nie beda widoczne.
- czy w 1 skrypcie php odpaliles 1000razy funkcje do obliczen (nie tracisz czasu na odpalanie kodu)?
phpion
Testowałem to tak, że w kodzie na sztywno zapisałem zakodowany ciąg wejściowy (ten z PDFa). Następnie do kodu dodałem:
  1. $xdebug_time_index = xdebug_time_index();
  2. $xdebug_memory_usage = xdebug_memory_usage();
  3. $xdebug_peak_memory_usage = xdebug_peak_memory_usage();
  4.  
  5. $sql = mysql_pconnect('localhost', 'root', '');
  6. mysql_select_db('konkurs', $sql);
  7.  
  8. mysql_query('INSERT INTO xdebug (script, xdebug_memory_usage, xdebug_peak_memory_usage, xdebug_time_index) VALUES ("'.$_SERVER['REQUEST_URI'].'", '.$xdebug_memory_usage.', '.$xdebug_peak_memory_usage.', '.$xdebug_time_index.')');

dzięki czemu zapisywałem sobie uzyskane parametry do bazy danych. Później wyświetlałem je sobie odpowiednim widokiem, który obliczał sumaryczny czas wykonania, średni czas wykonania itp.

Skrypt wywoływałem poprzez:
Kod
ab -n1000 http://...


Szczerze mówiąc sądzę, że byłbym w zdecydowanej czołówce. Siedziałem nad tym praktycznie bite 2 tygodnie. Kombinowałem raz tak, raz srak (i w moich testach wyszło, że while jest faktycznie szybsze od for!) i w końcu spłodziłem to, co spłodziłem. Nawet głupie obliczanie długości wejścia zrobiłem while'm, gdyż było to szybsze niż strlen. No ale zapomniałem (źle doczytałem) końcowego entera sciana.gif

Aha, żeby umożliwić zapis danych do bazy musiałem zamienić die() na zwykłe echo, co też spowolniło działanie skryptu (sprawdzałem również bez zapisu do bazy).

// Edit:
Poniżej zebrane czasy zamieszczonych tu prac (uruchamiane w kolejności alfabetycznej z ok. 10 sekundowymi przestojami między kolejnymi uruchomieniami):
Kod
+---------------+-------------------+
| skrypt        | czas              |
+---------------+-------------------+
| phpion.php    |  1.63519223213194 |
| rolka.php     |  2.08828377723708 |
| sever88.php   |  2.11622476577766 |
| krowal.php    |  2.79060316085828 |
| l0ud.php      |  3.10421872138977 |
| dr_bonzo.php  |  3.55402493476858 |
| askone.php    |  3.72726726532000 |
| Daimos.php    |  3.82858920097367 |
| zegarek84.php |  4.41141557693496 |
| Pawel_W.php   |  5.93350315093991 |
| ernie242.php  |  7.32922220230119 |
| Demio.php     |  9.24934792518643 |
| jasin.php     | 21.57112717628520 |
+---------------+-------------------+
ernie242
2 tygle. Wow, no to naprawdę szkoda :/
dr_bonzo
@phpion - roznice w czasach sa ciekawe. Moze to "wina" php'a jako modul apacha i jakichs keszow.
phpion
Może, nie wiem. Ja opierałem się na tych wynikach testując kolejne wersje swojego rozwiązania. Faktycznie - szkoda tych 2 tygodni (coprawda jedynie pracując po godzinach w domu, ale jednak...) ale mogę być wściekły tylko na siebie. Ponoć przypadków jak mój było więcej i zostaną upublicznione czasy wykonania wszystkich nadesłanych prac. Oczywiście błędne rozwiązania nie będą wchodziły w grę w konkursie. Dlatego jedyne co teraz mi pozostaje to cicha nadzieja, że moje rozwiązanie w liście ogólnej nie znajdzie się na żadnym z trzech pierwszych miejsc smile.gif hehe.
ernie242
Być może podarują Tobie ten jeden LF smile.gif
dr_bonzo
A mi smieci w kodzie i kiepski czas.
phpion
Cytat(ernie242 @ 5.11.2010, 14:11:13 ) *
Być może podarują Tobie ten jeden LF smile.gif

Nie - już wyniuchałem tą sprawę. Jest to błąd w rozwiązaniu i tyle.

Teraz sobie pomyślałem o sztandarowym tekście: "Nie przyjechałem tu dla pieniędzy, przyjechałem się dobrze bawić, to tylko gra" smile.gif hehe.
rzymek01
@phpion nie ma co się poddawać, nawet na olimpiadzie informatycznej nie karzą za brak znaku nowej linii smile.gif

PS. faktycznie, juz poprawiłem tongue.gif
flashdev
Cytat(rzymek01 @ 5.11.2010, 16:10:05 ) *
@phpion nie ma co się poddawać, nawet na olimpiadzie informatycznej nie każą za brak znaku nowej linii smile.gif


Rzeczywiście dziwnie to zostało zorganizowane. Na takim spoj.pl dodatkowe entery nie odgrywają żadnej roli, ponieważ te linijki przez taką instrukcję jak scanf zostałyby odczytane w ten sam sposób, anwet jak by nie było enterów pomiędzy kolejnymi prostokątami.

karzą - karwinksmiley.jpg
dr_bonzo
No dobra, ale to byl chyba najjasniej i najprecyzyjniej opisany punk regulaminu smile.gif
Pawel_W
ja o tym dobrze wiedziałem i sam nie wiem, dlaczego nie dałem tej dodatkowej linii... może jakiś rozkojarzony byłem? smile.gif
ADeM
Mój amatorski kod: http://pastebin.com/ETZPV0Ug
phpion
Cytat(dr_bonzo @ 5.11.2010, 16:23:28 ) *
No dobra, ale to byl chyba najjasniej i najprecyzyjniej opisany punk regulaminu smile.gif

Może i było to dość jasno i wyraźnie napisane, ale ja (jak i ponoć całkiem sporo osócool.gif odczytaliśmy to nieco inaczej. Szczerze mówiąc miałem (mam?) nadzieję, że celem konkursu jest faktycznie napisanie skryptu, który w sposób najwydajniejszy wykona postawione zadanie (w zasadzie 2: odkodowanie ciągu i utworzenie prostokątów). Okazuje się jednak, że reguły są sztywne i tak naprawdę rozwiązanie schodzi na drugi plan, a jego miejsce zajmuje czytanie ze zrozumieniem. Moim skromnym zdaniem brakujący enter nie jest wyznacznikiem poprawności rozwiązania zadania. Rozumiem błędy w odkodowaniu ciągu, obliczania kolejnej wartości sekwencji, złe umieszczenie cyfr w prostokątach... no ale enter? To jakby na konkursie matematycznym podkreślić wynik końcowy, a nie napisać "Odp: Wynik to X".

Poza tym w poście informującym o konkursie DeyV napisał:
Cytat
Jeśli macie jakieś pytania lub sugestie -piszcie śmiało

Pytań było kilka i na żadne (ze związanych z postawionym zadaniem) nie uzyskaliśmy odpowiedzi. Jeśli więc z założenia miało to wyglądać "macie i główkujcie" to informacja o możliwości zadawania pytań była zbędna.

Może jestem rozgoryczony swoim przypadkiem i się czepiam, ale mogłoby to wyglądać nieco lepiej...
Pawel_W
Cytat(phpion @ 6.11.2010, 13:40:51 ) *
To jakby na konkursie matematycznym podkreślić wynik końcowy, a nie napisać "Odp: Wynik to X".

no to jest akurat złe porównanie, bo na większości konkursów (przynajmniej tak było w podstawówce i gimnazjum) trzeba było udzielić pełnej odpowiedzi słownej smile.gif

ale popieram smile.gif
phpion
No to może porównanie średnio trafne. Na konkursach/olimpiadach matematycznych bywałem w podstawówce, czyli jakiś czas temu winksmiley.jpg
itsme
pamiętajcie że jezeli chodzi o pierwsza nagrode tutaj decyzje podejmuje polcode natomiast jezeli chodzi 2 i 3 to mentax.

Zatem można wliczyć na zdrowo rozsądkowe podejście do Waszych prac.
NIe mniej należy wrócić uwagę na fakt że tutaj prezentuje swój kod okolo 10-15 osób zaś prac konkursowych wpłynęło znacznie więcej.

teraz pozostało się uzbroić w cierpliwość !
phpion
Cytat(itsme @ 6.11.2010, 14:23:55 ) *
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 winksmiley.jpg ale jednak sporo do głowy weszło.
flashdev
Cytat(phpion @ 6.11.2010, 14:52:50 ) *
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.

Cytat(phpion @ 6.11.2010, 14:52:50 ) *
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 winksmiley.jpg 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:
  1. <?php
  2. $str = str_repeat('x', 1e4);
  3. while( $n-- ){
  4. $len = strlen($str);
  5. }

  1. <?php
  2. $str = str_repeat('x', 1e4);
  3. while( $n-- ){
  4. $len = 0;
  5. while(isset($str{++$len}));
  6. }


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.
phpion
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 smile.gif 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 smile.gif
flashdev
Cytat(phpion @ 6.11.2010, 17:19:06 ) *
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 smile.gif 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 smile.gif


* blinksmiley.gif - mam nadzieję, że nie w manualu smile.gif

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.
phpion
Cytat(flashdev @ 6.11.2010, 17:29:16 ) *
* blinksmiley.gif - mam nadzieję, że nie w manualu smile.gif

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 smile.gif
ernie242
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:

Cytat(flashdev @ 6.11.2010, 17:05:17 ) *
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.
l0ud
@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.
rzymek01
możesz zamieścic wyniki smile.gif
chrix
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



  1. <?php
  2. function a() {
  3. global $argv;
  4. $invcode='9876543210ZYXWVUTSRQPONMLKJIHGFEDCBA9876543210ZYXWVUTSRQPONMLKJIHGFEDCBA';
  5. $p=-1;
  6. $i=$move=$l=strlen($argv[1]);
  7. $last=$prelast='0';
  8. do {
  9. $of=$move%36;
  10. $idx=ord($argv[1][++$p]);
  11. ($idx<65)?$v=$invcode[57-$idx+$of]:$v=$invcode[100-$idx+$of];
  12. $vv=ord($v)-48;
  13. if ($vv>-1&&$vv<10) {
  14. switch($last) {
  15. case'K':
  16. $k=$vv;
  17. break;
  18. case'W':
  19. $w=$vv;
  20. break;
  21. case'A':
  22. $a=$vv;
  23. break;
  24. case'Z':
  25. $z=$vv;
  26. break;
  27. case'1':
  28. if($prelast=='K')$k=10+$vv;
  29. elseif($prelast=='W')$w=10+$vv;
  30. break;
  31. case'2':
  32. if($prelast=='K')$k=20;
  33. elseif($prelast=='W')$w=20;
  34. break;
  35. }
  36. }
  37. $prelast=$last;
  38. $last=$v;
  39. $step=$move;
  40. $move+=$l;
  41. $l=$step;
  42. }while(--$i);
  43. $pt='0123456789';
  44. $bar='-------------------------------
  45. -*****************************-
  46. -*****************************-
  47. -*****************************-
  48. -*****************************-
  49. -*****************************-
  50. -*****************************-
  51. -*****************************-
  52. -*****************************-
  53. -*****************************-
  54. -*****************************-
  55. -*****************************-
  56. -*****************************-
  57. -*****************************-
  58. -*****************************-
  59. -*****************************-
  60. -*****************************-
  61. -*****************************-
  62. -*****************************-
  63. -*****************************-
  64. -*****************************-
  65. -*****************************-
  66. ';
  67. $ii=(int)$w*$k;
  68. $bar[$k+33]='-';
  69. $s=33;
  70. $t=($w<<5);
  71. $off=33;
  72. $off2=$t+1;
  73. $off3=$t+$k;
  74. $K=$k>>1;
  75. $s=$off2+32;
  76. do {
  77. $bar[++$s]='-';
  78. ++$s;
  79. }while(--$K);
  80. $bar[$off3+32]='-';
  81. $bar3=$bar2=$bar;
  82. $v=$a;
  83. $vec=1;
  84. $vec2=-32;
  85. do {
  86. $bar[$off]=$pt[$v];
  87. $bar2[$off2]=$pt[$v];
  88. $bar3[$off3--]=$pt[$v];
  89. if ($bar[$off+$vec]!='*')switch($vec) {
  90. case'1':$vec=32;
  91. break;
  92. case'32':$vec=-1;
  93. break;
  94. case'-1':$vec=-32;
  95. break;
  96. case'-32':$vec=1;
  97. }
  98. $off+=$vec;
  99. $off2+=$vec2;
  100. if ($bar2[$off2]!='*') {
  101. $vec2=-$vec2;
  102. $off2+=$vec2+1;
  103. }
  104. if($bar3[$off3]!='*')$off3-=32-$k;
  105. ($v==$z)?$v=$a:++$v;
  106. }while(--$ii);
  107. $eff3=$eff2=$eff='';
  108. $off=33;
  109. $W=$w;
  110. do {
  111. $K=$k;
  112. do {
  113. $eff.=$bar[$off];
  114. $eff2.=$bar2[$off];
  115. $eff3.=$bar3[$off++];
  116. }while(--$K);
  117. $eff.='
  118. ';
  119. $eff2.='
  120. ';
  121. $eff3.='
  122. ';
  123. $off+=32-$k;
  124. }while(--$W);
  125. echo $eff,'
  126. ',$eff2,'
  127. ',$eff3,'
  128. ';
  129. }
  130. a();
l0ud
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 smile.gif Inna sprawa, że aby to sprawdzić musiałem wywalić tą całą funkcję z globalem.
chrix
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
kaliberx
Jak dla mnie sposób pomiaru zaproponowany w regulaminie jest niezbyt dobry. Zakładając, że kod będzie w stylu:

  1. $prog = 'moj.php';
  2. $param = 'VTRNH7R1VZXZZ137DN3TZVXVVTTZ4CU1U40C2137DN3TZVXVVTRNH7R1VZXZZ137DN3TZV';
  3. for ($i=0; $i<1000; $i++) {
  4. popen("php -f $prog $param", "r");
  5. }


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.
dr_bonzo
@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.
ernie242
Cytat(kaliberx @ 9.11.2010, 18:13:55 ) *
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...
dr_bonzo
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"
DeyV
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 smile.gif
pauluZ
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ń smile.gif
Wklejam całość tutaj oraz przez link:

http://wklej.org/id/421468/

5. miejsce i kusi mnie strasznie chęć chwalenia się smile.gifsmile.gif - ajajaj smile.gif Pozdrawiam!!

Gratulacje!! dla zwycięzców oraz dla 4. miejsca --- także zamieść swój kod exclamation.gif
Jesteś lepszy ode mnie o 0.16 sekundy, hehehe

  1. <?php
  2. /**
  3.  * Polcode Code Contest PHP-2010.10
  4.  * Nick: pauluZ
  5.  */
  6. $t['A'] = 0; $t['B'] = 1; $t['C'] = 2; $t['D'] = 3; $t['E'] = 4; $t['F'] = 5; $t['G'] = 6; $t['H'] = 7; $t['I'] = 8; $t['J'] = 9;
  7. $t['K'] = 10; $t['L'] = 11; $t['M'] = 12; $t['N'] = 13; $t['O'] = 14; $t['P'] = 15; $t['Q'] = 16; $t['R'] = 17; $t['S'] = 18; $t['T'] = 19;
  8. $t['U'] = 20; $t['V'] = 21; $t['W'] = 22; $t['X'] = 23; $t['Y'] = 24; $t['Z'] = 25; $t['0'] = 26; $t['1'] = 27; $t['2'] = 28; $t['3'] = 29;
  9. $t['4'] = 30; $t['5'] = 31; $t['6'] = 32; $t['7'] = 33; $t['8'] = 34; $t['9'] = 35;
  10. $str = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789';
  11. $arg = $argv[1];
  12.  
  13. $lenght = strlen($arg);
  14.  
  15. $out = '';
  16. $fib[-2] = 0;
  17. $fib[-1] = $lenght;
  18. for ($i = 0; $i < $lenght; $i++) {
  19. $fib[$i] = $fib[$i-2] + $fib[$i-1];
  20. $j = ($t[$arg{$i}] - $fib[$i]) % 36;
  21. $out .= $str[(($j<0)?($j+36):$j)];
  22. }
  23. preg_match_all('([KWAZ][0-9][0-9]?)', $out, $matches);
  24. for ($i = 0; $i < 4; $i++) {
  25. ${$matches[0][$i]{0}} = substr($matches[0][$i], 1);
  26. }
  27. // ----------------------------------------------------
  28. // pierwszy prostokat - 1
  29. $p = $A;
  30. $sx = 1;
  31. $sy = 1;
  32. $kx = $K;
  33. $ky = $W;
  34. while (true) {
  35.  
  36. for ($x=$sx; $x<=$kx; $x++) {
  37. $result[$x][$sy] = $p;
  38. ($p==$Z) ? $p = $A : $p++;
  39. }
  40. $sy++;
  41. if ($sy > $ky) break;
  42.  
  43. for ($y=$sy; $y<=$ky; $y++) {
  44. $result[$kx][$y] = $p;
  45. ($p==$Z) ? $p = $A : $p++;
  46. }
  47. $kx--;
  48. if ($sx > $kx) break;
  49.  
  50. for ($x=$kx; $x>=$sx; $x--) {
  51. $result[$x][$ky] = $p;
  52. ($p==$Z) ? $p = $A : $p++;
  53. }
  54. $ky--;
  55. if ($sy > $ky) break;
  56.  
  57. for ($y=$ky; $y>=$sy; $y--) {
  58. $result[$sx][$y] = $p;
  59. ($p==$Z) ? $p = $A : $p++;
  60. }
  61. $sx++;
  62. if ($sx > $kx) break;
  63. }
  64.  
  65. for ($y=1; $y<=$W; $y++) {
  66. for ($x=1; $x<=$K; $x++) {
  67. echo $result[$x][$y];
  68. }
  69. echo "\n";
  70. }
  71. echo "\n";
  72. // ----------------------------------------------------
  73. // drugi prostokat - 2
  74. $p = $A;
  75. $x = 1;
  76. while ($x <= $K) {
  77. if ($x % 2 == 1) {
  78. for ($y=$W; $y>=1; $y--) {
  79. $result[$x][$y] = $p;
  80. ($p==$Z) ? $p = $A : $p++;
  81. }
  82. } else {
  83. for ($y=1; $y<=$W; $y++) {
  84. $result[$x][$y] = $p;
  85. ($p==$Z) ? $p = $A : $p++;
  86. }
  87. }
  88. $x++;
  89. }
  90.  
  91. for ($y=1; $y<=$W; $y++) {
  92. for ($x=1; $x<=$K; $x++) {
  93. echo $result[$x][$y];
  94. }
  95. echo "\n";
  96. }
  97. echo "\n";
  98. // ----------------------------------------------------
  99. // trzeci prostokat - 3
  100. $R = $K*$W;
  101. $groups = floor( $R / ($Z-$A+1) );
  102. $remain = $R - ($groups * ($Z-$A+1));
  103.  
  104. $sek_s = '';
  105. for ($i=$Z; $i>=$A; $i--) {
  106. $sek_s .= $i;
  107. }
  108. $sek = '';
  109. for ($i=1; $i<=$groups; $i++) {
  110. $sek .= $sek_s;
  111. }
  112. for ($i=$A; $i<=$A+$remain-1; $i++) {
  113. $sek = $i . $sek;
  114. }
  115.  
  116. echo chunk_split($sek, $K, "\n");
  117. echo "\n";
dr_bonzo
Masz calkiem sexi kod

Kod
$sek_s .= $i;
phpion
Cytat(dr_bonzo @ 18.11.2010, 18:05:45 ) *
Masz calkiem sexi kod

Kod
$sek_s .= $i;

Hehehe, dobre smile.gif

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 :/
Daimos
Cytat(phpion @ 18.11.2010, 19:39:16 ) *
Hehehe, dobre smile.gif

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? snitch.gif 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/
To jest wersja lo-fi głównej zawartości. Aby zobaczyć pełną wersję z większą zawartością, obrazkami i formatowaniem proszę kliknij tutaj.
Invision Power Board © 2001-2025 Invision Power Services, Inc.