-
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
atman.pl!.POSTED!not-for-mail
From: Borneq <b...@a...hidden.pl>
Newsgroups: pl.comp.programming
Subject: Re: Struktura do przydzielania numerków
Date: Sat, 5 Dec 2015 09:37:39 +0100
Organization: ATMAN - ATM S.A.
Lines: 67
Message-ID: <n3u7o7$rbe$1@node1.news.atman.pl>
References: <n3s6h0$itv$1@node2.news.atman.pl> <n3s7d4$js6$1@node2.news.atman.pl>
<3...@g...com>
<n3sapd$trt$1@node1.news.atman.pl>
<f...@g...com>
<n3t46b$ol1$1@node1.news.atman.pl> <n3t8qq$tv4$1@node1.news.atman.pl>
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: u...@a...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: <n3t8qq$tv4$1@node1.news.atman.pl>
Xref: news-archive.icm.edu.pl pl.comp.programming:208965
[ ukryj nagłówki ]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
Następne wpisy z tego wątku
- 05.12.15 12:44 M.M.
- 06.12.15 10:12 Borneq
- 06.12.15 10:21 Borneq
- 06.12.15 11:29 Borneq
- 06.12.15 17:26 bartekltg
- 06.12.15 19:47 Borneq
- 07.12.15 01:05 Borneq
- 07.12.15 03:09 bartekltg
- 07.12.15 03:13 bartekltg
- 07.12.15 10:31 Borneq
Najnowsze wątki z tej grupy
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
Najnowsze wątki
- 2024-09-16 zapora Stronie Slaskie
- 2024-09-16 powodz
- 2024-09-16 Aple ma przycisk APARATU. SERIO? Tyle lat im to zajęło?
- 2024-09-15 Mulitisim
- 2024-09-15 Jaki telefon dla "SENIORA"? ;-)
- 2024-09-18 Co z 7 miejsc w leasingu dla fizycznych?
- 2024-09-17 Kultura zapie....ania
- 2024-09-17 Gdańsk się skończył dla mnie.
- 2024-09-16 Elektryki z południa lecą do ciepłych krajów :)
- 2024-09-16 Re: Wolkswagen szantażuje rząd aby powróciły dotacje do elektryków
- 2024-09-17 Wybuchające pagery
- 2024-09-18 szukam speca od mini-remontow (w w-wie)
- 2024-09-18 Warszawa => Spedytor międzynarodowy <=
- 2024-09-18 Kraków => Java Full Stack Developer (Angular/React) <=
- 2024-09-18 Warszawa => Projektant/Programista React Native <=