[python] re: hlavolam

[Radek Kanovsky]

On Wed, Jun 15, 2005 at 07:45:44AM +0200, pavel.kosina wrote:

> >Někdo tady psal, že spoléhat se nato, že se slovník sám srovná, je
> >spoléhání na náhodu,
> >ale ono to fakt vypadá, že se srovná vždycky, takže je to spíš výhoda
> >použití slovníku.
> 
> nejsem super teoretik, ale fakt si jen tak matně vpomínám, že v obyčejném 
> výpise slovníku se může lišit pořadí jednotlivých položek v závislosti na 
> systému. Na jednom stroji to bude asi porad stejne, to je fakt, ale na 
> jinych strojich, jinych op. systemech, to je nezarucitelne.

V tomto velmi konkretnim pripade to bude podle me fungovat vzdy, ale
jako reseni bych to neprijal :-)

Funguje to proto, ze hash prirozeneho cisla, je samo prirozene cislo
(hash(33) == 33), proto se jednotlive polozky ukladaji ve vnitrnim poli
slovniku "ma_table" za sebou (jako v normalnim poli). Napr.:
    
    d = {1:'C', 2:'X'}

    ma_table   item
    ------------------
    0          NULL
    1          (1,'C')
    2          (2,'X')
    3          NULL

    d.items() == [(1,'C'), (2,'X')] # OK

Pokud by byl pridan do slovniku klic, ktery je vetsi nez velikost
ma_table, cele se to rozhodi, protoze hash se prepocitava dalsimi
algoritmy tak, aby vysledek byl mensi nez velikost interni struktury
slovniku a aby ukazoval na prazdne misto. Napr.:

    d = {1:'C', 2:'X', 8:'A'}

    ma_table   item
    ------------------
    0          (8,'A')
    1          (1,'C')
    2          (2,'X')
    3          NULL

    d.items() == [(8,'A'), (1,'C'), (2,'X')] # Spatne

Cili musi platit, ze klice jsou integery, a hodnota zadneho klice
nesmi presahnout (+/- urcita tolerance) pocet klicu, coz v pripade
hlavolamu vzdy plati. Tolerance je zde proto, ze velikost ma_table
se meni skokove, ne po pridani jedne polozky do slovniku.

Zdravi,

Radek Kaňovský