Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #28146 > unrolled thread

Struktura do przydzielania numerków

Back to article view | Back to pl.comp.programming

Contents

  Struktura do przydzielania numerków Borneq <borneq@antyspam.hidden.pl> - 2015-12-04 15:04 +0100
    Re: Struktura do przydzielania numerków Adam M <amorawski@magna-power.com> - 2015-12-04 06:16 -0800
    Re: Struktura do przydzielania numerków Borneq <borneq@antyspam.hidden.pl> - 2015-12-04 15:19 +0100
      Re: Struktura do przydzielania numerków Adam M <amorawski@magna-power.com> - 2015-12-04 06:51 -0800
        Re: Struktura do przydzielania numerków Borneq <borneq@antyspam.hidden.pl> - 2015-12-04 16:17 +0100
          Re: Struktura do przydzielania numerków Adam M <amorawski@magna-power.com> - 2015-12-04 11:10 -0800
            Re: Struktura do przydzielania numerków "M.M." <mmarszik@gmail.com> - 2015-12-04 11:17 -0800
            Re: Struktura do przydzielania numerków Borneq <borneq@antyspam.hidden.pl> - 2015-12-04 23:30 +0100
              Re: Struktura do przydzielania numerków bartekltg <bartekltg@gmail.com> - 2015-12-05 00:49 +0100
                Re: Struktura do przydzielania numerków Borneq <borneq@antyspam.hidden.pl> - 2015-12-05 09:37 +0100
                  Re: Struktura do przydzielania numerków bartekltg <bartekltg@gmail.com> - 2015-12-06 17:26 +0100
                    Re: Struktura do przydzielania numerków Borneq <borneq@antyspam.hidden.pl> - 2015-12-06 19:47 +0100
                      Re: Struktura do przydzielania numerków bartekltg <bartekltg@gmail.com> - 2015-12-07 03:09 +0100
                        Re: Struktura do przydzielania numerków Borneq <borneq@antyspam.hidden.pl> - 2015-12-07 10:31 +0100
                    Re: Struktura do przydzielania numerków Borneq <borneq@antyspam.hidden.pl> - 2015-12-07 01:05 +0100
                      Re: Struktura do przydzielania numerków bartekltg <bartekltg@gmail.com> - 2015-12-07 03:13 +0100
    Re: Struktura do przydzielania numerków "M.M." <mmarszik@gmail.com> - 2015-12-04 08:21 -0800
    Re: Struktura do przydzielania numerków Adam Klobukowski <adamklobukowski@gmail.com> - 2015-12-04 08:31 -0800
      Re: Struktura do przydzielania numerków "M.M." <mmarszik@gmail.com> - 2015-12-04 09:13 -0800
      Re: Struktura do przydzielania numerków Adam M <amorawski@magna-power.com> - 2015-12-04 10:58 -0800
    Re: Struktura do przydzielania numerków bartekltg <bartekltg@gmail.com> - 2015-12-05 00:45 +0100
      Re: Struktura do przydzielania numerków "M.M." <mmarszik@gmail.com> - 2015-12-05 03:44 -0800
    Re: Struktura do przydzielania numerków Borneq <borneq@antyspam.hidden.pl> - 2015-12-06 10:12 +0100
      Re: Struktura do przydzielania numerków Borneq <borneq@antyspam.hidden.pl> - 2015-12-06 10:21 +0100
      Re: Struktura do przydzielania numerków Borneq <borneq@antyspam.hidden.pl> - 2015-12-06 11:29 +0100

Page 1 of 2  [1] 2  Next page →

#28146 — Struktura do przydzielania numerków

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ć?
Dodatkowo potrzebne jeszcze mutexy, aby nie przydzielić dwa razy tego 
samego numeru przy pracy na wątkach.
Jaka struktura i algorytm wydajnie wyszuka wolny numer?

[toc] | [next] | [standalone]

#28147

Do trzymania informacji o zajetych numerach (zasobach) nie potrzeba zadnej listy - wystarczy int lub long int. Kazdy bit identyfikuje zajety zasob. Binarne sprawdzanie zajetosci bitu. Jesli system ma bardzo malo pamieci trzeba sobie jakos radzic - lista zjadla by cale zasoby ;-)

Do wyszukiwania wolnego miejsca - wyszukiwanie polowkowe i rolowanie bitow w prawo lub lewo jak kto woli ;-)

