Generisanje random UNIQUE kodova

[bluesman]

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:

create table kodovi ( kod char(8) not null, primary key (kod));

Script će generisati kod, upisivati u tabelu, na svaki mysql error, on će da generiše ponovo taj kod sve dok ne prođe bez "duplicate key" greške i tek onda ide na sledeći u petlji. Kasnije samo uradim dump te tabele u bilo koji format i isporučim spisak od 2 miliona kodova.

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 :)

[MorenoArdohain]

Uvek moze brze :)
Napravi petlju koja generise te kodove, ali rezultate smesti u memoriju, u niz..
Pa tek onda sruci sav array u bazu

[bluesman]

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 :)

[noviKorisnik]

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?

[bokacbl]

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 :)

pa postavis da to radi u while petlji sve dok ne dobijes potreban broj kodova i povecavas counter nakon svakog uspjesnog upisa...mozda

[Petar Marić]

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

[MorenoArdohain]

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

[Ilija Studen]

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.

[bluesman]

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.

[Milos Vukotic]

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..
Moze i ovo Morenovo (osim sto treba $niz[$counter] = $broj]; ) samo da se u istoj while petlji negdje 'snima' dobijeni kod, a niz da sluzi samo za kontrolu. Sve pod uslovom da je in_array brzi od mysql-a :)

[MorenoArdohain]

Pa ja preferiram memoriju, manje ce drljati disk :)

[MorenoArdohain]

Moze i ovo Morenovo (osim sto treba $niz[$counter] = $broj]; )

Ne mora, key se automatski povecava

[noviKorisnik]

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.
Može biti, ali je dovoljno jednostavno da dozvoliš sebi luksuz da to testiraš. Deluje mi racionalnije od bar 2 miliona pojedinačnih inserta u bazu.

[dinke]

Uvek moze da koristi memory tabelu tj:

engine = memory

:)

[MorenoArdohain]

Kad bi vi ovako teoretisali i o mom geotargeted postu, cccc
http://www.devprotalk.com/showthread.php?t=587

[noviKorisnik]

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...
ini_set ('memory_limit', 19000000);
... valjano priprema memoriju za ovo.



// ali mu zato treba kila vremena ... stavio sam da se vrti za 200 000 i nikako da završi skriptu

[MorenoArdohain]

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)

[Petar Marić]

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:
brojevi = randint(1, 2e6, 2^32); Vreme izvršenja? Nešto malo više od 1 sekunde u virtuelnoj mašini.

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
podaci = sprintf('%x\n', randint(1, broj_kodova*multiplikator, 2^32)); Ovim korakom ćemo automatski dobiti broj_kodova*multiplikator kodova (u suštini su to 32-bitni brojevi u heksadecimalnoj reprezentaciji)

3. Izvršimo sledeći kod:
brojac = 1;
delta = broj_kodova;
4. Napravimo view jedinsteni_kodovi u bazi koji se sastoji od SELECT DISTINCT... SQL upita, tako da možemo jednostavnim brojanjem redova u view-u da saznamo koliko imamo jedinstvenih kodova, i hajde da kažemo da tu vrednost čuvamo u broj_jedinstvenih_kodova

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. brojac = delta+brojac;
delta = (broj_kodova - broj_jedinstvenih_kodova) * faktor_ubrzanja;
8. Ako je delta > 0 onda se vraćamo na korak 5

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

[dinke]

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)
Pa rekoh ja lepo, a niko da slusa :)

MySQL tabela:
create table kodovi ( kod char(8) not null, primary key (kod)) engine = memory;

[bluesman]

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)

[Petar Marić]

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 (http://www.devprotalk.com/showpost.php?p=6030&postcount=18) može imati monstruozno visoku brzinu konvergencije ako se pravilno izaberu multiplikator i faktor_ubrzanja.

[bluesman]

Samo sam pogresno napisao, na isto sam mislio :)

BTW, evo nekih RAZOCARAVAJUCIH rezultata.

Koristio sam funkciju array_rand (), prvi parametar je array:
$a = array ('0','1','2','3','4','5','6','7','8','9',
'a','b','c','d','e','f','g','h','i','j','k','l','m ','n','o','p','q','r','s','t','u','v','w','x','y', 'z');

drugi parametar, naravno 8.

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:

