dalsi hlavolam WAS: jak z toho ven

[Ing. Vlastimil Pospíchal]

On Mon, Jun 30, 2003 at 02:22:16 +0200, Petr Vileta wrote:
> > > Takze kdyz tam dam pro jistotu 100 pokusu, tak docela
> > > urcite nastane stav, kdy by se to podarilo na 101. pokus :-)
> >
> > A nutí vás snad někdo omezit počet pokusů? Pouze vám vysvětluji, že
> > pravděpodobnost, že by vám 100 pokusů nestačilo, je zcela zanedbatelná.
> > Problémy nastanou až při téměř úplném nasycení - a to by svědčilo
> > o nedostatečně velkém rozsahu.
> Jasne, jenze pri velkem nasyceni to bude trvat dlouho a bylo by vhodne o tom
> navstevnika nejak uvedomit. To ale znamena napred udelat nejaky SELECT
> COUNT(*) a podle vysledku bud rovnou zacit generovat, nebo poslat nejakou
> stranku s upozornenim, ze to muze trvat dlouho...

... což znamená další zdržování. Jakmile je počet unikátních klíčů vyčerpán
řekněme z 90% (záleží na kvalitě generátoru a KROKU po kolizi), svědčí to
o špatně navrženém systému klíčů. Pokud by k takové situaci mohlo dojít,
byť jen teoreticky, je nutné klíč příslušně prodloužit. Pokud by klíč měl
být zapamatovatelný a neměl by přesáhnout 6 číslic, přidal bych k nim sérii
ze dvou znaků, nejlépe iniciály jména. Např. VP456785. Riziko kolize se tak
výrazně sníží.

> Ja ani zadavatel v tuhle chvili nedokazeme rici, jestli se soutez uchyti
> a bude tam statisice prihlasenych, nebo to bude skomirat na desitkach.
> Petr

To člověk nikdy neví, ale je nutné na to být připravený. Pokud je potřeba
vybírat z konečné množiny klíčů, je nezbytné, aby ta množina byla dostatečně
velká.

Skvělý nápad byl s pseudogenerátorem založeným na prvočísle, který postupně
vybere všechny klíče, aniž by docházelo ke kolizím. Jen tak cvičně jsem si
zkusil

#!/usr/bin/perl -w
$a=1;
for(1..899980){
   $a=$a*7%899981;
   print $a+100000,"\n";
}

Generována byla všechna čísla <100001..999980> a "kupodivu" se žádné
neopakovalo. Přitom generovaná posloupnost vypadala vcelku náhodně.
Místo čísla 7 je možné použít třeba 25457 nebo jiné vhodné prvočíslo.

Pozor, všechna prvočísla se nehodí, například 25409 je pro tento případ
vyloženě nevhodné, protože vyrobí jen 5294 unikátních čísel a pak se
začnou opakovat.

Kit
-- 
Ing. Vlastimil Pospíchal
http://www.hoteldrnholec.cz