02. 02. 2006. | #21 |
Python Ambassador
Master
|
Blues, u pitanju je 36^8 = 2.821.109.907.456 (rezultat si doduše pogodio ) i u pitanju su varijacije sa ponavljanjem a ne kombinacije.
Eh da, zaboravio sam da spomenem da gorespomenuto rešenje može imati monstruozno visoku brzinu konvergencije ako se pravilno izaberu multiplikator i faktor_ubrzanja.
__________________
Python Ambassador of Serbia Poslednja izmena od Petar Marić : 02. 02. 2006. u 02:17. |
02. 02. 2006. | #22 |
Goran Pilipović
Sir Write-a-Lot
|
Samo sam pogresno napisao, na isto sam mislio
BTW, evo nekih RAZOCARAVAJUCIH rezultata. Koristio sam funkciju array_rand (), prvi parametar je array: PHP kôd:
Iako sam seed-ovao (navodno posle PHP 4.2. ne mora ni to) već posle 1000 kodova počeo sam da dobijam enormno mnogo duplikata, koji su se ponavljali čak i desetak puta. Iako sam stavio set_limit_time (180); skript je pucao, a uspeo je da ubaci samo 26 000 kodova. Zatim sam ponovo pokrenuo script, još gore. Ubacio je za 180 sekundi samo 4 000 novih kodova. Šta to znači? PHP random funkcije su žešće sranje? kod je izgledao ovako: PHP kôd:
A onda sam pomislio da nije u pitanju neki cache ili nešto, pošto je broj novih kodova pri svakoj novoj egzekicuji scriptova bio sve manji. Dodao sam shuffle($a); u ovom delu: PHP kôd:
I tada je prodadilo kako treba. Prosečno je generisao po 300 k kodova za oko 100 sekundi. Predlog sa držanjem u memoriji bi očigledno propao, ništa ne bi upisao pre završetka scripta.
__________________
Goran Pilipović a.k.a. Ugly Fingers Bradley f.k.a. bluesman I don't always know what I'm talking about but I know I'm right! |
02. 02. 2006. | #23 |
Python Ambassador
Master
|
Slažem se da su PHP-ove random() funkcije sranje jer IIRC koriste ANSI C rand() koja ima period od 2^31.
Ako želiš ekstremno dug period probaj Mersenne Twister algoritam, baš smo ga spominjali iz numerike na predavanjima - poznat je po tome što ima monstruozan period od 2^19937-1 u svojoj osnovnoj verziji. edit: Nakon malo kopanja po dokumentaciji uvideo sam da ipak u PHP-u postoji implementiran Mersenne Twister algoritam, samo umesto rand() koristi mt_rand(). Mada još uvek smatram da će se brže izračunati i da će se dobiti kvalitetniji rezultati u specijalizovanom softveru za numeričke proračune tipa MATLAB.
__________________
Python Ambassador of Serbia Poslednja izmena od Petar Marić : 02. 02. 2006. u 03:23. |
02. 02. 2006. | #24 |
Igor Marinović
Expert
|
Jeste da koristim MySQL za sve i svašta, ali kod ovog zadatka ja sam ipak za memoriju. Za kontrolni array bih koristio hash array, mnogo je brži nego obični. Ali, (naravno postoji ali) hash array koristi mnogo memorije ... Jeste, za 2 miliona objekata za ovaj zadatak troši se nešto manje od 300Mb. Ali zato je vreme izvršavanja na kućnoj mašini 45 sekundi sa sve debugom!
Evo koda: PHP kôd:
izvrseno za 45 s, provereno 2000490 kodova Mogla bi se uštedeti koja sekunda bez ispisivanja kontrolnih podataka, i uklanjanja rand(..) funkcije. rand funkcija je tamo za one koji ne veruju da je substring od petog mesta za microtime dovoljno slučajan. Čak i kod ovako jednostavnih zadataka ne prolazimo jeftino. Nešto uvek trpi, da li memorija, da li procesor, ili vreme. Ovde je to bila memorija, ali uslovno rečeno, jer se danas 300Mb baš i ne smatra zauzećem memorije, naročito ako ono traje manje od minut. Koliko bi ovo trajalo sa MySQL? Myth Busted. Poslednja izmena od nixa : 02. 02. 2006. u 12:39. |
02. 02. 2006. | #25 |
Igor Marinović
Expert
|
Hm, setio sam se još nešto (čovek ima dovoljno vremena za razmišljanje dok se brije).
U bluesmanovom programčetu će svi karakteri biti različiti, a nisam siguran da se to traži. Kada se kaže slučajno odabran niz, obično se misli na varijacije sa ponavljanjem, ne bez ponavljanja. Zato je md5 funkcija za bilo koje pseudonizove majka. |
02. 02. 2006. | #26 |
Dejan Katašić
Wrote a book
Datum učlanjenja: 10.06.2005
Lokacija: Novi Sad
Poruke: 1.017
Hvala: 129
86 "Hvala" u 43 poruka
|
Da, in_array je problematican ... izgleda da trci kroz niz i proverava redom vrednosti, blah, a kad niz naraste i to ispitivanje uleti u petlju ... hehe, dzaba.
Igorovo resenje radi lepo, guta taman toliko memorije ... evo malih kozmetickih izmena PHP kôd:
|
02. 02. 2006. | #27 |
Knowledge base
Wrote a book
Datum učlanjenja: 16.06.2005
Lokacija: Novi Sad
Poruke: 1.437
Hvala: 37
131 "Hvala" u 82 poruka
|
Igore, cestitam na resenju, to je ono sto je trebalo da napisem
__________________
Năo quero mais seguir um só caminho |
02. 02. 2006. | #28 |
Goran Pilipović
Sir Write-a-Lot
|
Moram da kažem da sam probao Igorovo rešenje jer mi se učinlo elegantno ali desilo se sledeće:
- Script je krenuo veliko brzinom da generiše kodove, ali kako se povećavao broj generisanih kodova tako je usporenje bilo sve veće da bi na kraju potpuno prestalo. - Pri izvršenju scripta mi se totalno "zamrzao" računar, iako ima 1GB RAM, odrmzao se tek nakon 15-ak minuta. To što se generišu samo hex vrednosti nije toliko problem. veći je problem ono što sam i pretpostavljao da je zauzimanje memorije toliko veliko da dovede do smrzavanja računara. Da ne bude zabune, nije ovde reč o "ovaj je bolji", ja sam odradio posao i poslao tih 2 miliona kodova, međutim možda nebi bilo loše, kada smo započeli da nađemo neko dobro rešenje. Onaj moj radi, doduše sporije, ali je sve bilo bez greške. Ono što mene još zbunjuje je što je i md5(microtime()...) generisao nekoliko desetina hiljada duplikata. [edit]na kraju sam ipak morao da restartujem masinu.[/edit]
__________________
Goran Pilipović a.k.a. Ugly Fingers Bradley f.k.a. bluesman I don't always know what I'm talking about but I know I'm right! Poslednja izmena od bluesman : 02. 02. 2006. u 15:21. |
02. 02. 2006. | #29 | |
Dejan Katašić
Wrote a book
Datum učlanjenja: 10.06.2005
Lokacija: Novi Sad
Poruke: 1.017
Hvala: 129
86 "Hvala" u 43 poruka
|
Citat:
|
|
02. 02. 2006. | #30 | |
Igor Marinović
Expert
|
Citat:
Probao sam na vise racunara, cisto da uporedim brzinu, brzina je bila srazmerna brzini procesora. Proveo sam nKov bluesman.txt, izgenerisani kodovi su stvarno bili razliciti. Nije md5(microtime()...) generisao nekoliko desetina hiljada duplikat, nego substring od njega. Mnogo je veca verovatnoca da ces naleteti na isti substring od 8 karaktera nego od 32 karaktera |
|
|
|
Slične teme | ||||
Tema | Početna poruka teme | Forum | Odgovori | Poslednja poruka |
random + mysql | mega023 | PHP | 9 | 09. 03. 2010. 16:08 |
random select na velikoj tabeli | kodi | SQL baze podataka - Sponzor: Baze-Podataka.net | 14 | 09. 04. 2008. 12:46 |
random koji favorizuje | kodi | Programiranje | 16 | 29. 04. 2007. 21:09 |
java.util.Random security | Ivan | Programiranje | 0 | 02. 01. 2007. 18:43 |
Random image - preraditi za flash... | headcutter | (X)HTML, JavaScript, DHTML, XML, CSS | 4 | 02. 09. 2005. 22:14 |