Zagonetni problem oko nizova

Re: Zagonetni problem oko nizova 23.03.2009. u 22:27 · pre 214 meseci #21

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.

Re: Zagonetni problem oko nizova 23.03.2009. u 22:39 · pre 214 meseci #22

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

Re: Zagonetni problem oko nizova 23.03.2009. u 23:07 · pre 214 meseci #23

@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...

Re: Zagonetni problem oko nizova 23.03.2009. u 23:19 · pre 214 meseci #24

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.

Potpis

rafforum.rs - Forum Računarskog Fakulteta

Re: Zagonetni problem oko nizova 24.03.2009. u 00:16 · pre 214 meseci #25

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.

Re: Zagonetni problem oko nizova 24.03.2009. u 10:49 · pre 214 meseci #26

Citat:

javljaju vrlo slozena medjuresenja pa i u vidu jednodimenzionalnih nizova

Sta rece i osta ziv

Re: Zagonetni problem oko nizova 24.03.2009. u 11:37 · pre 214 meseci #27

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,

Re: Zagonetni problem oko nizova 24.03.2009. u 11:47 · pre 214 meseci #28

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...

Potpis

http://norway.dakipro.com/

Re: Zagonetni problem oko nizova 24.03.2009. u 12:02 · pre 214 meseci #29

@dakipro

Sve zavisi na kakvom projektu radis, recimo projekat na 10 servera i svaki dan se parsiraju logovi koji budu teski i po 4GB na svakom serveru.

Znaci ima mnosto reporta koji se trebaju izvuci sa samo jednim prolazom kroz sve logove.

Forum kao aplikacija na telefonu

Srodne teme