DevProTalk - Generisanje random UNIQUE kodova

DevProTalk (http://www.devprotalk.com/index.php)

- Programiranje (http://www.devprotalk.com/forumdisplay.php?f=23)

- - Generisanje random UNIQUE kodova (http://www.devprotalk.com/showthread.php?t=588)

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";

}

A kako postići unique? sa sort -u komandom. Sve zajedno traje negde oko 40 sekundi. (pretpostavljam da je sort gutao memoriju)

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/;

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 )

    );

}

A rezultat izvrsavanja...

Kôd:

$ time perl rand.pl | sort -u | wc -l

1999556



real    0m14.923s

user    0m14.129s

sys     0m0.460s

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;

test.m:

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

Rezultati testa:

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.

>>

Naravno svi kodovi su jedinstveni i generiše se tačno zahtevani broj kodova, tj ako se mogu generisati pri zadatim uslovima.

Š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++) {

        printf("%08x\n",rand(2000000000));

}

gde je 2002000 'nesto vise' od 2 miliona, a 2 milijarde dovoljno veliki broj da se ne pojave duplikati. Rezultat izvrsavanja uz sort -u je bio negde oko 17s.

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/;

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";

    }

}

Manje petljanja - brze izvrsenje...

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

Naravno, MATLAB opet odradi posao znatno brze. Pandan MATLAB-ovog resenja radi malo sporije (11 sec prosek), i generise neznatno vise duplikata (0.05% umesto 0.025%).

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:

Originalno napisao zigor

...
gde je 2002000 'nesto vise' od 2 miliona, a 2 milijarde dovoljno veliki broj da se ne pojave duplikati. Rezultat izvrsavanja uz sort -u je bio negde oko 17s.
...

Ne bi trebao da koristiš opseg od [0..2e9-1] već [0..2^32-1] upravo zato da bi imao uniformnu raspodelu generisanih kodova.
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 :)