On Friday, December 4, 2015 at 9:04:17 AM UTC-5, 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ć?
> Dodatkowo potrzebne jeszcze mutexy, aby nie przydzielić dwa razy tego 
> samego numeru przy pracy na wątkach.
> Jaka struktura i algorytm wydajnie wyszuka wolny numer?

[toc] | [prev] | [next] | [standalone]

#28148

W dniu 2015-12-04 o 15:04, Borneq pisze:
> Jaka struktura i algorytm wydajnie wyszuka wolny numer?

Nasuwa się struktura bitowa, choć dużo numerów, to tylko po bicie na 
jeden. Gdy dużo wolnego, to szybko znajdzie wolne, gdy prawie cała 
zajęta będzie musiał przeszukiwać tablicę aby znaleźć zero.
Może to zależeć od aktualnej liczy użytych:
- gdy mało użytych - wtedy lista użytych
- gdy dużo,ale mniej niż np. połowa - tablica bitowo
- gdy więcej niż połowa - lista wolnych

[toc] | [prev] | [next] | [standalone]

#28149

Dlaczego struktura bitowa raczej unia struktory bitowej z odpowiadajacym unsigned int lub unsigned long - to jest standardowe rozwiazanie np przy programowaniu MCUs
Aby znalezc wolny bit niezaleznie od zajetosci potrzeba cztery podzialy 32, 16, 8, 4 i 4 rolowania w najgorszym przypadku przy 32 bit int i 5 podzialow  i 4 rolowania przy 64 bit long.

On Friday, December 4, 2015 at 9:19:18 AM UTC-5, Borneq wrote:
> W dniu 2015-12-04 o 15:04, Borneq pisze:
> > Jaka struktura i algorytm wydajnie wyszuka wolny numer?
> 
> Nasuwa się struktura bitowa, choć dużo numerów, to tylko po bicie na 
> jeden. Gdy dużo wolnego, to szybko znajdzie wolne, gdy prawie cała 
> zajęta będzie musiał przeszukiwać tablicę aby znaleźć zero.
> Może to zależeć od aktualnej liczy użytych:
> - gdy mało użytych - wtedy lista użytych
> - gdy dużo,ale mniej niż np. połowa - tablica bitowo
> - gdy więcej niż połowa - lista wolnych

[toc] | [prev] | [next] | [standalone]

#28150

W dniu 2015-12-04 o 15:51, Adam M pisze:
> Dlaczego struktura bitowa raczej unia struktory bitowej z odpowiadajacym unsigned int lub unsigned long - to jest standardowe rozwiazanie np przy programowaniu MCUs
> Aby znalezc wolny bit niezaleznie od zajetosci potrzeba cztery podzialy 32, 16, 8, 4 i 4 rolowania w najgorszym przypadku przy 32 bit int i 5 podzialow  i 4 rolowania przy 64 bit long.

Jak wykonywać te podziały? zwykle przy połowie słowa liczy się tylko to 
młodsze.
czy będzie to tak a wewnątrz procedura inline szukaj_przesuwajac 
używająca << maksymalnie 4 razy?
uint32_t mask
if(mask)
{
   if (mask & 0x0000ffff) //16 młodszych
   {
     if (mask & 0x000000ff) //8 najmłodszych
     {
       if (mask & 0x0000000f) szukaj_przesuwajac
       else szukaj_przesuwajac
     }
     else
     {
       if (mask & 0x00000f00) szukaj_przesuwajac
       else szukaj_przesuwajac
     }
   }
   else
   {
     if (mask & 0x00ff0000) //8 najmłodszych
     {
       if (mask & 0x000f0000) szukaj_przesuwajac
       else szukaj_przesuwajac
     }
     else
     {
       if (mask & 0x0f000000) szukaj_przesuwajac
       else szukaj_przesuwajac
     }
   }
}

[toc] | [prev] | [next] | [standalone]

#28155

