Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > pl.comp.programming > #28146 > unrolled thread
| Started by | Borneq <borneq@antyspam.hidden.pl> |
|---|---|
| First post | 2015-12-04 15:04 +0100 |
| Last post | 2015-12-06 11:29 +0100 |
| Articles | 5 on this page of 25 — 5 participants |
Back to article view | Back to pl.comp.programming
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 2 of 2 — ← Prev page 1 [2]
| From | bartekltg <bartekltg@gmail.com> |
|---|---|
| Date | 2015-12-05 00:45 +0100 |
| Message-ID | <n3t8i9$tnq$1@node1.news.atman.pl> |
| In reply to | #28146 |
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. 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. 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. pzdr bartekltg
[toc] | [prev] | [next] | [standalone]
| From | "M.M." <mmarszik@gmail.com> |
|---|---|
| Date | 2015-12-05 03:44 -0800 |
| Message-ID | <e48062f0-b9cc-47bf-b40d-9b5cffd6e58b@googlegroups.com> |
| In reply to | #28159 |
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
[toc] | [prev] | [next] | [standalone]
| From | Borneq <borneq@antyspam.hidden.pl> |
|---|---|
| Date | 2015-12-06 10:12 +0100 |
| Message-ID | <n40u4i$5ld$1@node2.news.atman.pl> |
| In reply to | #28146 |
W dniu 2015-12-04 o 15:04, Borneq pisze:
> 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.
Zrobiłem, nie myślałem że będzie to takie skomplikowane, dużo pomogła mi
obiektowość C++. Liczy aż 500 linii .cpp i 100 linii .h
Zrobiłem maski bitowe. 256 bitów maski reprezentowane jest przez jeden
bit AND i jeden bit OR na poziomie 1, z kolei te 256 bitów przez jeden
maski AND i OR na poziomie 2.
Ponieważ najwyższy poziom liczy 256 bitów, to maksymalnie struktura może
trzymać 256*256*256 = 16M pozycji.
Na poziomie 0 mamy: (dla uproszczenia - 4 zamiast 256 bitów)
[1111] [1011] [0011] [0000] | [0100] [1111] [1000] [0000] | [0000]
[0000] [0000] [0000] | [1111] [1111] [1111] [1111]
Na poziomie 1 maska AND:
1000 | 0100 | 0000 | 1111
Na poziomie 1 maska OR:
1110 | 1110 | 0000 | 1111
więcej pamięci niż maski mogą zużywać indeksu gdzie indeks =
(wskaźnik,numer), gdzie numer to 1 bajt ale wskaźnik to 4 a nawet 8.
i teraz ciekawe: nie pamiętamy na poziomie 0 tych, dla których są same
jedynki albo same zera, czyli te dla których zarówno na poziomie 1 są
jedynki dla AND i OR jak i zera dla obu, czyli XOR=0.
Pamiętamy tylko te nieliczne, gdzie dla OR jest jedynka a dla AND zero.
on level 1 indices from range(16) only for this: not all 0, not all 1
1,2,4,6
just indices is for set bits od XOR mask:
0110 | 1010 | 0000 | 0000
XOR maski AND i OR będzie 0110 | 1010 | 0000 | 0000
czyli będą istnieć maski rzędu 0 dla indeksów 1,2,4,6
Indeks rzędu 2 podobnie tworzymy z rzędu 1.
Podaję linka, może się przydać:
https://gist.github.com/borneq/0bd3c32e5aec4966a40d
Ta wersja ma jeden mankament, o którym pisałem na grupie C "Destruktor
zachowuje się jakby był niewirtualny"
void yBitmaskHi::releaseAllIndices()
{
for (int i = 0; i < indexCount; i++)
delete indices[i].lowerLevel;
indexCount = 0;
}
nie woła destruktora level1, nie wiem czemu
[toc] | [prev] | [next] | [standalone]
| From | Borneq <borneq@antyspam.hidden.pl> |
|---|---|
| Date | 2015-12-06 10:21 +0100 |
| Message-ID | <n40umo$64u$1@node2.news.atman.pl> |
| In reply to | #28170 |
W dniu 2015-12-06 o 10:12, Borneq pisze: > Na poziomie 0 mamy: (dla uproszczenia - 4 zamiast 256 bitów) > Podaję linka, może się przydać: > https://gist.github.com/borneq/0bd3c32e5aec4966a40d Uwaga: mówię o 256 bitach, ale tutaj mamy ustawione na razie #define BitsToBit 4 do celów debugowania, czyli mamy strukturę 4*4*4
[toc] | [prev] | [next] | [standalone]
| From | Borneq <borneq@antyspam.hidden.pl> |
|---|---|
| Date | 2015-12-06 11:29 +0100 |
| Message-ID | <n412l2$mrh$2@node1.news.atman.pl> |
| In reply to | #28170 |
W dniu 2015-12-06 o 10:12, Borneq pisze:
> Ta wersja ma jeden mankament, o którym pisałem na grupie C "Destruktor
> zachowuje się jakby był niewirtualny"
> void yBitmaskHi::releaseAllIndices()
> {
> for (int i = 0; i < indexCount; i++)
> delete indices[i].lowerLevel;
> indexCount = 0;
> }
> nie woła destruktora level1, nie wiem czemu
Poprawione, destruktory muszą być jawnie oznaczone jako wirtualne i w
dodatku klasa bazowa musi mieć konstruktor wirtualny, choćby pusty.
[toc] | [prev] | [standalone]
Page 2 of 2 — ← Prev page 1 [2]
Back to top | Article view | pl.comp.programming
csiph-web