David Klasinc wrote:
>
> On Sun, Jul 30, 2000 at 03:42:43PM -0700, Blaz Antonic wrote:
> > Moj predlog: najdi eno razumno mero tolerance, kjer si napake se
> > pripravljen dopuscati. Vec napak kot lahko preneses, ves informacije
> > lahko zavrzes. Najbolj extremen primer je preverjanje paritete, kjer
> > imas za "checksum" samo en bit.
>
> Problem je v tem, da bi rad zadevo imel brez napak... :)))
>
> Anyway, od openSSH sem si sposodil crc32.c/h (btw, openssh ima tudi
> izposojenega) in zaenkrat mi ustreza...
>
> Iskanje po arrayu z takimi checksumi je priblizno 4x hitrejse kot po arrayu
> polnem stringov.
>
> V bistvu sem nasel to kar sem hotel.
Ne wem kok si podkovan iz algoritmov, ampak zdi se da je tisto kar ti
isces je dobra hash funkcija.. in nasploh je odgovor na tvoje vprasanje
hash tabela oziroma po slovensko razprseni seznam... hmmm
ce te zanima je na to temo ogromno napisanega ker so hash tabele zelo
pametna zadeva kadar imas veliko podatkov...
Ce hashas stringe sem preprican da ti bo genericini preizkusen hash
pomagal bolj kot crc ...
preprosto sta to dve razlicni stvari... v bistvu tudi delno podobni
ampak vseen razlicni
V glavnem, ce je tole kar imas 4x hitreje naj povem da je namen hashanja
iz linerane zahtevnosti cas iskanja po kljucu spravljen na (skoraj)
konstantno zahtevnost (odvisno od tega koliko spomina si pripravljen
zrtvovati)
Aja.. hiter recept za hash funkcije dobis v sedgewicku, malo bolj so
detajlno obdleane v introduction to algorithms, nedvomno pa so tocno
temu posvecene tudi cele knjige ...
ce nic ne najdes ti lahko izbrskam kaj na netu...
Lep Pozdrav
Andraz Tori
