Path: csiph.com!news.mixmin.net!weretis.net!feeder4.news.weretis.net!ecngs!testfeeder.ecngs.de!81.171.118.63.MISMATCH!peer03.fr7!news.highwinds-media.com!newsfeed.neostrada.pl!unt-exc-01.news.neostrada.pl!newsfeed2.atman.pl!newsfeed.atman.pl!.POSTED!not-for-mail From: Borneq Newsgroups: pl.comp.programming Subject: =?UTF-8?Q?Re:_Struktura_do_przydzielania_numerk=c3=b3w?= Date: Sat, 5 Dec 2015 09:37:39 +0100 Organization: ATMAN - ATM S.A. Lines: 67 Message-ID: References: <304e402f-18c6-406c-901a-b412811bfcc9@googlegroups.com> NNTP-Posting-Host: 91.239.205.105 Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit X-Trace: node1.news.atman.pl 1449304647 28014 91.239.205.105 (5 Dec 2015 08:37:27 GMT) X-Complaints-To: usenet@atman.pl NNTP-Posting-Date: Sat, 5 Dec 2015 08:37:27 +0000 (UTC) User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:38.0) Gecko/20100101 Thunderbird/38.4.0 In-Reply-To: X-Received-Bytes: 3430 X-Received-Body-CRC: 175387993 Xref: csiph.com pl.comp.programming: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