On Friday, December 4, 2015 at 10:17:02 AM UTC-5, Borneq wrote:
> W dniu 2015-12-04 o 15:51, Adam M pisze:
> > Dlaczego struktura bitowa raczej unia struktory bitowej z odpowiadajacym unsigned int lub unsigned long - to jest standardowe rozwiazanie np przy programowaniu MCUs
> > Aby znalezc wolny bit niezaleznie od zajetosci potrzeba cztery podzialy 32, 16, 8, 4 i 4 rolowania w najgorszym przypadku przy 32 bit int i 5 podzialow  i 4 rolowania przy 64 bit long.
> 
> Jak wykonywać te podziały? zwykle przy połowie słowa liczy się tylko to 
> młodsze.
> czy będzie to tak a wewnątrz procedura inline szukaj_przesuwajac 
> używająca << maksymalnie 4 razy?
> uint32_t mask
> if(mask)
> {
>    if (mask & 0x0000ffff) //16 młodszych
>    {
>      if (mask & 0x000000ff) //8 najmłodszych
>      {
>        if (mask & 0x0000000f) szukaj_przesuwajac
>        else szukaj_przesuwajac
>      }
>      else
>      {
>        if (mask & 0x00000f00) szukaj_przesuwajac
>        else szukaj_przesuwajac
>      }
>    }
>    else
>    {
>      if (mask & 0x00ff0000) //8 najmłodszych
>      {
>        if (mask & 0x000f0000) szukaj_przesuwajac
>        else szukaj_przesuwajac
>      }
>      else
>      {
>        if (mask & 0x0f000000) szukaj_przesuwajac
>        else szukaj_przesuwajac
>      }
>    }
> }

Tka przy okazji, z czystej ciekawosci sie pytam na jakim systemie to mam byc implementowane - czy to tylko teoretyczne dewagacje - za wyjatkiem duzych web-serwerow i baz danych obslugujacych bardzo duze firmy (w tym przypadku sa dobrze znane rozwiazania jak radzic sobie z problemem) ciezko mi wyobrazic sobie system ktory uruchamia miliony watkow - nie mowiac juz o milionach zadan.

[toc] | [prev] | [next] | [standalone]

#28156

On Friday, December 4, 2015 at 8:11:03 PM UTC+1, Adam M wrote:
> On Friday, December 4, 2015 at 10:17:02 AM UTC-5, Borneq wrote:
> > W dniu 2015-12-04 o 15:51, Adam M pisze:
> > > Dlaczego struktura bitowa raczej unia struktory bitowej z odpowiadajacym unsigned int lub unsigned long - to jest standardowe rozwiazanie np przy programowaniu MCUs
> > > Aby znalezc wolny bit niezaleznie od zajetosci potrzeba cztery podzialy 32, 16, 8, 4 i 4 rolowania w najgorszym przypadku przy 32 bit int i 5 podzialow  i 4 rolowania przy 64 bit long.
> > 
> > Jak wykonywać te podziały? zwykle przy połowie słowa liczy się tylko to 
> > młodsze.
> > czy będzie to tak a wewnątrz procedura inline szukaj_przesuwajac 
> > używająca << maksymalnie 4 razy?
> > uint32_t mask
> > if(mask)
> > {
> >    if (mask & 0x0000ffff) //16 młodszych
> >    {
> >      if (mask & 0x000000ff) //8 najmłodszych
> >      {
> >        if (mask & 0x0000000f) szukaj_przesuwajac
> >        else szukaj_przesuwajac
> >      }
> >      else
> >      {
> >        if (mask & 0x00000f00) szukaj_przesuwajac
> >        else szukaj_przesuwajac
> >      }
> >    }
> >    else
> >    {
> >      if (mask & 0x00ff0000) //8 najmłodszych
> >      {
> >        if (mask & 0x000f0000) szukaj_przesuwajac
> >        else szukaj_przesuwajac
> >      }
> >      else
> >      {
> >        if (mask & 0x0f000000) szukaj_przesuwajac
> >        else szukaj_przesuwajac
> >      }
> >    }
> > }
> 
> Tka przy okazji, z czystej ciekawosci sie pytam na jakim systemie to mam byc implementowane - czy to tylko teoretyczne dewagacje - za wyjatkiem duzych web-serwerow i baz danych obslugujacych bardzo duze firmy (w tym przypadku sa dobrze znane rozwiazania jak radzic sobie z problemem) ciezko mi wyobrazic sobie system ktory uruchamia miliony watkow - nie mowiac juz o milionach zadan.

Może jeden wątek dostaje listę zasobów, potem część z tej listy zwalnia, a
zwolnione powinny pójść do innych/nowych wątków? Może średnio działa 10 
wątków i każdy dostaje średnio 200tys numerków?

Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#28158

