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)

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:


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

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:


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

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:


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

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:

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.

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