Generisanje jedinstvenog slucajnog broja, koji vec ne postoji u bazi

[srdjan]

Svaki korisnik ima svoj jedinstven 6-cifren slucajan broj (token) generisan prilikom registracije. Broj se generise na ovaj nacin:

SELECT
  random.value 
FROM
  (SELECT 100000 + TRUNCATE(RAND(UNIX_TIMESTAMP()) * 900000, 0) AS value) random
WHERE
  random.value NOT IN (SELECT token FROM user)

Ako ovo vrati NULL, to znaci da je RAND() vratio broj koji vec postoji u koloni user.token. U petlji, gornji SELECT izvrsava dok se ne dobije broj. Taj broj se insertuje zajedno sa ostalim podacima.

E sad, ovo radi "dovoljno dobro" , medjutim postoje 2 problema:

1. radice sve sporije kako bude korisnika
2. moguce je da se dogode 2 identicna tokena - mogu to da resim tako sto bi bio UNIQUE INDEX na polju, a u slucaju INSERT greske ponovi se ceo proces generisanja.

PITANJE: da li neko zna za inteligentnije resenje za ovaj problem, idealno bi bilo da nema petlje tako da se izbor jedinstvenog slucajnog broja moze staviti u INSERT.

[Peca]

jedino da SELECT-ujes iz tabele sve brojeve, ubacis ih u PHP array, i onda:
while (1)
{
$rnd=rand(1,100000);
if (!isset($array[$rnd])) break;
}

ne vidim brzi nacin.

p.s. obezbedi PHP-u dovoljno memorije.

------------

drugo resenje, pa stavi UNIQUE INDEX, pa 'na slepo' insert-uj [u petlji] dok ne prodje?
mislim da ce to najbrze raditi... jedino ce biti previse neuspesnih insert-a kada popunis kombinacije preko 95%

[degojs]

Jedino koliko-toliko prihvatljivo rešenje koje mi pada na pamet jeste da imaš jednu tabelu koja ima samo jednu kolonu (npr. ID) i koja je već popunjena vrednostima redom od 1 do 999999.

I kada izabereš (slučajno) neki broj (red) iz te tabele, onda odmah i ukloniš (delete) taj red, tako da prilikom sledećeg biranja ne možeš ponovo da uzmeš taj broj.

Svaki put naravno biraš red koji je unutar 1..count(*) skupa.

I to je to.

[DejanVesic]

U dva projekta sa sličnom tematikom sam radio sledeće:

- generišem niz od 0 - 999,999 elemenata gde

a[i] = i, i = 0 .. 999,999

- izaberem kulturan RND generator i:

rnd1 = NextRnd();
rnd2 = NextRnd();

for(j=0; j < 1,000,000; j++) 
{
    swap(a[rnd1],a[rnd2]);
    rnd1 = NextRnd();
    rnd2 = NextRnd();
}

Kreiram dve tabele:

MAXUSED( Current int);

Randoms( RecNo Int PK, Value Int);

U MaxUsed ide inicijalno samo jedan slog, Current = 0;

Randoms popunim sa:

for(j=0; j < 1,000,000; j++) 
{
    INSERT INTO RANDOMS( j, a[j]);
}

Sad, kako ko dođe na sajt:

- zaključam prvi slog (i jedini) od MaxUsed, pokupim vrednost (nextToUse), uvećam za jedan i vratim u prvi slog

- dohvatim slog br. nexToUse (po indeksu iz Randoms) i vrednost (Value)

Ovako imam intenzivan proces jednom (kada se radi deployment projekta) a posle trivijalne operacije koje su jako brze (update jednog sloga, select drugog).

[ivanhoe]

ovo sto kaze degojs, ili da pomeris generisanje random broja u kod, a onda sa unique indexom mozes da kontrolises da ne bude kolizija..

plus unix_timestamp i nije bas random, lako se da pogoditi ako se zna priblizno vreme regstracije, pa bi bilo bolje sa nekim pravim random generatorom to raditi...

[srdjan]

Tnx svima

Verovatno ce biti degojs-ova ideja prekalkulisanih slucajnih brojeva.

Pada mi na pamet i kombinacija prekalkulisanih i generisanja novih, prema potrebi.

token      used
-----------------
345334       1
123562       1
926456       1
128524       0
745236       0
...
-----------------

Kada count(token) WHERE used = 0 dostigne minimum X ("padne na rezervu"), onda se doda jos Y komada novih slucajnih.

[filmil]

Originalno napisao DejanVesic

U dva projekta sa sličnom tematikom sam radio sledeće:
(...)

rnd1 = NextRnd();
rnd2 = NextRnd();

for(j=0; j < 1,000,000; j++) 
{
    swap(a[rnd1],a[rnd2]);
    rnd1 = NextRnd();
    rnd2 = NextRnd();
}

На жалост, метод који си описао није добар, јер низ који се добија нема униформну расподелу(*).

Решење са бирањем случајног броја и избацивањем те вредности из скупа могућих бројева даје униформну расподелу (то је плус), по цену меморијског простора који је пропорционалан величини простора (то је минус) кључева.

Треће решење које ми пада на памет, које захтева константан простор и константно време за израчунавање, јесте генерисање неког хеша (МД5, СХА1) на основу (рецимо) монотоног системског сата (то је сат који се састоји од две компоненте: системског времена, и инкремента који се повећава за један сваки пут када се генерише један хеш. Згодно је за почетни инкремент узети излаз из /dev/random. Монотоно време је збир дотична два.)

Вероватноћа да се хешеви милион узастопних уноса сударе је занемарљиво мала (из праксе: још нисам наишао ни на једну), а расподела кључева треба да је униформна.

ф

(*) Доказ тврдње, за радознале: горе поменут алгоритам има 1е6^1e6 могућих исхода пермутовања. Пошто укупно има 1е6! пермутација од милион елемената (! = факторијел), што је број који је мањи од милион на милионити степен, то се свака од пермутација мора да понови много пута.

Ако је расподела униформна, онда се свака пермутација јавља једнак и цео број пута. Број понављања сваке пермутације је онда 1e6^1e6/1e6!, укупан број исхода подељен бројем различитих исхода.

Међутим, овај број не може да буде цео, на пример зато што је именилац дељив са 3, док бројилац није дељив са 3.

Закључак — пермутовање низа на горе описани начин не може да да униформну расподелу бројева, па ни униформну расподелу пермутација низа 0..1е6-1.

[cvele]

Sto komplikujes ? Napravi lepo sekvencu(ako koristis mysql, simuliraj sekvencu). Kada dobijes iz sekvence jednocifreni broj, zalepi 5 nula na pocetak, ili postavi sekvencu da pocinje na broju 99999, kako ti milije.

[srdjan]

^ Pa ne treba mi sekvenca nego slucajan broj