W dniu 2015-12-04 o 20:10, Adam M pisze:
> Tka przy okazji, z czystej ciekawosci sie pytam na jakim systemie to mam byc implementowane - czy to tylko teoretyczne dewagacje - za wyjatkiem duzych web-serwerow i baz danych obslugujacych bardzo duze firmy (w tym przypadku sa dobrze znane rozwiazania jak radzic sobie z problemem) ciezko mi wyobrazic sobie system ktory uruchamia miliony watkow - nie mowiac juz o milionach zadan.

Na Linuxie, zasoby te to akurat nie wątki, ale np. okna i inne.
Chcę oprogramować korzystanie z czystego protokołu X11. Tam gdy chcę 
utworzyć okno to wypełniam strukturę i wysyłam do socketu do pliku typu 
specjalnego w /tmp. W tej strukturze muszę podać numer uchwytu, a ten 
numer wiem, że może być >= numerowi bazowemu i dostępnych jest ok 2 mln 
(akurat w mojej konfiguracji). Nie utworzę tyle okien i innych zasobów, 
ale gdy będę tworzył i niszczył okno w pętli to nie mogę brać cały czas 
najwyższego numeru, musi być recykling.

[toc] | [prev] | [next] | [standalone]

#28160

On 04.12.2015 23:30, Borneq wrote:
> W dniu 2015-12-04 o 20:10, Adam M pisze:
>> Tka przy okazji, z czystej ciekawosci sie pytam na jakim systemie to
>> mam byc implementowane - czy to tylko teoretyczne dewagacje - za
>> wyjatkiem duzych web-serwerow i baz danych obslugujacych bardzo duze
>> firmy (w tym przypadku sa dobrze znane rozwiazania jak radzic sobie z
>> problemem) ciezko mi wyobrazic sobie system ktory uruchamia miliony
>> watkow - nie mowiac juz o milionach zadan.
>
> Na Linuxie, zasoby te to akurat nie wątki, ale np. okna i inne.
> Chcę oprogramować korzystanie z czystego protokołu X11. Tam gdy chcę
> utworzyć okno to wypełniam strukturę i wysyłam do socketu do pliku typu
> specjalnego w /tmp. W tej strukturze muszę podać numer uchwytu, a ten
> numer wiem, że może być >= numerowi bazowemu i dostępnych jest ok 2 mln
> (akurat w mojej konfiguracji). Nie utworzę tyle okien i innych zasobów,
> ale gdy będę tworzył i niszczył okno w pętli to nie mogę brać cały czas
> najwyższego numeru, musi być recykling.

No to nie potrzebujesz wcale trzymać wszystkich N numerów.

Jak opisałem poprzednio, kolejka fifo w cyklicznym buforze.
Ale inicjalizowana małą ilośćią liczb na początek.
Jeśli kolejka opustoszje, realokujesz dla niej dwa raz wiekszą
pamieć (tzn powiekszasz vectror, w którym to trzymasz:)
i dodajesz kolejne liczby.

pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

#28161

W dniu 2015-12-05 o 00:49, bartekltg pisze:
> Jak opisałem poprzednio, kolejka fifo w cyklicznym buforze.
> Ale inicjalizowana małą ilośćią liczb na początek.
> Jeśli kolejka opustoszje, realokujesz dla niej dwa raz wiekszą
> pamieć (tzn powiekszasz vectror, w którym to trzymasz:)
> i dodajesz kolejne liczby.

Pomysł ciekawy, zwłaszcza to, że jest inicjowana małą ilością liczb na 
początek, a potem można zwiększać. Kolejkę FIFO rozumiem jako dwa 
indeksy wskazujące na bufor, aby nie trzeba było przemieszczać danych?
Na razie zaangażowałem się w maski potrójnego poziomu - maska maks. 256 
bitów, drugiego poziomu miała być 65 K  a trzeciego 16 M. To raczej 
skomplikowana sprawa, więc, jak będą trudności zrobię powiększające się 
FIFO.
Wracając do szukania bitu w słowie:
zrobiłem testy, tam m.in. dwie metody z Uczty Programistów, które 
przesuwają kolejno o 18,8,4 i 2 bity. Metoda połówkowania całkowita do 
bitu i do czterech bitów; dodałem również dla porządku najoczywistszą 
metodę pętli.
Co się okazało: wszystkie mniej więcej w tym samym czasie, a najszybsza 
była metoda w pętli: (co dziwne, bo czas miał być proporcjonalny do 
liczby bitów a nie logarytmu z nich)
int ntz5_15(unsigned x)
{
	int n;
	x = ~x & (x - 1);
	n = 0;
	while (x != 0)
	{
		n = n + 1;
		x = x >> 1;
	}
	return n;
}
Tutaj jest jeden myk: "x = ~x & (x - 1)" wypełnia bity aż do napotkania 
pierwszej jedynki od dołu. Dzięki temu nie trzeba w pętli stosować AND.
W gruncie rzeczy potrzebowałem szukać zer, więc:
int findZero32(uint32_t x)
{
	int n;
	x = x & (~x - 1);
	n = 0;
	while (x != 0)
	{
		n = n + 1;
		x = x >> 1;
	}
	return n;
}
Lecz dla 64 bitów pętla to przesada, więc połówkuję go:
int findZero64(uint64_t x)
{
	if ((x | 0xffffffff00000000)!= 0xffffffffffffffff)
		return findZero32((uint32_t)x); //this branch must be first
	else
		return findZero32((uint32_t)(x >> 32)) + 32;		
}


