-
Path: news-archive.icm.edu.pl!news.icm.edu.pl!news.supermedia.pl!news.nask.pl!news.na
sk.org.pl!news.unit0.net!cyclone01.ams2.highwinds-media.com!voer-me.highwinds-m
edia.com!peer01.am1!peering.am1!peer01.fr7!news.highwinds-media.com!newsfeed.ne
ostrada.pl!unt-exc-02.news.neostrada.pl!unt-spo-a-01.news.neostrada.pl!news.neo
strada.pl.POSTED!not-for-mail
From: szemrany <s...@o...off>
Subject: Re: Szybkie szukanie ustawionego bitu
Newsgroups: pl.comp.programming
User-Agent: 40tude_Dialog/2.0.15.84
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: 8bit
Sender: n...@p...no
References: <1...@4...net>
Date: Tue, 1 Sep 2015 14:40:34 +0200
Message-ID: <wc4ru3v45dm0$.1mtwq7sfflbyu.dlg@40tude.net>
Lines: 53
Organization: Telekomunikacja Polska
NNTP-Posting-Host: 89-71-60-55.dynamic.chello.pl
X-Trace: 1441111235 unt-rea-a-01.news.neostrada.pl 4778 89.71.60.55:2227
X-Complaints-To: a...@n...neostrada.pl
X-Received-Body-CRC: 3884815321
X-Received-Bytes: 2552
Xref: news-archive.icm.edu.pl pl.comp.programming:208102
[ ukryj nagłówki ]
Reasumując chcę wszystkim podziękować za uwagi i sugestie oraz chcę
przedstawić wyniki testów. Zrobiłem 4 funkcje operujące na różnych
algorytmach i pomierzyłem ich wydajność.
Założenie: daję do sprawdzenia liczbę, która ma ustawiony dopiero 38 bit (i
inne dalej), pętla wykonuje się 10 mln razy, oto wyniki:
- Metoda klasyczna czyli pętla while i przesuwanie bitów w prawo, aż będzie
ustawiony najmłodsdzy bit
Czas: 813 ms
- Metoda dzielenia połówkowego/binarnego, algorytm z wiki:
function ctz (x)
if x = 0 return 32
n <- 0
if (x & 0x0000FFFF) = 0: n <- n + 16, x <- x >> 16
if (x & 0x000000FF) = 0: n <- n + 8, x <- x >> 8
if (x & 0x0000000F) = 0: n <- n + 4, x <- x >> 4
if (x & 0x00000003) = 0: n <- n + 2, x <- x >> 2
if (x & 0x00000001) = 0: n <- n + 1
return n
Czas: 67 ms
- Metoda z X & -X (pozostawienie tylko najmłodszego ustawionego bitu),
potem sprawdzenie młodszych 32 bitów przez &, jeśli nic nie ma to dodanie
do wyniki 32, przesunięcie starszych 32 bitów w prawo i sprawdzenie czy coś
w nich jest przez &, a gdy jest to switch na wartości od 2 do 32, który
zwraca indeks (dla 256 zwraca 8)
Czas: 51 ms
- Assemblerowa instrukcja BSF użyta dwa razy na starszych i młodszych
bitach liczby 64 bitowej:
BSF EAX, DWORD PTR [&u64]
JNZ @@Exit
BSF EAX, DWORD PTR [&u64 + 4]
JZ @@Exit
ADD EAX, 32
@@Exit:
MOV &Result, EAX
Czas: 28 ms
--
howgh
szemrany
"Trzeba z żywymi naprzód iść, po życie sięgać nowe,
a nie w uwiędłych laurów liść z uporem stroić głowę"
Następne wpisy z tego wątku
- 01.09.15 16:10 bartekltg
- 01.09.15 17:28 szemrany
- 01.09.15 22:20 szemrany
- 04.09.15 09:14 Wojciech Muła
- 04.09.15 09:53 szemrany
- 04.09.15 17:01 Wojciech Muła
- 04.09.15 20:20 szemrany
- 07.09.15 09:46 Radoslaw Szwed
Najnowsze wątki z tej grupy
- Popr. 14. Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- Arch. Prog. Nieuprzywilejowanych w pełnej wer. na nowej s. WWW energokod.pl
- 7. Raport Totaliztyczny: Sprawa Qt Group wer. 424
- 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
Najnowsze wątki
- 2025-02-01 Śmierć mózgu a narządy do pobrania
- 2025-01-31 A niektórym to naprawdę zależy na ekologi w miastach LPG POWRACA ;-)
- 2025-01-31 Lublin => Programista Delphi <=
- 2025-01-31 Łódź => Programista NodeJS <=
- 2025-01-31 Wrocław => Senior SAP Support Consultant (SD) <=
- 2025-01-31 Warszawa => Full Stack web developer (obszar .Net Core, Angular6+) <=
- 2025-01-31 Gdańsk => iOS Developer (Swift experience) <=
- 2025-01-31 Kraków => UX Designer <=
- 2025-01-31 Warszawa => Data Engineer (Tech Leader) <=
- 2025-01-31 Gliwice => Business Development Manager - Dział Sieci i Bezpieczeńst
- 2025-01-31 Gliwice => Business Development Manager - Network and Network Security
- 2025-01-31 Warszawa => Architekt rozwiązań (doświadczenie w obszarze Java, AWS
- 2025-01-31 Warszawa => Full Stack .Net Engineer <=
- 2025-01-31 Warszawa => Programista Full Stack (.Net Core) <=
- 2025-01-31 Gdańsk => Programista Full Stack .Net <=