[so] [SO] [Tema1] General questions

[Alexandra Sava]

2011/2/23 Stefan Munteanu <stef8803 at gmail.com>:
> 2011/2/23 Victor Carbune <victor.carbune at gmail.com>:
>> Salut,
>>
>> 2011/2/23 Laura Vasilescu <vasilescu.laura at gmail.com>:
>>> 2011/2/23 Daniel Baluta <daniel.baluta at gmail.com>:
>>>> 2011/2/23 Victor Carbune <victor.carbune at gmail.com>:
>>>>> Eu bănuiesc că trebuie să refolosim memoria alocată în hash, şi nu să
>>>>> alocăm un "nou hash".
>>>>
>>>> Hmm, depinde de implementare aici. Dacă ai folosit liste pentru buckets
>>>> atunci clar refolosești memoria.
>>>
>>> Problema cu varianta propusă de Ștefan în care dacă hash-ul este
>>> identic, acesta trebuie scos și readăugat la sfârșitul listei e că în
>>> loc să nu faci nimic, faci o operație de ștergere (care e O(1) pentru
>>> varianta cu liste pentru buckets) și o adăugare (care poate fi ceva
>>> mai costisitoare, întrucât trebuie să inserezi la sfârșitul listei).
>>> Desigur, s-ar putea implementa o funcție diferită pentru adăugarea
>>> elementelor în caz de resize (reținându-se un pointer către sfârșitul
>>> listei), dar mi se pare ineficient din punct de vedere al
>>> modularizării. Funcția de adăugare în caz de resize trebuie să fie
>>> aceeași cu cea pentru adăugarea unui element nou în hashTable.
>>
>> Asta e și nelămurirea mea.
>> Ambele variante sunt deterministe și pot fi testate, însă una dintre
>> ele e ineficientă.
>
> Salut,
>
> Sorry de rapunsurile tarzii, dar momentan sunt pe alt fus orar.
> Here it  goes:
> Comportamentul dorit la resize este unul echivalent cu urmatorul: se
> creeaza un nou hash, se itereaza prin bucketurile din vechiul hash si
> se adauga in noul hash.
> Modul acesta de rezolvare este unul simplist, care poate fi facut de
> toata lumea fara probleme. Este interesanta si varianta lui Victor si
> poate fi aplicata si fara probleme, doar ca trebuie ajustata astfel
> incat sa aiba aceleasi rezultate ca cealalta.
> In final, ambele solutii au aceeasi complexitate, dar una se comporta
> un pic mai bine.
> Nu va sugerez nicio rezolvare anume, cu cat mai multe idei cu atat mai
> bine :) Singura conditie este sa treaca testele.
>
> Stefan
>
> PS Hashtable-ul din java se comporta la fel (ceea ce e logic, incat
> acolo nu exista realloc)
> _______________________________________________
> http://elf.cs.pub.ro/so/wiki/resurse/lista-discutii

Salut!

Am niste nelamuriri legate de terminarea programului. Pe Linux, daca
se citeste din fisier, este clara treaba cand se termina (se
detecteaza EOF si gata). Cand se citeste de la stdin, in momentul cand
se trimite comanda ctrl+d, aceasta este "interceptata" de program si
se termina (asa am considerat eu terminarea, altfel nu vad cum).
Pe windows insa acestea nu mai merg (cel putin nu cea cu "crtl+d"),
deci nu este corect deoarece sursa trebuie sa mearga pe ambele
platforme. Cum ar trebui interpretata terminarea (care implica
eliberarea intregii memorii) cand se citeste de la stdin?



Alexandra