[so] [SO] [Tema1] General questions

[Adrian Dobrescu]

Mie mi se pare mai natural sa aloci alte bucket-uri și consider că adăugarea la sfârșitul listei nu își are rostul. Motive:
- Oricum hash-ul se redimensionează. Îl dublezi și creezi noi buckets sau îl înjumătățești și eliberezi memorie.
- Ca să folosești aceeași zonă de memorie, să zicem că adaugi la sfârșitul unui nou bucket. Trebuie să îl realoci. Să îl mărești. Trebuie să reții un index unde se termina vechea lista de cuvinte din acel bucket, pentru că va urma să fie parcurs. Apoi, când îi vei redistribui, va trebui să ștergi elementele de la începutul listei, deci să faci deplasări, eventual să eliberezi memorie în surplus.
- Nu văd de ce nu e mai eficient din majoritatea aspectelor să aloci o alte liste de cuvinte, și după terminarea procesului de redistribuire, free(vechiul bucket) și modifici pointerul cu cel nou.

--- On Wed, 23/2/11, Victor Carbune <victor.carbune at gmail.com> wrote:

From: Victor Carbune <victor.carbune at gmail.com>
Subject: Re: [so] [SO] [Tema1] General questions
To: "Sisteme de Operare" <so at cursuri.cs.pub.ro>
Date: Wednesday, 23 February, 2011, 10:57

Salut,

>>> 2011/2/22 Laura Vasilescu <vasilescu.laura at gmail.com>:
>>> > Tot oarecum de acest aspect:
>>> > La redistribuire o să începem parcurgerea de sus în jos (de la bucket
>>> > 0) și o să readăugăm cuvintele conform noilor valori hash calculate.
>>> > Ce se întâmplă atunci când hash-ul vechi și hash-ul nou sunt identice?
>>> > 1) cuvântul rămâne pe loc
>>> > 2) cuvântul este șters din poziția actuală și adăugat la sfârșitul
>>> > listei?
>>>
>>> Varianta 2, însă îl rog pe Ștefan să confirme.
Care e argumentul pentru această operație?

Mi se pare că doar adaugă complexitate inutilă (dacă e în bucket-ul
care trebuie, de ce l-aș mai muta la sfârșitul listei?).

> Salut,
>
> La operatiile de resize sunt parcurse toate bucketurile in ordine si
> cuvintele sunt adaugate in noul hash in ordinea in care sunt intalnite
> in vechiul hash. Nu trebuie pastrate timestampuri.

Eu bănuiesc că trebuie să refolosim memoria alocată în hash, şi nu să
alocăm un "nou hash".

Victor
_______________________________________________
http://elf.cs.pub.ro/so/wiki/resurse/lista-discutii


      
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cursuri.cs.pub.ro/pipermail/so/attachments/20110223/e1c5b883/attachment.htm>