Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Tabele hash - scurta prezentare  (Citit de 4722 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
stef2n
Nu mai tace
*****

Karma: 218
Deconectat Deconectat

Mesaje: 641



Vezi Profilul
« : Februarie 20, 2009, 02:32:01 »

Comentarii la articolul Tabele hash - scurta prezentare
Memorat

Exista 10 categorii de oameni: cei care inteleg sistemul binar si cei care nu il inteleg.
nash
De-al casei
***

Karma: 0
Deconectat Deconectat

Mesaje: 109



Vezi Profilul
« Răspunde #1 : Iunie 02, 2010, 08:45:32 »

"Aceasta metoda este o imbunatatire a punctului anterior: pentru ca lungimea unui lant este cel mult lg(N), putem sa folosim, in loc de liste inlantuite, vectori alocati dinamic de lungime lg(N) - sau lg(N) + 3, ca sa fim siguri Smile. Scapam astfel de lucrul cu pointerii."

Cum arati ca lungimea unui lant este logN ? Dupa mintea mea daca ai o dispersie perfecta ai |U| / N pe fiecare lant... pentru cazul in care ai toate elementele universului in hash .
Memorat
blasterz
Nu mai tace
*****

Karma: 92
Deconectat Deconectat

Mesaje: 255



Vezi Profilul
« Răspunde #2 : Iunie 02, 2010, 09:08:45 »

"In fiecare locatie din hash tinem o lista inlantuita; astfel, la oricare din cele 3 operatii se va parcurge toata lista. Pe un caz pur teoretic, toate cele N elemente ar putea fi repartizate in aceeasi locatie, insa pe cazuri practice lungimea medie a celui mai lung lant este de lg(N)."



Memorat
marcelcodrea
Nu mai tace
*****

Karma: 173
Deconectat Deconectat

Mesaje: 217



Vezi Profilul
« Răspunde #3 : Iunie 02, 2010, 09:50:52 »

Cred că termenul de double hashing poate induce în eroare cititorul. Double hashing e o metodă veche(apare şi în Introducere în algoritmi) de rezolvare a coliziunilor folosită în tabelele cu adresare deschisă, de fapt cea mai bună metodă pentru că evită atât formarea "grupărilor" primare cât şi a "grupărilor" secundare(primary& secondary clustering). Această metodă de rezolvare a coliziunilor e mai bună decât linear probing şi quadratic probing pentru că în determinarea secvenţei de verificare se foloseşte de două funcţii de dispersie(de acolo venindu-i şi numele).

Ar trebui să luăm legătura cu Mihai Pătraşcu, un guru al acestui domeniu, să vedem cum s-a sedimentat tehnica lui de "double hashing" în literatura de specialitate, pentru că double hashing e cu totul altceva decât ce se descrie în articol.
Memorat
nash
De-al casei
***

Karma: 0
Deconectat Deconectat

Mesaje: 109



Vezi Profilul
« Răspunde #4 : Iunie 02, 2010, 12:58:11 »

Ok... nu ma intereseaza niste afirmatii... ma intereseaza cum arati ca asa este.
"pe cazuri practice lungimea medie a celui mai lung lant este de lg(N)." Mediu intre ce ? E cel putin ciudat sa consideri mediu intre ceva constant o(1) memorie pe lant.. si ceva liniar ca fiind ceva logaritmic. Oricum... ce inseamna cazuri practice ? Adica... care este raportul dintre universul cheilor si numarul de liste din tabela ?

O incercare de sustinere a unei afirmatii printr-o mini demonstratie ar fi benefica. Smile
Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #5 : Iunie 03, 2010, 12:00:22 »

Citat
Primul pas in a rezolva problema memoriei este de a folosi O(N) memorie in loc de O(|U|), unde N este numarul de elemente adaugate in hash
Deci daca ai avea o functie de dispersie perfecta ai avea 1 element pe fiecare lant.

Acuma sa luam pentru numere intregi functia h(x) = x % M.
Acuma trebuie sa luam toate sirurile de N numere din U, sa aflam lungimea celui mai lung lant pentru fiecare si apoi sa impartim la numarul total de lanturi.

Vom defini ~ ca fiind o relatie de echivalenta pe sirurile astea astfel:
S1 ~ S2 daca si numai daca S1[ i] = S2[ i] (modulo M) (E clar ca lungimea celui mai lung lant atat pentru S1 cat si pentru S2 e aceeasi).

De asemenea e destul de usor de vazut ca toate clasele de echivalenta au acelasi nr de elemente (E destul de usor de gasit o bijectie de la o clasa la alta, daca nu reusesti zi-mi si o sa explic mai detaliat).

Astfel problema s-a redus la a lua toate sirurile cu N elemente mai mici decat un nr M, a calcula lungimea celui mai lung lant pentru fiecare, iar suma impartita la M^N (numarul total de siruri cu N elemente mai mici decat M) sa dea aproximativ log N.

Eh si aici se cam opresc ideile mele in ceea ce privesc demonstratia. Am incercat sa gasesc o formula pentru L(x) = numarul de siruri cu N elemente mai mici decat M in care fiecare element apare de cel mult X ori dar nu am reusit. Daca are vreo cineva o idee sa continue de aici. Oricum cred ca cam asta e ideea de demonstratie.


Memorat
nash
De-al casei
***

Karma: 0
Deconectat Deconectat

Mesaje: 109



Vezi Profilul
« Răspunde #6 : Iunie 04, 2010, 16:20:15 »

La relatia de echivalenta ar mai trebui adaugate si toate sirurile permutari ale lui S2 , nu ?
adica...  Si ~ Sj <=> |Hash[p]| pentru sirul "i" = |Hash[p]| pentru sirul "j"   ( unde  0 <= p < M-1 )
// Am putea sa definim si sa luma siruri echivalente inclusiv pe acelea care pentru care lungimile lanturilor din tabela ( Hash ) sunt egale pentru o anumita permutare a acestora . Cred insa ca acesta clauza duce demonstratia pe un drum mai greoi.

Plecand de la ideea ta : Este necesar si suficient sa luam numai sirurile de lungime N a caror elemente se gasesec in interiorul valorilor 0 M-1 ca si multime de reprezentanti a numerelor pentru generarea multimii factor data de relatia de echivalenta mai sus precizata .

Numarul total de de echivalente ( marimea multimii cat ) este de Nr[N][M] care reprezinta numarul de a imparti cele N numere in M clase fiecare.
De aici rezulta ca fiecare numar poate fi la un moment dat in una din cele M clase intr-un sir de N elemente  adica N^M posibilitati.

De aici s-ar putea face inca o factorizare a acestor clase de echivalente dupa lungimea celui mai mare lant din Hash[p] . In acesta situatie avem clar "N" clase in care se vor imparti cele N^M clase . Si trebuie vazut care dintre aceste clase are cele mai multe elemente. Intuiesc ca cele mai multe se regasesc undeva pe la o clasa care face ca lungimea sa fie logN . [desi ciudat, pentru ca in cel mai bun caz lungimea acestuia ar trebui sa fie N/M atunci cand functia de dispersie isi face treba bine, singura logica ar fi ca in urma verificarii sa se arate ca de fapt in majoritatea claselor de echivalenta lungimea majoritatii lanturilor din hash sa fie suficient de mica si sa se arate ca acesta ar fi ~ logN si ca sa fie posibil asa ceva existand si lanturi mai mari dar care sa nu fie extrem de multe in comparatie cu cele mici] ( Ar trebui sa fac un program sa vad dispersia ... uniforma a elementelor ) . Ar fi interesant insa sa si demonstram asta . Smile


Ceea ce ma intriga este faptul ca in gandirea mea. Numarul de liste din tabela de dispersie adica "M" are o importanta in a valida complexitatea pe cand cele prezentate in articol singurul factor importantant era secventa de lumgime N care era adaugata in Hash . Smile . Evident, se poate considera ca M este un factor constant in creerea tabelei de dispersie initiale si N nu este dar totusi in cele mai multe tabele de dispersie acesta este foarte mare si este destul de important pentru a creste performantele hash-ului .

Citat
De asemenea e destul de usor de vazut ca toate clasele de echivalenta au acelasi nr de elemente .

Nu sunt chiar de aceeasi parere. Detaliaza te rog Smile
« Ultima modificare: Iunie 04, 2010, 18:30:10 de către nash mit » Memorat
nash
De-al casei
***

Karma: 0
Deconectat Deconectat

Mesaje: 109



Vezi Profilul
« Răspunde #7 : Iunie 09, 2010, 23:28:24 »

Citat
Probabil articolul este un pic confuz. Dacă funcția de hash este
complet aleatoare, cea mai lungă listă este de mărime Theta(lg n /
lglg n), deși lista medie este evident de mărime O(1).

Pentru a demonstra rezultatul de lg n / lglg n, se folosesc Chernoff
bounds. Am scris un pic despre asta la mine pe blog:
http://infoweekly.blogspot.com/2010/01/moments.html

Dacă funcția de hash nu e complet aleatoare (cum se întâmplă în
realitate), lungime celei mai lungi liste poate să fie mult mai
proastă...

-mihai

>
> Salut !
>   Citeam zilele astea un articol pe Infoarena si acolo se facea o precizare conform careia :
> "In fiecare locatie din hash tinem o lista inlantuita; astfel, la oricare din cele 3 operatii se va parcurge toata lista. Pe un caz pur teoretic, toate cele N elemente ar putea fi repartizate in aceeasi locatie, insa pe cazuri practice lungimea medie a celui mai lung lant este de lg(N)."
> Am incercat sa vad cum se poate asa... am ajuns la un rezultat dar nu la finalul demonstratiei. Stiu ca acest rezultat l-ati prezentat in mai multe confereinte si as fi curios daca ati putea sa ma ajutati sa inteleg. Ati putea sa imi trimiteti prezentarea cu demonstratia ? Sunt foarte curios cum s-a ajuns la acest rezultat Smile .
>  Multumesc anticipat !
>Horea
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines