-
21. Data: 2015-12-06 19:47:03
Temat: Re: Struktura do przydzielania numerków
Od: Borneq <b...@a...hidden.pl>
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 ?
-
22. Data: 2015-12-07 01:05:49
Temat: Re: Struktura do przydzielania numerków
Od: Borneq <b...@a...hidden.pl>
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.
-
23. Data: 2015-12-07 03:09:01
Temat: Re: Struktura do przydzielania numerków
Od: bartekltg <b...@g...com>
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
-
24. Data: 2015-12-07 03:13:19
Temat: Re: Struktura do przydzielania numerków
Od: bartekltg <b...@g...com>
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
-
25. Data: 2015-12-07 10:31:09
Temat: Re: Struktura do przydzielania numerków
Od: Borneq <b...@a...hidden.pl>
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?