Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > pl.comp.programming > #28170
| From | Borneq <borneq@antyspam.hidden.pl> |
|---|---|
| Newsgroups | pl.comp.programming |
| Subject | Re: Struktura do przydzielania numerków |
| Date | 2015-12-06 10:12 +0100 |
| Organization | ATMAN - ATM S.A. |
| Message-ID | <n40u4i$5ld$1@node2.news.atman.pl> (permalink) |
| References | <n3s6h0$itv$1@node2.news.atman.pl> |
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
Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web