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

Groups > pl.comp.programming > #28161

Re: Struktura do przydzielania numerków

Show all headers | View raw

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

Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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