W dniu 2013-09-24 00:53, Piotrne pisze:
> W dniu 2013-09-23 22:35, Wojciech Muła pisze:
>
>> No dobra, a dlaczego nie możesz posługiwać się piątką liczb 1..52
>> i potraktować je jako cyfry dla systemu liczenia o podstawie 52?
>> Wtedy miałbyś od razu indeks do tablicy, kosztem 5 mnożeń i 4 dodawań.
>
> Przypuszczam, z powodem jest 52^5 = 380204032, większe od 2,5 miliona.
>
>
>> Jeśli to jednak nie przejdzie, to może lepiej rozważ użycie drzew
>> trie.
>
>
>
> Napisałem funkcję c2num, która wykonuje przekształcenie, o które pytał
> autor wątku. W funkcji używane są współczynniki dwumianowe, które
> oczywiście można stablicować zamiast liczyć za każdym razem.

Pytacz pewnie by docenił dwa słowa, skąd wzorek;)


Współczynniki pewnie rzeczywiście najłatwiej stablicować,
na pewno nie mogą zostać tak:

> /* Współczynnik dwumianowy */
> int binom(int n, int k)
> { if ((k==0) || (k==n)) return 1; else return
> binom(n-1,k-1)+binom(n-1,k); }

Odpalenie binom(n,k) oznacza odpalenie tej funkcji
rekurencyjnie C(n,k)*2-1 razy. Dla n=52 i k=26 to 9.9*10^14 razy.
:-)

Lepszym, a nadal prostym wzorkiem jest np 12 stąd:
http://mathworld.wolfram.com/BinomialCoefficient.htm
l
C(n; k+1) = ( C(n; k) * (n-k) ) / (k+1)
plus C(n;0)=1 oczywiście.


nawiązując do oryginalnego pytania:
Piotrne wykorzystał tutaj postać liczb. Nie zawsze się
tak da, Ale nawet, jeśli nasze liczby sa losowe nie wszytko
stracone, nadal możemy zbudować doskonałą funkcję haszującą,
kosztem oczywiście pamięci.

Date: Thu, 7 Mar 2013 19:10:04 -0800 (PST)
Message-ID: <3...@g...c
om>
Subject: w poszukiwaniu funkcji hash
i hasełko perfect hash.

Można też brutalniej. Zapisać wszystkie liczby 'pięciobinarne',
posortować, a potem indeksu szukać binarnie. Obstawiam jednak,
że wzorek będzie szybszy.

pzdr
bartekltg