DevProTalk
Strana 1 od 2 1 2 >
Prikažite 40 poruka iz ove teme na jednoj stani

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)

bluesman 01. 02. 2006. 22:34
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:
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 01. 02. 2006. 22:40
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 01. 02. 2006. 23:07
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 01. 02. 2006. 23:13
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 01. 02. 2006. 23:13
Citat:
Originalno napisao 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 :)
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ć 01. 02. 2006. 23:25
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 01. 02. 2006. 23:30
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 01. 02. 2006. 23:37
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 01. 02. 2006. 23:41
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 01. 02. 2006. 23:44
Citat:
Originalno napisao 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..
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 01. 02. 2006. 23:47
Pa ja preferiram memoriju, manje ce drljati disk :)

MorenoArdohain 01. 02. 2006. 23:48
Citat:
Originalno napisao Milos Vukotic
Moze i ovo Morenovo (osim sto treba $niz[$counter] = $broj]; )
Ne mora, key se automatski povecava

noviKorisnik 01. 02. 2006. 23:55
Citat:
Originalno napisao bluesman
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 02. 02. 2006. 00:00
Uvek moze da koristi memory tabelu tj:

engine = memory

:)

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

noviKorisnik 02. 02. 2006. 00:14
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:
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 02. 02. 2006. 00:46
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ć 02. 02. 2006. 00:59
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);
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
Kôd:
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:
Kôd:
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.
Kôd:
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 02. 02. 2006. 01:14
Citat:
Originalno napisao 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)
Pa rekoh ja lepo, a niko da slusa :)

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

bluesman 02. 02. 2006. 02:00
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ć 02. 02. 2006. 02:06
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.

bluesman 02. 02. 2006. 02:35
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:
$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:
PHP kôd:
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:
PHP kôd:
    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ć 02. 02. 2006. 02:57
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.

marinowski 02. 02. 2006. 06:21
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:
?
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 02. 02. 2006. 06:44
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 02. 02. 2006. 09:57
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:
<?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 02. 02. 2006. 12:15
Igore, cestitam na resenju, to je ono sto je trebalo da napisem :)

bluesman 02. 02. 2006. 14:54
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]

noviKorisnik 02. 02. 2006. 16:35
Citat:
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 02. 02. 2006. 16:56
Citat:
- 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 03. 02. 2006. 19:40
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.

zextra 04. 02. 2006. 01:39
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

Petar Marić 04. 02. 2006. 03:42
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

marinowski 04. 02. 2006. 06:58
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 :)

zextra 04. 02. 2006. 09:47
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 :)

zextra 04. 02. 2006. 10:26
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%).

marinowski 04. 02. 2006. 10:52
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ć 04. 02. 2006. 11:17
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ć 04. 02. 2006. 11:36
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.

zextra 04. 02. 2006. 11:51
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 22:57.
Strana 1 od 2 1 2 >
Prikažite 40 poruka iz ove teme na jednoj stani

Powered by vBulletin® Verzija 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Copyright © DevProTalk. All Rights Reserved.

Mišljenja, saveti, izjave, ponude ili druge informacije ili sadržaji nastali na Sajtu su vlasništvo onoga ko ih je kreirao, a ne DevProTalk.com, tako da ne morate da se oslanjate na njih.
Autori poruka su jedini odgovorni za ovakve sadržaje. DevProTalk.com ne garantuje tačnost, kompletnost ili upotrebnu vrednost informacija, stavova, saveta ili datih izjava. Ne postoje uslovi pod kojima bi mi bili odgovorni za štetu ili gubitak koji je posledica bilo čijeg oslanjanja na nepouzdane informacije, ili bilo kakve informacije nastale kroz komunikaciju između registrovanih članova.
Web sajt može sadržavati linkove na druge web sajtove na Internetu ili neke druge sadržaje. Ne kontrolišemo niti podržavamo te druge web sajtove, niti smo pregledali bilo kakve sadržaje na takvim sajtovima. Mi nećemo biti odgovorni za legalnost, tačnost ili prikladnost bilo kog sadržaja, oglasa, proizvoda, usluga ili informacije lociranim na ili distribuiranih kroz druge web sajtove, niti za bilo kakvu štetu nastalu kao posledica takvih informacija. DevProTalk.com drži i čuva druga prava vlasništva na web sajtu. Web sajt sadrže materijale zaštićene copyright-om, zaštitne znakove i druge informacije o pravu vlasništva ili softver. Članovi mogu poslatu informacije zaštićene pravima vlasništva njihovih nosilaca i ona ostaju zaštićena bez obzira da li su oni koji prenose te informacije to naveli ili ne. Osim informacija koje su u javnom vlasništvu ili za koje dobijete dozvolu, nemate pravo da kopirate, modifikujete ili na bilo koji način menjate, objavljujete, prenosite, distribuirate, izvršavate, prikazujete ili prodajte bilo koju informaciju zaštićenu pravima vlasništva. Slanjem informacija ili sadržaja na bilo koji deo DevProTalk.com, Vi automatski dozvoljavate i predstavljate garanciju da imate pravo da dozvolite DevProTalk.com ili članovima DevProTalk.com bespovratnu, kontinualnu, neograničenu, globalnu dozvolu da koriste, kopiraju, izvršavaju, prikazuju i distribuiraju takve informacije i sadržaje i da iz takvih sadžaja koriste bilo koji deo u bilo koje svrhe, kao i pravo i dozvolu da koriste gore navedene sadržaje. Svi zaštitni znakovi (trademarks), logotipi, oznake usluga, firme ili imena proizvoda koji se pominju na ovom web sajtu su vlasništvo kojim raspolažu njihovi vlasnici.