Jeszcze o testach: test jednorodny odpada, bo połowa przypadków to były 
by pomiędzy 2 miliardy a 4 miliardy. Wybieram więc liczbę jedynek od 1 
do trzech, potem dla bitu losuję pozycję od 0 do 31 i ustawiam.

Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#28174

On 05.12.2015 09:37, Borneq wrote:
> W dniu 2015-12-05 o 00:49, bartekltg pisze:
>> Jak opisałem poprzednio, kolejka fifo w cyklicznym buforze.
>> Ale inicjalizowana małą ilośćią liczb na początek.
>> Jeśli kolejka opustoszje, realokujesz dla niej dwa raz wiekszą
>> pamieć (tzn powiekszasz vectror, w którym to trzymasz:)
>> i dodajesz kolejne liczby.
>
> Pomysł ciekawy, zwłaszcza to, że jest inicjowana małą ilością liczb na
> początek, a potem można zwiększać. Kolejkę FIFO rozumiem jako dwa
> indeksy wskazujące na bufor, aby nie trzeba było przemieszczać danych?

Tak. W booście jest chyba nawet gotowiec. A jak nie ma, zbudujesz
to na bazie vektor w 10 minut.


> Na razie zaangażowałem się w maski potrójnego poziomu - maska maks. 256
> bitów, drugiego poziomu miała być 65 K  a trzeciego 16 M. To raczej
> skomplikowana sprawa, więc, jak będą trudności zrobię powiększające się
> FIFO.

I jaką z tego będzeisz miał korzyść?
Potrzebujesz tam jakiś dodatkowych operacjji, o których nie wiem?

Czasowo jest gorsze.
Pamięćiowo najprawdopoobnij też (ile na raz okien będzie otwartych?),
a te dodatkowe 32 bity chyba nie są takim wqielkim narzutem, skoro
jadna liczba przyopada na okno (bardziej skomplikowaną strukturę).

Nie mówiąc o tym, że trudniejsze do napsiania;-)

pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

#28175

W dniu 2015-12-06 o 17:26, bartekltg pisze:
> Czasowo jest gorsze.
> Pamięćiowo najprawdopoobnij też (ile na raz okien będzie otwartych?),
> a te dodatkowe 32 bity chyba nie są takim wqielkim narzutem, skoro
> jadna liczba przyopada na okno (bardziej skomplikowaną strukturę).

Jak to dokładnie będzie wyglądało? Przypuśćmy że mamy tablicę 256 
wartości uint32_t, na razie pustą. Poza tym jedną liczbę oznaczającą 
numer uchwytu do pobrania, gdy nic nie będzie w kolejce. Na początku ta 
liczba jest 0, potem 1,2..99. zwalniamy 5, potem 2, potem 7.
W kolejce jest 5,2,7 w takiej kolejności, nie koniecznie kolejności 
wzrastających id. Allokujemy: bierzemy 5, itd. aż gdy kolejka będzie 
pusta to bierzemy 100 ?

[toc] | [prev] | [next] | [standalone]

#28177

