Generisanje random UNIQUE kodova

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