Effektiv random select - uden tilbagelægning

Der må være flere forskellige tilnage.

Men umiddelbrat tænker jeg i retning af:

lave en tabel pin med to felter val (integer) og inuse (boolean)

og bruge følgende til at assigne med:

SELECT val FROM pin WHERE NOT inuse ORDER BY RAND() LIMIT 1
gem værdi af val i X
UPDATE pin SET inuse=TRUE WHERE val=X AND NOT inuse
check antal opdaterede rækker, hvis 0 så træk en ny værdi fordi nogen snuppede denne for næsen af os

Jeg har selv tænkt på noget lignende...

Det virker dog lidt voldsomt at skulle oprette alle pinkoder på forhånd. Med til historien hører også, at der tilknyttes en del ekstra information til pinkoden (udleveringsdato, reference til administrator, index på koden, index på datoen etc. etc. etc.) Tabellen kommer således til at fylde en del.

PT. er min fremgangsmåde:
1) Vælg en tilfædig pinkode
2) Hvis koden eksisterer i tabellen, gå til 1) igen
3) Hvis koden ikke eksisterer, opret den i tabellen og returner pinkode

Det er imidlertid hamrende ineffektivt når tabellen begynder at vokse.

Jeg kan gøre en del fra min applikation (cache), men hver pinkode fylder min 3 bytes -> i praksis 4 hvis ikke jeg skal definere nye (ineffektive) datatyper.

4bytes*999999=> 3,8MB RAM hvis jeg bruger et simpelt array.

Jeg ville nok også lave den i app. Men nu spurgte du jo i MySQL kategorien.

Med logik i app skal du have et uniks index på feltet og have en logik som:

top:
træk random nummer
select
hvis fundet gå til top
insert
hvis fejl gå til top

Den select bør være lynhurtig hvis der er index på feltet.

Data er ikke specielt store.

For DB løsningen vil det fylde 1 million x måske 50 bytes = 50 MB. Det er vel max.
for 5 øre harddisk.

For app løsningen vil 1 million x 1 byte (du behøver kun 1 byte til at markere ibrug status)
fylde 1 MB. Hvilket er under 1 øre RAM.

Fremfor et array med inuse kunne du vælge en associativt array/Map/Dictionary data struktur.

Der *ER* hurtigt - så længe der er lille chance for positiv match i select.

Worst case kan jeg dog risikere at hænge uendeligt i select(random) så snart der er blot een optaget pinkode. I praksis begynder problemerne at dukke op når ca 1/3 af koderne er i brug.

<ole>

Hvis feltet er unikt, kunne man vel godt undvære select'en og bare sige:

top:
træk random nummer
insert
hvis fejl (1062, hvis allerede eksisterer) gå til top

/mvh
</bole>

En variant af den første måde: generer alle pinkoder, og gem dem i en tabel, men "bland" pinkoderne i tabellen i en app, så du blot altid skal tage den første, der ikke er i brug. Med passende index er det hurtigt!

Jeg mener løsninger med "ORDER BY RAND()" eller
  "top:
  træk random nummer
  select
  hvis fundet gå til top"
er nødløsninger, eller kun for få data. De kan begge være tunge.

svj>

Med 1/3 fill, så vil sandsynligheden for at måtte søge N gange være 1/3^N - kan det virkeligt være så slemt.

olebole>

Jeg har en formodning om at en select er betydeligt hurtigere end en mislykket insert.

erik>

Smart. Det er uden tvivl det hurtigste.

arne_v >> det er slet ikke utænkelig, men det skal vel vejes op imod, at hver gang inserten lykkes, er selecten overflødig(?) ... i dunno  =)

- men under alle omstændigheder er Eriks fiksest