On 06.12.2015 19:47, Borneq wrote:
> W dniu 2015-12-06 o 17:26, bartekltg pisze:
>> Czasowo jest gorsze.
>> Pamięćiowo najprawdopoobnij też (ile na raz okien będzie otwartych?),
>> a te dodatkowe 32 bity chyba nie są takim wqielkim narzutem, skoro
>> jadna liczba przyopada na okno (bardziej skomplikowaną strukturę).
>
> Jak to dokładnie będzie wyglądało? Przypuśćmy że mamy tablicę 256
> wartości uint32_t, na razie pustą. Poza tym jedną liczbę oznaczającą
> numer uchwytu do pobrania, gdy nic nie będzie w kolejce. Na początku ta
> liczba jest 0, potem 1,2..99. zwalniamy 5, potem 2, potem 7.
> W kolejce jest 5,2,7 w takiej kolejności, nie koniecznie kolejności
> wzrastających id. Allokujemy: bierzemy 5, itd. aż gdy kolejka będzie
> pusta to bierzemy 100 ?

class numerkomat{
uint32_t nastepny_numrek;
stack<numerek> data;
public:
  numerkomat();
  void numerek daj_numetek(){
  zwroc_numerek( numerek x)  {

};

numerek numerkomat::daj_numetek(){
   if (data.empty()) napelnij_numerkami( nastepny_numerek*2);
   numerek wyn = data.top();
   data.pop();
   return wyn;
}

void numerek numerkomat::zwroc_numerek(numerek x ){
{
    data.push(x);
}


numerkomat::numerkomat()
{
   napelnij_numerkami(100); //magiczna liczba, poprawić
}

void numerkomat:: napelnij_numerkami( numerek do_ilu )
{
   for (numerek n = nast_numerek; n != do_ilu; n++)
   {
      data.push(n);
   }
}


Dziel problem na poziomy. Powyżej masz klasę, która przydziela
numerki (nietestowana, szkicowana na kolanie). Tu używa std:stack.
W 20s podmienisz to na std:queue lub własną kalsę będącą cyklicznym
buforem zbudowanym na vectro (co jest drugim, zupełnie niezależnym
i niekoniecznie potrzebnym zadaniem).

Pewnie warto by też klasę numerek napisać tak, aby była niekopiowalna,
i tego typu obekty produkować tylko wewnętrz numerkomatu.
Trzeba by wtedy zmienić implementacje i wywołanie napelnij_numerkami,
ale za to użytkownik nie strzeli sobie w stopę tak łatwo, np zwracajkąc
ręcznie wpisaną liczbę.

pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

#28180

W dniu 2015-12-07 o 03:09, bartekltg pisze:
> void numerkomat:: napelnij_numerkami( numerek do_ilu )
> {
>    for (numerek n = nast_numerek; n != do_ilu; n++)
>    {
>       data.push(n);
>    }
> }

Trochę się różni, bo ja w kolejce w yAllocFifo trzymałem te, które 
zostawały zwolnione, a tu mamy napełnianie nowymi.
Jeśli chodzi o std:queue to jakie ma właściwości oprócz dwóch 
wskaźników? czy samoczynnie się powiększa? odporność na wątki?

[toc] | [prev] | [next] | [standalone]

#28176

W dniu 2015-12-06 o 17:26, bartekltg pisze:
> Czasowo jest gorsze.
> Pamięćiowo najprawdopoobnij też (ile na raz okien będzie otwartych?),
> a te dodatkowe 32 bity chyba nie są takim wqielkim narzutem, skoro
> jadna liczba przyopada na okno (bardziej skomplikowaną strukturę).
>
> Nie mówiąc o tym, że trudniejsze do napsiania;-)

A to za to bardzo proste:
yAllocFifo::yAllocFifo(const uint32_t base, const uint32_t count)
{
	alloc_base = base;
	alloc_count = count;
	sentinel = base + count;
	nextNumber = base;
}

uint32_t yAllocFifo::getNumber()
{
	if (fifo.canPop()) return fifo.pop();
	else
	{
		if (nextNumber >= sentinel) throw exception("no more nmbers");
		nextNumber++;
		return nextNumber-1;		
	}
	return 0;
}

void yAllocFifo::releaseNumber(uint32_t number)
{
	if (number < alloc_base)
		throw exception("releaseNumber: bad number, too small");
	if (number - alloc_base >= alloc_count)
		throw exception("releaseNumber: bad number, too big");
	fifo.push(number);
}


tylko nie sprawdza nic przy release, np. gdy zwalniamy już zwolnione to 
wtedy doda dwa razy, albo zwalniamy zupełnie inny numer, którego nie 
wzięliśmy.

[toc] | [prev] | [next] | [standalone]

#28178

On 07.12.2015 01:05, Borneq wrote:
> W dniu 2015-12-06 o 17:26, bartekltg pisze:
>> Czasowo jest gorsze.
>> Pamięćiowo najprawdopoobnij też (ile na raz okien będzie otwartych?),
>> a te dodatkowe 32 bity chyba nie są takim wqielkim narzutem, skoro
>> jadna liczba przyopada na okno (bardziej skomplikowaną strukturę).
>>
>> Nie mówiąc o tym, że trudniejsze do napsiania;-)
>
> A to za to bardzo proste:
> yAllocFifo::yAllocFifo(const uint32_t base, const uint32_t count)
> {
>      alloc_base = base;
>      alloc_count = count;
>      sentinel = base + count;
>      nextNumber = base;
> }
>
> uint32_t yAllocFifo::getNumber()
> {
>      if (fifo.canPop()) return fifo.pop();
>      else
>      {
>          if (nextNumber >= sentinel) throw exception("no more nmbers");
>          nextNumber++;
>          return nextNumber-1;
>      }
>      return 0;
> }
>
> void yAllocFifo::releaseNumber(uint32_t number)
> {
>      if (number < alloc_base)
>          throw exception("releaseNumber: bad number, too small");
>      if (number - alloc_base >= alloc_count)
>          throw exception("releaseNumber: bad number, too big");
>      fifo.push(number);
> }
>
>
> tylko nie sprawdza nic przy release, np. gdy zwalniamy już zwolnione to
> wtedy doda dwa razy, albo zwalniamy zupełnie inny numer, którego nie
> wzięliśmy.

A dlaczego chcesz wolnić coś już zwolnionego?

Numerek powiązany jest z czasem życia okna. pobiera
się w konstruktorze, uwalnia w destruktorze.
Jak uwolnił, to już go nie ma i dośc ciężko, żęby go niszczona drugi
raz.

Jak się bardzo obawiasz, że w kodzie może jadnak taka sytuacja występić,
zamiast szybkiego kontenera, który ma to gdiześ (stack, queue, ręczna
kolejna) wstaw tam tesotwo std::(unordered)set i sprawdzaj przy
oddawaniu, czy zwracanego obiektu już nie ma. Jak jest, podnosi
alarm i zatrzymuje debugger.

pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

#28151

On Friday, December 4, 2015 at 3:04:17 PM UTC+1, Borneq wrote:
> Dodatkowo potrzebne jeszcze mutexy, aby nie przydzielić dwa razy tego 
> samego numeru przy pracy na wątkach.
Nie bardzo mam czas, podpowiem tylko, że nie są konieczne do tego
muteksy.

[toc] | [prev] | [next] | [standalone]

#28152

Najlepsze rozwiązanie tego problemu z jakim się spotkałem to pamiętanie największego dotąd przyznanego numeru i posortowanej listy zwolnionych numerów.

AdamK

[toc] | [prev] | [next] | [standalone]

#28153

On Friday, December 4, 2015 at 5:31:48 PM UTC+1, Adam Klobukowski wrote:
> Najlepsze rozwiązanie tego problemu z jakim się spotkałem to pamiętanie największego dotąd przyznanego numeru i posortowanej listy zwolnionych numerów.
> 
> AdamK

Nie wierzę że nie spotkałeś się z lepszym :)

[toc] | [prev] | [next] | [standalone]

#28154

On Friday, December 4, 2015 at 11:31:48 AM UTC-5, Adam Klobukowski wrote:
> Najlepsze rozwiązanie tego problemu z jakim się spotkałem to pamiętanie największego dotąd przyznanego numeru i posortowanej listy zwolnionych numerów.
> 
> AdamK

Po pierwsze przepraszam za uzywanie angielskich zwrotow ale w pracy od kilkunastu lat uzywam wylacznie jezyka angielskiego wiec nie znam polskich odpowiednikow niektorych zwrotow.

Twoj pomysl bedzie dzialal dobrze tylko w systemie w ktorym task churn (duzo zadan jest uruchamainych i szybko zamykanych w losowych odstepach czasu) jest niewielki i nie wystepuje tzw. task attack lub inaczej task ramp-up effect (bardzo duzo zadan jest uruchamianych bardzo szybko po sobie przy niewielkiej ilosci zadan zwalnianych - stosunek zadan uruchamainych do zwalnianych jest bardzo niekorzystny)

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | pl.comp.programming

csiph-web