srand((float) microtime() * 10000000);

$count_total = 300000; // koliko kodova da generise
$len = 8; // dužina koda u karakterima

$a = array ('0','1','2','3','4','5','6','7','8','9',
'a','b','c','d','e','f','g','h','i','j','k','l','m ','n','o','p','q','r','s','t','u','v','w','x','y', 'z');

for ($i = 1; $i <= $count_total; $i++)
{
$s = "";
$rand_keys = array_rand($a, $len);
foreach ($rand_keys as $key => $val)
{
$s .= $a[$val];
}

$result = mysql_query('insert into kodovi values("'.$s.'")');
if (!$result)
{
srand((float) microtime() * 10000000);
echo mysql_error()."\r\n";
$i--;
}

}


I to je bilo žešće sranje od scripta jer je konstantno generisao identične kodove. Kako i zašto, nemam pojma.

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:

if (!$result)
{
shuffle($a);
srand((float) microtime() * 10000000);
echo mysql_error()."\r\n";
$i--;
}


Znači, kada god naidje na duplikat, uradi shuffle().

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.

[Petar Marić]

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 (http://en.wikipedia.org/wiki/Mersenne_Twister), 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 (http://en.wikipedia.org/wiki/Mersenne_Twister), samo umesto rand() koristi mt_rand() (http://www.php.net/manual/en/function.mt-rand.php).

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.

[marinowski]

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:

?
set_time_limit(0);
ini_set ('memory_limit', 300000000);
$out = array();
$t = time();
$i = 0;

while (sizeof($out)<2000000) {
if (!(++$i%100000)) {
print "$i ".sizeof($out)."<BR>";
flush();
}
$s = substr(md5(microtime().rand(1,1000)),5,8);
if (!$check[$s]) {
$check[$s]++;
$out[] = $s;
}
}

$t = time() - $t;
print "izvrseno za $t s, provereno $i kodova<BR>";

for ($i = 0; $i<100; $i++) {
print "$out[$i]<BR>";
}

?>


Programče ispiše nešto tipa:
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.

[marinowski]

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

[noviKorisnik]

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
set_time_limit(300);
ini_set ('memory_limit', 300000000);

$check = array ();
$output = "";
$nl = "\r\n";
$inserted = 0;

while ($inserted < 2000000) {
$s = substr(md5(microtime().rand(1,1000)),5,8);
if (!isset ($check[$s])) {
$check[$s] = true;
$output .= "$s$nl";
$inserted++;
}
}

$f = fopen ('bluesman.txt', 'w');
fwrite ($f, $output);
fclose ($f);
?>
done

Ostaje samo jos jedna primedba - md5 daje u izlazu heksadecimalne cifre, a ne alfanumerike.

[MorenoArdohain]

Igore, cestitam na resenju, to je ono sto je trebalo da napisem :)

[bluesman]

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.

na kraju sam ipak morao da restartujem masinu.

[noviKorisnik]

Ono što mene još zbunjuje je što je i md5(microtime()...) generisao nekoliko desetina hiljada duplikata.
Čudno obzirom na rezultat koji navodi Igor sa svega 490 duplikata na 2 miliona. Testirao sam i dobio sličan rezultat.

[marinowski]

- 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.
Pretpostavljam da ti je nestalo memorije za ovaj proces, otud usporenje. Proces zauzima nesto manje od 300Mb, treba mu toliko sveze memorije da bi se izvrsio, kao sto sam vec naglasio.

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 :)

[marinowski]

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:

#!/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.

[zextra]

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..
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...
$ time perl rand.pl | sort -u | wc -l
1999556

real 0m14.923s
user 0m14.129s
sys 0m0.460s

[Petar Marić]

OK, na kraju sam i ja napravio rešenje - doduše u MATLAB-u.

generate_unique_codes.m:
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:
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:
>> 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

[marinowski]

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:

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 :)

[zextra]

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 :)

[zextra]

Moze i Perl (+ bash) za manje od 10 sec:

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

$ 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%).

[marinowski]

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

[Petar Marić]

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.

[Petar Marić]

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

[zextra]

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 :)

[BraMom]

Nisam citao celu diskusiju tako da se unapred izvinjavam ako je neko vec dao ovu ideju.

