Generisanje random UNIQUE kodova
Script treba da generiše 2 miliona kodova. Svi moraju biti unique, svi imaju dužinu od 8 karaktera, koriste se samo mala slova i cifre, ne smeju da budu u bilo kakvom redosledu. Znači, primer jednog koda je: a39sdk2b
Sve to može da se generiše u lokalu, ne mora ništa real time, sada razmišljam kako da uradim to najbrže. Sam PHP kod nije problem, jedini mi je mali "problem" kako da budem siguran da nema duplikata. Moja ideja je da napravim jednu mysql tabelu koja će imati samo jednu kolonu koja je definisana kao primary key. Na primer ovako: PHP kôd:
Da li neko može da se seti nekog bržeg ili jednostavnijeg rešenja? Ne mora čak da bude ni PHP, može i iz Windows Paint ako treba :) |
Uvek moze brze :)
Napravi petlju koja generise te kodove, ali rezultate smesti u memoriju, u niz.. Pa tek onda sruci sav array u bazu |
I ako ima duplikata moram da prebrojim koliko je stvarno upisano, pa onda da generisem ponovo ostatak i tako dok ne popunim svih 2 miliona? Imao sam ideju da to uradim jednim izvrsenjem scripta :)
|
http://www.php.net/in_array
jedan niz, jedna petlja, jedan random generator, jedan brojač koji se povećava kad nova vrednost već nije u nizu samo isključi time limit, nemam predstavu koliko to može da traje // eh, da - koji jezik je u pitanju? |
Citat:
|
Najbrže? Najbolje?
1. Pa, za početak ključ od 8 karaktera je u stvari heksadecimalan prikaz 32-bitnog neoznačenog broja. 2. Tako kodiran ključ ima šansu pogotka od 1:2147,483648. 3. Za generisanje samih 32-bitnih brojeva iskoristi specijalizovani softver za numeričke proračune tipa MATLAB. Mislim da se u MATLAB-u da jednostavno napisati funkcija (tj, ako već ne postoji) za generisanje vektora jedinstvenih pseudo-slučajnih brojeva Paranoik si i ne veruješ pseudo-slučajnim brojevima? Poveži mikrofon na ulaz zvučne kartice, meri beli šum i koristi njegovu numeričku reprezentaciju kao slučajni broj. Takođe povećaj širinu broja na 64 bita i uradi konverziju bajt u karakter koda po svom ukusu. A onda, možda ipak ja samo previše teoretišem pred ispit iz Numerike :D |
Da, napravis petlju koja generise unique i proverava da li vec postoji u nizu, ako NE postoji, povecas counter...
Nesto kao do { $broj=generisi_broj(); if (!in_array($broj, $niz)) { $counter++; $niz[] = $broj;} } while ($counter<2000000); Ovo je odoka.. Valjda radi.. |
Preterujete. Rešenje koje je bluesman predložio je jednostavno, da se brzo napraviti i odradiće posao dok si rekao piksla.
1 x PK ili UNIQUE kolona 1 x brojač 1 x while loop 1 x generator koda Zbućkati, izvršiti i to je to. Pre ili kasnije ćeš morati podatke insertovati tako da baratanje nizom vidim kao suvišan korak. Nije neka ušteda, a pošto se radi samo jednom stvarno ne vidim zašto bismo pravili toliku nauku. Edit: moja greška. Pomislio sam da su podaci potrebni u bazi, ne u drugom (bilo kom) obliku. |
Petre, idi odspavaj malo :)
Ja ipak ne bih da smeštam 2 miliona kodova u memoriju pa onda da čuvam u file, to će potrajati i ako pukne, moram ponovo... nesigurno je. |
Citat:
|
Pa ja preferiram memoriju, manje ce drljati disk :)
|
Citat:
|
Citat:
|
Uvek moze da koristi memory tabelu tj:
engine = memory :) |
Kad bi vi ovako teoretisali i o mom geotargeted postu, cccc
http://www.devprotalk.com/showthread.php?t=587 |
Default memory limit je 8M. Za niz treba 2 miliona po 8 bajtova, dakle oko 16 mega. Ostatak koda ne troši memoriju, tako da bi trebalo da ti...
PHP kôd:
// ali mu zato treba kila vremena ... stavio sam da se vrti za 200 000 i nikako da završi skriptu |
Kad bolje razmislim, ova moja verzija ima jednu manu, za svaki generisani broj se proverava ceo niz.. sto znacajno usporava..
Dok bi mysql verzija bila u prednosti, jer kad lupis insert, odmah znas jel insertovao ili nije (ako vec postoji u bazi), pa ce skript raditi brze Tako da.. bolje mySQL :) (idem da se pokrijem ushima) |
Sad sam upravo generisao vektor od 2.000.000 celih pseudo-slučajnih brojeva sa opsegom [0..2^32-1] pomoću ove linije koda u MATLAB-u:
Kôd:
brojevi = randint(1, 2e6, 2^32); Nešto sam malo kopao po MATLAB-ovom helpu ali nisam uspeo da nađem funkciju koja uklanja istovetne vrednosti iz vektora, tako da mogu da dam sledeći algoritam (mrzelo me da pišem kod) koji može biti prilično brži od vaših IMHO: 1. Pokrenemo MATLAB i u definišemo sledeće promenljive: broj_kodova (broj jedinstvenih kodova koje želimo da generišemo), multiplikator (generišemo s njim "rezervne kodove", uzmimo da je vrednost 2) i faktor_ubrzanja (ubrzava dolazak do rešenja tako što poništava efekat nejedinstvenih kodova - uzmimo za vrednost 2) 2. Izvršimo Kôd:
podaci = sprintf('%x\n', randint(1, broj_kodova*multiplikator, 2^32)); 3. Izvršimo sledeći kod: Kôd:
brojac = 1; 5. Uradimo bulk insert podaci(brojac:delta+brojac-1, :) kodova u bazu (MATLAB podržava da se bulk insert izvrši jednim pozivom insert() funkcije) 6. Učitamo novu vrednost promenljive broj_jedinstvenih_kodova 7. Kôd:
brojac = delta+brojac; 9. Iz view-a povadimo broj_kodova redova i to smestimo u neku tabelu/dump/neki-drugi-izvor-podataka. 10. Pokrenemo, protegnemo se, popijemo kaficu i gotovo ;) I have way too much free time on my hands :D |
Citat:
MySQL tabela: Kôd:
create table kodovi ( kod char(8) not null, primary key (kod)) engine = memory; |
nego, da li neko moze da me podseti kako se tu racuna broj kombinacija. Znaci string od 8 karaktera, potencijalne vrednosti a...z i 0...9 (nema velikih slova) = 36 karaktera.
Da li je 8^36 ? 2.821.109.907.456 ? Sve sam zaboravio, a nekada sam imao poseban predmet matematicka verovatnoca :( Doduse, to je bilo pre 18 godina... (bolje da sam ćutao za godine) |
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. |
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. |
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. |
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. |
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. :) |
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:
|
Igore, cestitam na resenju, to je ono sto je trebalo da napisem :)
|
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] |
Citat:
|
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 :) |
Gledao sam još malo ovaj problem. Interesantan je što je postavka jednostavna, i ne trebaju nikakvi dodatni podaci da bi se počeo rešavati.
Slažem se sa bluesmanom da je najvažnije da program radi, pristalica sam pragmatičkog rešavanja problema. Problem je bio naći funkciju koja dobro "meša" karaktere, drugi problem je brzina, treći memorija. Recimo da mt_rand ili md5 dobro odabiru random karaktere. Brzina je bila ok, ali je 300Mb bilo suviše. Probao sam par varijanti: ideja je izgenerisati više kodova nego što treba, pa izbaciti duplikate. array_unique funkcija se čini idealna za to, ali troši 300Mb memorije. Nema veze, tu je array_sort, lakše je izbaciti duplikate iz sortiranog niza, džaba. Opet troši suviše memorije. Sledeća ideja mi se činila zgodnom: držati niz stalno sortiran, i proveravati pomoću binarnog pretraživanja da li je novogenerisani elemenat već u nizu. Ukoliko jeste, zaboraviti ga. Ukoliko nije, ubaciti ga na pravo mesto. array_splice mi se činila prava komanda za to, ništa premeštanje čitavih segmenata niza, samo treba da se ubaci elemenat i to je to. Na žalost, array_splice se itekako usporava kako niz raste, pa je i to bilo neupotrebljivo. Perl se ponašao bolje sa spliceom, ali opet nedovoljno brzo. OK, tu je memorija bila pod kontrolom, sve je bilo u jednom nizu. Binarni search je, po očekivanju, bio munjevit. Ja za ovakve zadatke obično koristim Perl, nekako mi je zgodnija komandna linija, a ima i dosta little-devil alata u shellu. Recimo ovakav program izgeneriše više od 2 miliona (ne unique!) kodova za manje od 30 sekundi: Kôd:
#!/usr/bin/perl Sve u svemu, nisam siguran koliko je PHP dobar za baratanje velikim strukturama, ima, čini se, tu mesta za optimizaciju. Svejedno, array_unique i array_splice su korisne komande, možda zatrebaju. |
Uz malu modifikaciju (0.5 umesto 2 miliona iteracija, ali se md5 hash sece na 4 dela - iako bi moglo na jos vise delova - pa se u jednoj iteraciji dobiju 4 key-a umesto jednog) skripta radi nesto brze. Ukupno zauzece memorije je manje od 30mb (negde oko 25-27) za perl i sort zajedno. Propustanjem unique key-eva kroz "wc -l" dobije se da je broj duplikata uvek manji od 0.025%, sto je verovatno zadovoljavajuce, uz vreme izvrsavanja manje od 15 sekundi (sa sve sortiranjem).
Ja sam uvek pre za Perl kada je iole veca kolicina podataka u pitanju - posebno ako treba nesto da se parsuje :) Eve ga i kod ako nekog zanima.. Kôd:
use Digest::MD5 qw/md5_hex/; Kôd:
$ time perl rand.pl | sort -u | wc -l |
OK, na kraju sam i ja napravio rešenje - doduše u MATLAB-u.
generate_unique_codes.m: Kôd:
function false_hit_chance = generate_unique_codes(number_of_codes, percent_of_extra_codes, out_file) Kôd:
out_file = 'out.txt'; Kôd:
>> test Šta na kraju da kažem do: The speed of my code sparkels your mind :D |
Zextrino iskoristavanje citavog md5 je pametno, gotovi se rezultati u fileu dobivaju za oko 15 sekundi.
Maricevo resenje stvarno radi munjevito, kod mene zavrsi posao za 3.8s (!), svaka cast. Matlab stvarno lepo mesa brojeve, i unique funkcija mu je munjevita. Probao sam slicno u Perlu, Matlab kod je u sustini ovo: Kôd:
for ($i = 0; $i<2002000; $i++) { Right tool for the right job :) |
Off Topic: Jbg ako bi to Perl odradio brze od MATLAB-a, mislim da bi s razlogom mogli da se zapitamo cemu zapravo MATLAB sluzi.. :D Svaka cast na resenju Petre :) |
Moze i Perl (+ bash) za manje od 10 sec:
Kôd:
use Digest::MD5 qw/md5_hex/; Kôd:
$ time perl rnd.pl > /dev/null |
Jeste bolje $m . $ms nego $m / $ms, jer konkatenacija oduzima manje procesora nego deljenje ... Medjutim, ovako rezultati opasno lice, ja bas jedan md5() ne bih koristio 25 puta ...
|
Hvala svima na pohvalama :D
Samo da napomenem jednu bitnu stvar - onih 0.025% koje Zextra pominje nastaju ako se percent_of_extra_codes postavi na 0 - zato i postoji taj parametar. Sad kad malo razmislim, mislim da sam bio prilično velikodušan što sam postavio percent_of_extra_codes na 0.1% - skript radi i sa 0.026%. što je savršeno logično. U stvari, potrebno je da percent_of_extra_codes bude samo neznatno veći od procenta očekivanog broja duplih kodova. |
Citat:
Ovako si odsekao 53.43% mogućih kodova što je najverovatnije razlog zbog kojeg dobijaš dva puta više duplikata. |
Omg sa cime se mi zavitlavamo... :)
@zigor: Slazem se da su dosta slicni kodovi, ali nakon mesanja istih, verovatnoca je nesto veca od 1:80.000 da iz te gomile izvuces dva koda koja su slicna... Doduse, ako se Marfi pita, verovatnoca je tek nesto veca od 1:5 ili tako nekako :D @Petar: dobro zapazanje :) |
Vreme je GMT +2. Trenutno vreme je 13:35. |
Powered by vBulletin® Verzija 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Copyright © DevProTalk. All Rights Reserved.