On Saturday, December 5, 2015 at 12:45:15 AM UTC+1, bartekltg wrote:
> On 04.12.2015 15:04, Borneq wrote:
> > Każdy zasób określony jest przez numer z zakresu <a,b), bez miany
> > ogólności możemy przyjąć że zakres jest <0,n) gdzie n=b-a.
> > N jest duże, np. dwa miliony, więc nie ma obaw że zabraknie zasobów, n
> > to ilość ile może być zasobów JEDNOCZEŚNIE. Ale gdy zwolnimy jakiś
> > zasób, jego numer może zostać przydzielony znowu.
> > Choć duże n, to może się skończyć, gdy będziemy przydzielać, zwalniać i
> > zwiększać k.
> > Są dwie strategie: albo przydzielać zawsze najniższy wolny numer, albo
> > cały czas inkrementować k, przydzielać najwyższy numer, aż gdy k
> > osiągnie n, wtedy zawinie się od początku. Jak jest lepiej?
> > Jaka struktura? Czy trzymać listę raczej wolnych czy raczej zajętych
> > numerów? Gdy będzie mało wykorzystane, oszczędniej trzymać raczej listę
> > zajętych, ale listę wolnych może lepiej szukać?
>
>
> Rozumoem, że nie chodzi o obiekt w pamięci. Bo jeśli tak,
> to można to zrobić jeszcze sprytniej.
No właśnie, dokładnie nie wiadomo do czego to jest potrzebne i trudno
coś doradzić. Ja zrozumiałem, nie wiedzieć czemu, że trzeba podać
najmniejszy wolny i bym zasugerował stertę. Może zrozumiałem tak
dlatego, że nie zdecydował się na ciągłe inkrementowanie long long.
Potem Broneq pisał coś o bezpośrednim programowaniu Xa, więc
najlepsze co można zrobić, to zajrzeć do przykładów - tam zapewne
znajdują się rozwiązania dedykowane i obsługujące różne przypadki
które ciężko z góry przewidzieć, i które mogą się pojawić. Struktura
musi być dostosowana do wszystkich przypadków a nie tylko do
podawania unikalnego id.



> Pomysł wstępny:
> Stos wolnych. Gdy wątek pobiera zasób, zabier go jednocześnie
> ze stosu. Gdy zwalnie, wsadza numer na samą górę.
>
> Wszystko w czasie stałym.
Jeśli jest potrzebny dowolny dostępny, to stos lub kolejka wydają się
najlepsze. Jeśli jakiś dowolny numer, to najlepiej:
get( id_thread ) {
static long long res[max] = {0,1,2,3,4...max-1};
return res[id_thread] += max;
}



> Modyfikacja: kolejka fifo w cyklicznym buforze (wielkosći N+1).
> Pobierasz z jednej strony, oddajesz po drugiej.
>
> Ale nie zawsze warto, jeśli ostatnio używane zasób jest
> z jakiś posobów lepszy (co siedzi w buforach) to pierwsza
> wersja lepsza.
>
>
> No, chyba, że zasobem są stałej wielkośći fragmenty pamięći
> (obiekty po kilka(set) bajtów). Wtedy robie się to inaczej.
Zależy, często w takich przypadkach stos i kolejka też się nadają.



Pozdrawiam