Problem se svodi na teoriju brojeva, dakle ciklicna grupa i njen generator.

npr. trebaju mi sve cifre (0-9) oznacicu skup za Z10, teorija kaze da ako uzmem bilo koji broj, zvacemo ga g, koji je uzajamno prost sa 10, on je generator grupe Z10 u odnosu na sabiranje po modulu 10

da ne davim mnogo, uzmimo g=3, 3 i 10 su uzajamno prosti, ok, generator dobijam samo sabiranjem po modulu 10, znaci:
3 mod 10 = 3
6 mod 10 = 6
9 mod 10 = 9
12 mod 10 = 2
...

teorija kaze da ce se ovako dobiti svi elementi grupe, tj. u nasem slucaju cifre od 0-9, nema ponavljanja

I, sto je najlepse, tacno znas koji je i-ti clan, tj. mozes da ga izracunas, a kako je ovakav generator i bijekcija, da se napraviti i inverz, tj. moze se izracunati da je npr. cifra 9, dobijena kao treci clan niza.

Ovu ideju treba malo razraditi i nema potrebe za smestanjem kodova u bazu.

[bluesman]

Posto nisi procitao od pocetka: traze se cifre 0..9 i karakteri a..z (case insensitive), ne samo cifre.

Iskreno, nisam bas najbolje shvatio tvoj predlog.

[BraMom]

Nisam čitao celu diskusiju, a postavku problema sam pročitao detaljno.
Možda je moj odgovor bio malo štur, ajde da probam detaljnije.

Pretpostavio sam da je svejedno da li si dobio kodove od cifara i slova, kakve tražiš, ili samo od cifara, jer kod od npr. 10 (ili više) cifara lagano možeš da prekodiraš u kod od 8 slova i cifara, ok?

Izgleda i da je osim jedinstvenosti, bitno da kodovi ne mogu da se "provale", tj. da bude onemogućeno da se na osnovu određenog broja kodova generiše sledeći.

Evo mog rešenja za 4 cifre od 0..9 (napisao bih i za 2 miliona, ali je potpuno isto).
Izabereš prvi kod, neka je to 7777 (nije bitno kakav je) i uzajamno prost broj sa 10000, bilo bi idealno da je to prost broj, tako je najteže za razbijanje, ali za primer će biti dobar i 7811 i pustiš ovako nešto (nemam instaliran paint :) ):

<?php
$start = 7777;
$seed = 7811;
for($i=0; $i<100; $i++)
{
$code = ($start + $i * $seed) % 10000;

echo $i, ' : ', $code, '<br>';
}
?>

Ovo ti daje (teorija brojeva garantuje) sve brojeve od 0 do 9999. Jasno dobijaćeš i brojeve sa manje cifara od 4, ali uvek možeš da dopišeš nule ispred.

Još koja random cifra između da skreneš trag i izbegneš kodove tipa 1111, i prekodiraš dve tri cifre u slova da dobiješ ono što si tražio, to bi bilo to.

Je l' sad bolje?

P.S.
Mislim da sam zaslužio veći rejting od "novi član"?

[bluesman]

Nešto sam sada umoran da čitam pažljivo, hoću samo da ti odgovorim za "novi član"... samo ti piši i promeniće ti se status onoliko brzo koliko doprinosiš forumu :)

[Petar Marić]

Napiši implementaciju svog rešenja da uradimo benchmark i da vidimo imamo li novog šampiona, način rešavanja problema mi je interesantan.

Nekoliko puta si spomenuo termin "teorija brojeva". Koja i imaš li link ka dodatnim informacijama o njoj? My geek sense is tingling, ovo može da bude nešto jako interesantno.

Eh da, imam jedno offtopic pitanje za tebe: Dolaziš nam sa PMF-a?

[Petar Marić]

