Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Lamuriri articol hashing  (Citit de 3045 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
wickedman
Echipa infoarena
Nu mai tace
*****

Karma: 227
Deconectat Deconectat

Mesaje: 670



Vezi Profilul WWW
« : Ianuarie 16, 2007, 14:42:34 »

http://infoarena.ro/hashing

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

ps: revin cu detalii Smile
« Ultima modificare: Ianuarie 17, 2007, 21:25:47 de către Cristian George Strat » Memorat
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #1 : Ianuarie 16, 2007, 22:22:30 »

Memorat
wickedman
Echipa infoarena
Nu mai tace
*****

Karma: 227
Deconectat Deconectat

Mesaje: 670



Vezi Profilul WWW
« Răspunde #2 : 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?
Memorat
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #3 : Ianuarie 18, 2007, 00:09:16 »

Nu, nu e acelasi lucru fiindca functiile de hash sunt diferite.
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #4 : 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.
Memorat
blasterz
Nu mai tace
*****

Karma: 92
Deconectat Deconectat

Mesaje: 255



Vezi Profilul
« Răspunde #5 : 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!
« Ultima modificare: Octombrie 20, 2007, 18:37:35 de către Mircea Dima » Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #6 : 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.
Memorat
blasterz
Nu mai tace
*****

Karma: 92
Deconectat Deconectat

Mesaje: 255



Vezi Profilul
« Răspunde #7 : 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
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #8 : 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.
Memorat
stef2n
Nu mai tace
*****

Karma: 218
Deconectat Deconectat

Mesaje: 641



Vezi Profilul
« Răspunde #9 : Februarie 20, 2009, 02:33:16 »

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

Exista 10 categorii de oameni: cei care inteleg sistemul binar si cei care nu il inteleg.
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

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