Imprimă pagina - Lamuriri articol hashing

Titlul: Lamuriri articol hashing
Scris de: Cristian Strat din Ianuarie 16, 2007, 14:42:34

http://infoarena.ro/hashing

de ce O(lg(lg(n)) ?

ps: revin cu detalii :)

Titlul: Raspuns: Lamuriri articol hashinh
Scris de: Mircea Pasoi din Ianuarie 16, 2007, 22:22:30

Se scrie "hashing" :) Din articolul scris de Mihai Patrascu:

Abordarea clasica:
* func?ii euristice de hashing
* rezolvarea coliziunilor prin inlantuire sau adresare deschisa
* daca functia de hash ar fi perfect random, lungimea medie pt cea mai lunga lista inlantuita este O(lgN/lglgN)

O solu?ie practic?:
* avem dou? func?ii hash ?i dou? tabele în care rezolv?m coliziunile prin înl?n?uire
* când inser?m un element, îl ad?ug?m la tabela în care intr? într-un lan? mai scurt
* c?utarea se face în amândou? tabelele în loca?iile corespunz?toare
* lungimea medie a lan?ului maxim este O(lglgN)
* dac? men?inem lan?urile care arbori echilibra?i avem opera?ii în O(lglglgN)

Titlul: Raspuns: Lamuriri articol hashing
Scris de: Cristian Strat din Ianuarie 17, 2007, 21:29:55

Si de unde ies logaritmii astia?

Daca functia de hash e perfecta, nu ar trebui sa avem N/M lungime medie de lant?
Daca faci functie dubla de hash si cauti in ambele parti, statistic nu e acelasi lucru ca si cum ai avea un singur lant mai mare?

Titlul: Raspuns: Lamuriri articol hashing
Scris de: Mircea Pasoi din Ianuarie 18, 2007, 00:09:16

Nu, nu e acelasi lucru fiindca functiile de hash sunt diferite.

Titlul: Raspuns: Lamuriri articol hashing
Scris de: Cosmin Negruseri din Februarie 05, 2007, 01:21:44

O(log log n) e numaru maxim de chestii din cel mai mare bucket. E O(1) in cazul mediu da te intereseaza ca si cazu naspa sa nu fie asa naspa. Parca in cazul normal bucketu maxim are O(log n), da nu mai stiu exact.

Titlul: RÄƒspuns: Lamuriri articol hashing
Scris de: Mircea Dima din Octombrie 20, 2007, 18:13:17

Eu am folosit un hash... destul de interesant si performant... Acum nu stiu cat de corect e... desi la problema loto (singura problema la care
am testat metoda) am luat 100.

fac asa:

Cod:

#define maxn 128123
#define maxlog 17

int H[maxn][maxlog];

inline void insert(int v) 
{
  H[v%maxn][v%maxlog]=v;
}

inline int find(int v)
{
  if(H[v%maxn][v%maxlog]==v)return 1;
  return 0;
}

inline void del(int v)  
{
  H[v%maxn][v%maxlog]=0;
}

Cele 3 operatii au complexitate O(1)
Daca stiti vreo problema la care nu functioneaza metoda asta va rog sa-mi spuneti!

Titlul: RÄƒspuns: Lamuriri articol hashing
Scris de: Cosmin Negruseri din Octombrie 20, 2007, 22:03:05

Mircea, mai sus era vorba de niste hashuri mai jmechere care merg mai rapid. In solutiile clasice si in solutia discutata de noi, complexitatea operatiilor in cazul mediu e O(1), dar noi discutam despre altceva. Este un articol care prezinta hashurile astea pe site si vorbeam de marimea medie a galetii celei mai umplute in acela hashuri.

Titlul: RÄƒspuns: Lamuriri articol hashing
Scris de: Mircea Dima din Octombrie 20, 2007, 22:08:54

Da am inteles ca vorbiti despre double hash... cand ai H1[maxn] si H2[maxn] si cand introduci un element, il pui in lista cu elemente mai putine... si am testat asta... dar sursa care am pus-o eu ruleaza de 3 ori mai repede...
pentru n=1 000 000 de insert si find a rulat in 0,1s pe un P4 3Ghz

Titlul: RÄƒspuns: Lamuriri articol hashing
Scris de: Cosmin Negruseri din Octombrie 20, 2007, 22:27:27

Ok, m-am uitat acum si la cod, si nu vad sa tratezi in vreun fel coliziunile, asa ca s-ar putea sa fie mai greu sa folosesti aceiasi metoda in toate problemele.

Titlul: RÄƒspuns: Lamuriri articol hashing
Scris de: Stefan Istrate din Februarie 20, 2009, 02:33:16

Discutia poate continua in topicul destinat acestui articol: http://infoarena.ro/forum/index.php?topic=3687.0

infoarena

infoarena - concursuri, probleme, evaluator, articole => Articole => Subiect creat de: Cristian Strat din Ianuarie 16, 2007, 14:42:34