03. 02. 2006. | #31 |
Igor Marinović
Expert
|
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 use MD5; use Time::HiRes qw(gettimeofday); while ($i++ < 2001000) { ($s,$ms) = gettimeofday; print substr(MD5->hexhash(utime().$s.$ms),5,8)."\n"; } 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. |
04. 02. 2006. | #32 |
Boris
Grand Master
Datum učlanjenja: 01.12.2005
Lokacija: Novi Sad
Poruke: 775
Hvala: 5
156 "Hvala" u 2 poruka
|
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/; use Time::HiRes qw/gettimeofday/; my $i = 0; while( $i++ < 500_000 ) { my ( $m, $ms ) = gettimeofday; my $code = md5_hex( $m / rand( $ms ) ); printf( "%s\n"x4, substr( $code, 0, 8 ), substr( $code, 8, 8 ), substr( $code, 16, 8 ), substr( $code, 24, 8 ) ); } Kôd:
$ time perl rand.pl | sort -u | wc -l 1999556 real 0m14.923s user 0m14.129s sys 0m0.460s
__________________
"It’s important to have goals when you pet. Otherwise you’re just rubbing another mammal for no reason." - Scott Adams |
04. 02. 2006. | #33 |
Python Ambassador
Master
|
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) %Generates random unique 8 character codes % %INPUT ARGUMENTS: % number_of_codes - desired number of codes % percent_of_extra_codes - percent of extra generated codes. % A non-zero value might be needed to eliminate nonunique codes % out_file - file to which the codes will be outputed %OUTPUT: % false_hit_chance - odds of a false hit %NOTES: % The codes themselves are a hexadecimal representation of randomly generated 32 bit integers % The odds of a false hit are number_of_codes/2^32 maximum_number_of_codes = 2^32; %do not change this or the code wont work if number_of_codes > maximum_number_of_codes error('ERROR: Unable to generate desired number of codes! Try decrasing the value of number_of_codes') end if percent_of_extra_codes < 0 error('ERROR: percent_of_extra_codes must be a non-negative number! Try increasing the value of percent_of_extra_codes') end codes = unique( randint(1, round( number_of_codes*(1 + percent_of_extra_codes/100) ), maximum_number_of_codes) ); length_of_generated_codes = length(codes); if length_of_generated_codes < number_of_codes error('ERROR: Failed to generate the desired number of codes! Try increasing the value of percent_of_extra_codes parameter.') end codes(number_of_codes+1:length_of_generated_codes) = []; %erase the unwanted codes fp = fopen(out_file, 'w'); fprintf(fp, '%08x\n', codes); fclose(fp); false_hit_chance = number_of_codes/maximum_number_of_codes; Kôd:
out_file = 'out.txt'; test_cases = [ 1e2 0.1 1e3 0.1 1e4 0.1 1e5 0.1 1e6 0.1 2e6 0.1 ]; %%%% DO NOT EDIT BELOW THIS LINE %%%% number_of_tests = size(test_cases, 1); tmp = sprintf('Starting the test with %d test case(s)...\n', number_of_tests); disp(tmp) for i = 1:number_of_tests number_of_codes = test_cases(i, 1); percent_of_extra_codes = test_cases(i, 2); tmp = sprintf('TEST %3d: CALLING generate_unique_codes(%d, %g, \"%s\")', i, number_of_codes, percent_of_extra_codes, out_file); disp(tmp) start_time = clock; generate_unique_codes(number_of_codes, percent_of_extra_codes, out_file); stop_time = clock; elapsed_time = etime(stop_time, start_time); tmp = sprintf('TEST %3d was done in %g second(s).\n', i, elapsed_time); disp(tmp) end disp('All test cases were successfully completed.') Kôd:
>> test Starting the test with 6 test case(s)... TEST 1: CALLING generate_unique_codes(100, 0.1, "out.txt") TEST 1 was done in 0.016 second(s). TEST 2: CALLING generate_unique_codes(1000, 0.1, "out.txt") TEST 2 was done in 0 second(s). TEST 3: CALLING generate_unique_codes(10000, 0.1, "out.txt") TEST 3 was done in 0.031 second(s). TEST 4: CALLING generate_unique_codes(100000, 0.1, "out.txt") TEST 4 was done in 0.375 second(s). TEST 5: CALLING generate_unique_codes(1000000, 0.1, "out.txt") TEST 5 was done in 3.766 second(s). TEST 6: CALLING generate_unique_codes(2000000, 0.1, "out.txt") TEST 6 was done in 7.797 second(s). All test cases were successfully completed. >> Šta na kraju da kažem do: The speed of my code sparkels your mind
__________________
Python Ambassador of Serbia |
04. 02. 2006. | #34 |
Igor Marinović
Expert
|
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++) { printf("%08x\n",rand(2000000000)); } Right tool for the right job |
04. 02. 2006. | #35 |
Boris
Grand Master
Datum učlanjenja: 01.12.2005
Lokacija: Novi Sad
Poruke: 775
Hvala: 5
156 "Hvala" u 2 poruka
|
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.. Svaka cast na resenju Petre
__________________
"It’s important to have goals when you pet. Otherwise you’re just rubbing another mammal for no reason." - Scott Adams Poslednja izmena od zextra : 04. 02. 2006. u 10:02. |
04. 02. 2006. | #36 |
Boris
Grand Master
Datum učlanjenja: 01.12.2005
Lokacija: Novi Sad
Poruke: 775
Hvala: 5
156 "Hvala" u 2 poruka
|
Moze i Perl (+ bash) za manje od 10 sec:
Kôd:
use Digest::MD5 qw/md5_hex/; use Time::HiRes qw/gettimeofday/; while( $i++ < 80_000 * 1.001 ) { my ( $m, $ms ) = gettimeofday; my $code = md5_hex( $m . $ms ); for( $a = 0; $a < 25; $a++ ) { print substr( $code, $a, 8 ), "\n"; } } Kôd:
$ time perl rnd.pl > /dev/null real 0m2.542s user 0m2.452s sys 0m0.032s $ time perl rnd.pl | sort -u | head -n 2000000 | wc -l 2000000 real 0m9.187s user 0m8.629s sys 0m0.320s
__________________
"It’s important to have goals when you pet. Otherwise you’re just rubbing another mammal for no reason." - Scott Adams Poslednja izmena od zextra : 04. 02. 2006. u 10:33. |
04. 02. 2006. | #37 |
Igor Marinović
Expert
|
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 ...
|
04. 02. 2006. | #38 |
Python Ambassador
Master
|
Hvala svima na pohvalama
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.
__________________
Python Ambassador of Serbia |
04. 02. 2006. | #39 | |
Python Ambassador
Master
|
Citat:
Ovako si odsekao 53.43% mogućih kodova što je najverovatnije razlog zbog kojeg dobijaš dva puta više duplikata.
__________________
Python Ambassador of Serbia |
|
04. 02. 2006. | #40 |
Boris
Grand Master
Datum učlanjenja: 01.12.2005
Lokacija: Novi Sad
Poruke: 775
Hvala: 5
156 "Hvala" u 2 poruka
|
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 @Petar: dobro zapazanje
__________________
"It’s important to have goals when you pet. Otherwise you’re just rubbing another mammal for no reason." - Scott Adams |
|
|
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 |