[so] [SO] [Tema1] General questions
Ghitulete Razvan
razvan.ghitulete at gmail.com
Wed Feb 23 11:55:29 EET 2011
Eu sunt bagat complet in ceata de ultimele reply-uri.
Din cate am inteles eu din ce am citit si din implementarea proprie, Victor
in momentul in care face resize(sa zicem double) face prima data un realloc
pe vector-ul de buckets(sper sa nu ma insel). In continuare redistribuie
doar cuvintele care nu corespund dupa schimbarea dimensiunii hash-ului. Spre
deosebire de cealalta varianta posibila, care presupune crearea unui nou
hash de la 0, care am inteles ca ar fi varianta propusa de echipa de SO(yet
again nu sunt foarte sigur de asta, pentru ca sunt foarte ambigue
explicatiile).
Deci mai la obiect, cum procedam in cazul resize?
1) realocam hash-ul initial cu realoc, si dupa doar il "corectam" unde e
"gresit" , adica in cazul in care in bucket-ul x gasim un cuvant care
corespunde lui x il lasam unde e si mergem mai departe, daca in schimb dupa
redistribuire corespunde lui y, il stergem din x(cu remove) si il adaugam in
y.
2) alocam un hash nou, il parcurgem pe cel vechi incepand de la bucket-ul 0,
adaugam in cel nou cuvintele, si il stergem pe cel vechi.
Dpmdv, ambele variante sunt deterministe, deci nu cred ca se poate argumenta
acest lucru impotriva oricareia dintre variante, asadar in esenta totul se
reduce la intrebarea:
Cum e implementata solutia oficiala?
--
Razvan Ghitulete
Universitatea Politehnica Bucuresti
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cursuri.cs.pub.ro/pipermail/so/attachments/20110223/5b048a43/attachment.htm>
More information about the so
mailing list