$code = ($start + $i * $seed) % 10000;
Videvši ovu liniju koda zasvrbeo me je mozak, a sad vidim i zašto:
Formula za izračunavanje koju si naveo me je jako podsetila na ovu (A, B i M su const.):
http://upload.wikimedia.org/math/e/f/8/ef869c3b00b5f7245b90082bef233a1b.png
što je opšti oblik formule za LCG (http://en.wikipedia.org/wiki/Linear_Congruential_Generators) (linearni kongruentni generator) što je jedan od načina za generisanje pseudo-slučajnih brojeva.

Iskreno rečeno, sad mi se tvoje rešenje i ne čini toliko hot. U ovom članku (http://en.wikipedia.org/wiki/Linear_Congruential_Generators) jasno piše da je korišćenje LCG-a u bilo kakvoj formi izrazito loša ideja u slučajevima kada je potreban visok kvalitet slučajnih brojeva (kao što je ovde slučaj). Ipak je Mersenne Twister algoritam zakon za ovakve stvari ;)

PS: Eh, da ima li ko da preporuči neki softver i/ili MATLAB kod/funkciju/biblioteku/toolkit za spektralnu/frekvencijsku analizu (inače ću ponovo morati da pišem svoje funkcije)? Mogli bismo da napravimo benchmark kvaliteta rešenja koji nam daju programi, tj. ako ima zainteresovanih.

[ivanhoe]

ovo je varijanta linearnog kongruentnog generatora... ako se dobro secam formula kojom se dobija sledeci pseudo-slucajn broj je:

x(i+1) = (A*x(i) + C) mod OPSEG

gde je x(i) prethodni rnd broj (ili seed za prvi u nizu), a A i C proizvoljne konstante...ono za uzajamno proste brojeve je uslov za dobijanje max. duzine ciklusa...

Koliko ja znam ovo se smatra kriptografski najslabijim pseudo-rnd generatorom (ne pitaj me zasto ga je najlakse razbiti, nemam pojma, ali tako pise u svim knjigama...)

EDIT: ostao mi otvoren prozor, pa nisam video da je petar u medjuvremenu napisao ovo isto...sorry

[nixa]

( ne osećam sebe da sam dovoljno geek da dodam nešto )

Drug novi član BraMom dobrodošao

bluesman sad si nadrljao počinje da se pravi i Niški lobi ovde :) Imate be svi da propričate po naški

[Petar Marić]

@invanhoe: Ako nacrtaš parove (x(i-1), x(i)) primetićeš strukturu rešetke. Ako uzmeš tri uzastopna pseudo-slučajna broja dobićeš nešto vrlo slično ovom:
http://upload.wikimedia.org/wikipedia/commons/a/a3/Lcg_3d.gif

I šta nama rešetka u suštini znači? Ako znamo jedan pseudo-slučajan broj i znamo algoritam (što skoro uvek znamo) onda možemo generisati sve pseudo-slučajne brojeve nakon njega.

[BraMom]

Hvala svima na dobrodošlici...

@BlueIce
Da, dolazim sa PMF-a u Nišu, u pravu si da ovo nije ništa novo, čista primena Teorije Brojeva koju sam slušao kod prof Žikice Peroviča na I godini studija.

Pogledaću Mersenne twister kad imama vremena, toga nije bilo kad sam učio ovu oblast, jer još nije bio ni napravljen (1997).

Što se tiče linkova, ne bavim se profesionalno matematikom, ali sigurno možeš da nađeš masu toga po netu (Number theory).

Nije mi bila ideja da pišem gotovo rešenje, a ni da postanem "šampion", čisto sam hteo da skrenem pažnju da postoji teorija koja pokriva temu i dam najjednostavniji primer...

[Petar Marić]

Svi koji su zainteresovani za benchmark kvaliteta raspodele neka objave na netu kompresovane data fajlove sa generisanim kodovima, koji moraju ispuniti sledeće uslove:
- 2 miliona jedinstvenih kodova
- kodovi moraju biti predstavljeni heksadecimalnim formatom 32 bitnih neoznačenih celih brojeva
- brojevi moraju biti sortirani po rastućem redosledu
- kodovi su međusobno razdvojeni jednim new-line karakterom (0x0D iliti "\n")

Vidimo se kod L2 keša ;)

[BraMom]

A generalni sponzor, svečano proglašenje pobednika...
Možda neka nagrada?

[Petar Marić]

Pitaj bluesman-a, on je organizator ovoga skupa/takmičenja - ipak je on pokrenuo temu ;)

[bluesman]

LOL :)

bluesman je odradio svoje jos posle 1. poruke, a vidim da ni vama nije lose posto ste razgibali mozak.

[Petar Marić]

I to što kažeš - malo mentalne gimnastike mi je dobro došlo :D