[es] - Zagonetni problem oko nizova

iizuzetan

Član broj: 186478
Poruke: 375
*.adsl.verat.net.

+16 Profil

^{23.03.2009. u 21:27 - pre 183 meseci}

Citat:

Nemanja Avramović: Evo i mog rešenja, bez ikakvih petlji (sa sve benchmarkingom):

Code:

.
.
.
.
.
Vreme izvrsenja skripte: 0.00017118453979492 sec

Mada mislim da bi trebalo da testiramo skriptu sa bar par stotina elemenata u nizu ;)

Moja skripta (usavrsena "Nikola Poša" dodatkom) se izvrsava u vremenu od 0.00010895729064941 sec a koristio sam potpuno iste funkcije za merenje vremena kao ti (iskopirao). E sad racunari nam nisu isti (tvoj je brzi), pa sam prekopirao ceo tvoj kod i izmerio vreme tvoje skripte i iznosi : 0.0001990795135498 sec

Znaci tvoje vreme na mom racunaru je 0.0001990795135498 sec a moje vreme na mom racunaru je 0.00010895729064941 sec.

Zakljucak: Moja skripta dolazi brze do resenja, i to cak brze za 45% !!!!!!!!!!!!
Drugim recima ako bi na indeksu bio veliki broj a tvoja skripta se izvrsi na primer za 10 sekundi moja bi se izvrsila za 5.5 sekundi. Malo li je?

E sad razlog je najverovatnije taj sto koristis dvodimenzionalni niz. Znaci jeste da je ugradjena funkcija brza od napisane skripte ali to ustedjeno vreme ti pojede dvodimenzionalan niz.

Napisao si da nemas ni jednu petlju. Jeste nemas vizuelno na prvi pogled ali nemoj da zaboravis da funkcija uasort() u sebi sadrzi potrebne petlje jer kako bi inace prosla kroz podatke i uporedila ih.

Odgovor na temu

kazil
Robert Bašić
Full time PHP dev :)
Bačka Topola - Novi Sad

Član broj: 120044
Poruke: 686
*.dynamic.stcable.net.

Jabber: robertbasic@elitesecurity.org
ICQ: 446475288
Sajt: robertbasic.com

+2 Profil

Re: Zagonetni problem oko nizova

^{23.03.2009. u 21:39 - pre 183 meseci}

Benchmarking nizova se radi sa po nekoliko miliona elemenata, merenja se vrse vise puta i na kraju je merodavno srednje vreme.

Odgovor na temu

Nikola Poša
Backend (PHP) developer
Beograd

Član broj: 173839
Poruke: 1616
*.adsl-4.sezampro.yu.

+33 Profil

Re: Zagonetni problem oko nizova

^{23.03.2009. u 22:07 - pre 183 meseci}

@iizuzetan

Ok, super, i drago mi je što je taj moja mala izmena presudila što se tiče brzine :), ali u realnim projektima ćeš se verovatno pre susretati sa dvodimenzionalnim nizovima, i bolje je ići sa dvodimenzionalnim nego sa više jednodimenzionalnih. I takvi problemi se onda rešavaju upotrebom nekih od gotovih f-ja za rad sa nizovima. Jer npr. zašto bi ti sad pisao ceo taj algoritam za sortiranje, kad možeš da napišeš samo npr. sort($niz). Siguran sam da većina tih ugrađenih f-ja za sortiranje koristi neke od onih algoritama koje sam napisao na prethodnoj strani. Njih nisam izmislio ja, oni su provereni i poznati algoritimi, i već dugo se koriste u programiranju.

I što kaže Robert, za pravo testiranje, potrebno je mnogo više elemenata u nizu...

Odgovor na temu

Aleksandar Ružičić
Software Architect, Appricot d.o.o.
Beograd

Član broj: 26939
Poruke: 2881

Jabber: krckoorascic@gmail.com
Sajt: krcko.net

+44 Profil

Re: Zagonetni problem oko nizova

^{23.03.2009. u 22:19 - pre 183 meseci}

nisi naveo onaj koji vecina (ne mogu da tvrdim za sve, jer nisam gledao kod svih fja ali je verovatno da ga sve koriste) ugradjenih sort funkcija, a to je qsort (iliti quick-sort), on je malcice komplikovaniji od ovih koje si ti naveo ali je u najvecem broju slucajeva najbrzi.

@iizuzetan: ako stvarno hoces da vidis koji kod je brzi moras da testiras bar 3 puta sa nizovima od 1000 elemenata najmanje da bi dobio konkretne rezultate. kao sto je kazil i rekao.

rafforum.rs - Forum Računarskog Fakulteta

Odgovor na temu

Tudfa
Jovicevic Vladimir

Član broj: 152699
Poruke: 384
*.dynamic.sbb.rs.

+3 Profil

Re: Zagonetni problem oko nizova

^{23.03.2009. u 23:16 - pre 183 meseci}

Evo ga jedan test sa vise elemenata ,mislim da je sve ok, barem sve radi ok sto se Nemanjinog predloga tice.

uasort sa 2000 elemenata:

Code:

<?php
function sortiraj($a, $b) {
 if ($a['ocena'] === $b['ocena']) {
 return 0;
 }
 return ($a['ocena'] > $b['ocena']) ? -1 : 1;
}

