On Mon, 31 Jul 2000, David Klasinc wrote:
>
> On Sun, Jul 30, 2000 at 08:44:47PM -0700, Tori Andraz wrote:
>
> > Ne wem kok si podkovan iz algoritmov, ampak zdi se da je tisto kar ti
>
> Nic... :P
Res priporocam da si preberes kaj... saj se vse da z veliko
iznajdljivosti, vendar je vseeno lazji problem ce vsaj ves kam pogledat
kaksne so bile ze pretekle resitve tvojega problema
>
> > isces je dobra hash funkcija.. in nasploh je odgovor na tvoje vprasanje
> > hash tabela oziroma po slovensko razprseni seznam... hmmm
>
> Ja, s hashi se nisem delal, sem pa ze razmisljal o tem, da bi vse skupaj dal
> v hash tabelo.
>
> Trenutno mi je to kar imam dovolj. Ce bo potreba bom naredil se hash
> implementacijo. Vseakor pa CRC modela ne mislim ven spustiti, primerjanje
> stevil je se vedno manj zahtevno kot primerjanje stringov.
Sicer ne wem tocnih razlik,ampak crc je bil zelo premisljeno izdelan za
eno stvar - assignanje razlicnih vrednosti za enako dolge bloke podatkov,
vazno je bilo da se majhne razlinke nujno vedno pokazejo v crc kodi
Torej crc je optimiziran na to, da tudi nekaj razlik v celem bloku ne
morejo spet dati iste crc vrednosti (pri recimo party checku ze dve
razliki zadostujeta da je napaka nezaznavna)
Kako se pa crc obnese pri radikalno razlicnih podatkih celo razlicnih
dolzin je pa vprasanje na katerega ne wem odgovora (tu je vprasanje koliko
collisnov se pojavlja)
Hash je tudi namenjen temu da ne primerjas celih stringov ampak le cifre
(ponavadi)
(a ima kdo boljse podatke o razlikah med cimbolj general purpose hash
funkcijami in crc16 in crc32 ?
> Problem nastane, da bom vcasih imel stringe v tabeli dolge tudi do 4k ali pa
> vec... :) To je pa ze prevec tudi za hash tabele.
to se naredi tako da imas v eni tabeli hashe in indexe v drugi pa
podatkeTo ni nic prevec za hash tabele... (dolzina kljucev nebi smela
vplivat, razen ce mislis cas izracunavanja hash vrednosti, ki pa je
(domnevam) da tu zanemarljiv... sicer pa primerljiv z crc)
> > iz linerane zahtevnosti cas iskanja po kljucu spravljen na (skoraj)
> > konstantno zahtevnost (odvisno od tega koliko spomina si pripravljen
> > zrtvovati)
>
> Spomin ni problem.. Vsaj trenutno ne... :)
Ce uporabljas C++ si na vsak nacin poglej STL (standard template library),
prihranjeno ti b o mnogo uric mucenja z vsemi osnovnimi podatkovnimi
strukturami in algoritmi
> > 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 ...
>
> Si bom malo pogledal...
Smart:)
Lep Pozdrav
Andraz Tori