//stvaranje velikog niza
$niz = array();
$n = 2000;
for($i = 1; $i<= $n;$i++)
{
 $niz[$i]['ime'] = 'ime'.$i;//ime + redni broj...
 $niz[$i]['ocena'] = ($i% 2 == 0 ? 5 : 10);
 //ako je redni broj paran ocena = 5 ako je neparan ocena = 10
 //ovo sam cisto radio ovako zbog sebe, da proverim da li se sa oba metoda dobijaju isti rezulati sto se tice sorta, tako da tu moze slobodno i rand(5,10)
}

// benchmarking deo
$mtime = microtime();
$mtime = explode(" ",$mtime);
$mtime = $mtime[1] + $mtime[0];
$starttime = $mtime;

uasort($niz, 'sortiraj');

// bench. deo, prikaz vremena izvršenja skripte
 $mtime = microtime();
 $mtime = explode(" ",$mtime);
 $mtime = $mtime[1] + $mtime[0];
 $endtime = $mtime;
 $totaltime = ($endtime - $starttime);
 echo "Vreme izvrsenja skripte: ".$totaltime." sec";

?>

Vreme izvrsenja skripte: 0.018789052963257 sec

resenje bez uasort:

Code:

<?php

//stvaranje velikog niza
$ime = array();
$ocena = array();
$n = 2000;
for($i = 1; $i<= $n;$i++)
{
 $ime[$i] = 'ime'.$i;
 $ocena[$i] = ($i% 2 == 0 ? 5 : 10);
}

// benchmarking deo
$mtime = microtime();
$mtime = explode(" ",$mtime);
$mtime = $mtime[1] + $mtime[0];
$starttime = $mtime;

//KLUCNA SKRIPTA KOJA SORTIRA NIZ $ime U ZAVISNOSTI OD VREDNOSTI NIZA $ocena:

for($a=1;$a<=$n; $a++){
 for($b=1;$b<=$n; $b++){
 if($ocena[$b]<$ocena[$a]) {
 $u=$ocena[$a];$t=$ime[$a];
 $ocena[$a]=$ocena[$b];$ime[$a]=$ime[$b];
 $ocena[$b]=$u;$ime[$b]=$t;
 }
 }
}
/*
for($a=1;$a<=$n; $a++){
 echo '$ime['.$a.']->'.$ime[$a].' ';
}
*/

// bench. deo, prikaz vremena izvršenja skripte
 $mtime = microtime();
 $mtime = explode(" ",$mtime);
 $mtime = $mtime[1] + $mtime[0];
 $endtime = $mtime;
 $totaltime = ($endtime - $starttime);
 echo "Vreme izvrsenja skripte: ".$totaltime." sec";
?>

Vreme izvrsenja skripte: 0.95595598220825 sec

E sad bi voleo da vi pregledate ovaj test, a narocito iizuzetan, jer ili sam ja nesto izostavio/zaboravi/prevideo ili je uasort pojeo ovo drugo resenje za dorucak.

_{[Ovu poruku je menjao Tudfa dana 24.03.2009. u 10:49 GMT+1]}

Odgovor na temu

rajkoBekrija

Član broj: 123164
Poruke: 53
*.broadband.blic.net.

Profil

Re: Zagonetni problem oko nizova

^{24.03.2009. u 09:49 - pre 183 meseci}

Citat:

javljaju vrlo slozena medjuresenja pa i u vidu jednodimenzionalnih nizova

Sta rece i osta ziv

Odgovor na temu

rajkoBekrija

Član broj: 123164
Poruke: 53
*.broadband.blic.net.

Profil

Re: Zagonetni problem oko nizova

^{24.03.2009. u 10:37 - pre 183 meseci}

Samo da napomenem iz svog licnog iskustva, vec ako ti je toliko bitno, @iizuzetan, da dobijes brzi sort iz mase podataka mislim da neces nikako koristiti svoj algoritam (cini mi se skolski Bubble sort) .
Odnosno najbitnije nam je da na kraju mozemo dobiti sortirana imena nevezano za medjurezultate.

npr. n= 10k redova

tvoj algoritam

Code:
for($a=0;$a<$n; $a++){
 for($b=0;$b<$n; $b++){
 if($ocena[$b]<$ocena[$a]) {
 $u=$ocena[$a];
 $ocena[$a]=$ocena[$b];
 $ocena[$b]=$u;
 }
 }
}

daje rezultat za 18.823191 sec,

Code:
arsort( $ocena );

daje rezultat za 0.003704 sec

----

za n=1M redova

tvoj algoritam daje rezultat za >2dana,

arsort algoritam daje rezultat za0.764639 sec,

Odgovor na temu

dakipro
Dalibor Jovic
Web Developer
Bergen, Norway

Moderator
Član broj: 31848
Poruke: 1792
91.148.79.*

Sajt: norway.dakipro.com

+190 Profil

Re: Zagonetni problem oko nizova

^{24.03.2009. u 10:47 - pre 183 meseci}

Ma najveca je fora sto niko nikad nece dovesti sebe u tu situaciju da tako sortira tolike nizove, nego uzmes lepo obradis, ubacis u bazu sta ti treba i kako je najlakse, i posle izvadis iz baze sa SORT BY zar par trenutaka, ionako je potrebna i paginacija uglavnom

Nego je dobro da teoretisemo malo, mada kad razmislim, meni je ovako nesto zatrebalo za ZIP locator, da se pretraze useri recimo koji su u krugu od 100milja od neke zip adrese, i da se sortiraju po daljini od pocetnog mesta pretrage, tu se mora raditi tako sa nizovima, naravno, lepo oblikovan multidimenzionalni niz sa dobrim pravim kljucevima i uz generic funkciju se ne oseti u radu...

http://norway.dakipro.com/

Odgovor na temu