Algoritmikus problémamegoldás: Hogyan lehet hatékonyan kiszámítani a számok áramának paritását

Probléma nyilatkozat:

Számfolyamot (mondjuk longtípusú számokat) kap, számítsa ki a számok paritását. Hipotetikusan hatalmas skálát kell kiszolgálnia, például 1 millió számot percenként. Tervezzen meg egy algoritmust, figyelembe véve ezt a méretarányt. Egy szám paritása 1, ha a szám bináris reprezentációjában a beállított bitek száma páratlan, a paritás pedig 0.

Megoldás:

1. megközelítés - Brute Force:

A problémamegállapodás világosan kimondja, hogy mi a paritás. Az adott szám bináris ábrázolásában kiszámíthatjuk a beállított bitek teljes számát. Ha a beállított bitek száma páratlan, akkor a paritás 1más 0. Tehát a naiv módszer az, hogy folytatunk egy-egy bölcs jobb jobb váltást az adott számon, és ellenőrizzük az aktuálisan legkevésbé jelentős bitet (LSB), hogy nyomon kövessük az eredményt.

A fenti kódrészletben whileegyesével végigmegyünk a hurok összes bitjén . A feltétellel ((no & 1) == 1)ellenőrizzük, hogy a jelenlegi LSB van-e, 1vagy 0ha 1igen result ^= 1. A változó resultinicializálása 0. Tehát amikor mi xor (^)közötti aktuális értékét resultés 1a resultlesz állítva 1, ha a resultjelenleg 0, egyébként 1.

Ha páros számú beállított bit van, akkor végül azzá resultválik, 0mert xormindenki között 1’störlik egymást. Ha páratlan számú van 1’s, akkor a végső értéke resultlesz 1. no >>> 1 jobbra eltolja a biteket 1-gyel.

>; >> logikus jobb oldali eltolás operátor a java-ban, amely eltolja az előjelbitet is (az előírt szám legjelentősebb bitje). Van még egy jobb oldali eltolás op er- vagy >>, amelyet aritmetikai jobb s emelési operátornak nevezünk [lásd az 1. hivatkozást az oldal első részén]. Nem tolja el a jelbitet a bináris reprezentációban - a jelbit épen marad ition. Finaleredményénél, és a 0x1 1-et ad vissza, ha ea paritás, vagy 0 egyébként.

Előnyök:

  1. A megoldás nagyon könnyen érthető és megvalósítható.

Hátrányok:

  1. Az összes bitet manuálisan dolgozzuk fel, ezért ez a megközelítés alig hatékony léptékben.

Időkomplexitás:O(n) hol nvan az összes bit száma az adott szám bináris ábrázolásában.

2. megközelítés - Törölje az összes beállított bitet egyenként:

Van egy szűk keresztmetszet a fenti megoldásban: whilemaga a hurok. Csak egyenként megy keresztül minden biten, valóban ezt kell tennünk? Aggódásunk a beállított bitek miatt van, ezért semmilyen előnyhöz nem jutunk azzal, ha túlhaladjuk a beállítatlan biteket vagy 0biteket. Ha csak beállított biteket tudunk áttekinteni, akkor a megoldásunk kissé optimalizáltabbá válik. A bitenkénti számításban, ha számot kapunk n, akkor a jobb szélső bitet törölhetjük a következő művelettel:

n = n & (n-1)

Vegyünk egy példát: azt mondják n = 40, a bináris 8 bites formátum: 00101000.

n = 0010 1000 n - 1 = 0010 0111 n & (n - 1) = 0010 0000 

Sikeresen töröltük a legalacsonyabb beállított bitet (4. bit a jobb oldalról). Ha ezt folytatjuk, a szám egy bizonyos időpontban nváltozik 0. Ezen logika alapján, ha kiszámítjuk a paritást, akkor nem kell az összes bitet beolvasnunk. Inkább csak kbiteket szkennelünk, ahol ka beállított bitek száma a & számban található k <= length of the binary representation. A következő a kód:

Előnyök:

  1. Egyszerű kivitelezni.
  2. Hatékonyabb, mint a nyers erő megoldása.

Hátrányok:

  1. Ez nem a leghatékonyabb megoldás.

Idő összetettsége:

O(k)hol kvan a megadott bitek teljes száma a számban.

3. megközelítés - gyorsítótár:

Nézze meg még egyszer a problémamegállapítást, mindenképpen aggályos a méretarány. Skálázódhatnak-e korábbi megoldásaink több millió kérés kiszolgálására, vagy van-e még lehetőség a jobb teljesítésre?

Valószínűleg gyorsabbá tehetjük a megoldást, ha az eredményt el tudjuk tárolni a memóriában - gyorsítótárban. Így menthetünk néhány CPU-ciklust ugyanazon eredmény kiszámításához. Tehát, ha az összes bit száma 64, mennyi memóriára van szükségünk az összes lehetséges szám elmentéséhez? 64bitek vezetnek arra, hogy legyenek Math.pow(2, 64)lehetséges aláírt számaink (a legjelentősebb bitet csak az előjelek tárolására használják). A longtípusszám mérete 64bit vagy 8bájt, tehát a teljes memória szükséges: 64 * Math.pow(2, 64)bit vagy 134217728 TeraBytes. Ez túl sok, és nem éri meg ilyen hatalmas mennyiségű adatot tárolni. Jobban tehetnénk?

Bonthatjuk a 64bitek számát bitek csoportjába 16, lehívhatjuk az egyes bitcsoportok paritását a gyorsítótárból és kombinálhatjuk őket. Ez a megoldás azért működik, mert egyenlő részekre 16oszlik 64, 4és csak a beállított bitek teljes száma miatt aggódunk. Tehát amennyire megkapjuk az egyes bitcsoportok paritását, meg tudjuk vizsgálni xoraz eredményeiket egymással, mivel xorez asszociatív és kommutatív. Az a sorrend, amelyben lekérjük az adott bitcsoportot és azokat működtetjük, nem is számít.

Ha tárolni azokat 16bites számok, mint egy egész, teljes memória szükséges a következő: Math.pow(2, 16) * 32 bits = 256 Kilo Bytes.

A fenti kód, csúsztatjuk egy csoport 16bitek i * WORD_SIZE, ahol

0 ≤ i ≤ 3és hajtsuk végre a bitenkénti ANDműveletet ( &) egy mask = 0xFFFF( 0xFFFF = 1111111111111111 ) paranccsal, hogy csak a jobb szélső 16biteket tudjuk kivonni egész változóként, mint például masked1, masked2stb., ezeket a változókat átadjuk egy olyan módszernek, checkAndSetInCacheamely kiszámítja ennek a számnak a paritását, ha az nem elérhető a gyorsítótárban. Végül csak xorműveletet hajtunk végre ezen számcsoport eredményével, amely meghatározza az adott szám végső paritását.

Előnyök:

  1. A gyorsítótár számára viszonylag kicsi memória árán jobb hatékonyságot érünk el, mivel a bemenetek között újból felhasználjuk a 16 bites számok csoportját.
  2. Ez a megoldás jól skálázható, mivel számok millióit szolgáljuk ki.

Hátrányok:

  1. Ha ezt az algoritmust ultra alacsony memóriaeszközökön kell megvalósítani, akkor a tér bonyolultságát előre meg kell gondolni annak eldöntésére, hogy megéri-e ekkora helyet befogadni.

Idő összetettsége:

O(n / WORD_SIZE)hol nvan a bináris reprezentáció bitjeinek teljes száma. Minden jobb / bal shift és bitenként &, |, ~stb. Művelet olyan szószintű művelet, amelyet a CPU rendkívül hatékonyan végez. Ezért feltételezhetően időbeli összetettségük O(1).

4. megközelítés - XOR és Shifting műveletek használata:

Nézzük ezt a 8 bites bináris: 1010 0100. A paritás ez a szám 1. Mi történik, ha jobbra 4toljuk ezt a számot úgy, hogy ezt magával a számmal végezzük ?

n = 1010 0100 n >>> 4 = 0000 1010 n ^ (n >> 4) = 1010 1110 n = n ^ (n >>> 4) = 1010 1110 (n is just assigned to the result)

A jobb szélső 4bit, az összes bit van beállítva, amelyek különböznek a n& n >&gt;> 4. Most koncentráljunk erre a jobbra 4- ts oszer: 1110, felejtsük el a többi b-t i. Now n is 1010 1110 & csak a elegalacsonyabb 4-re koncentrálunk, its azaz; 1110. Végezzünk bitenként jobbra sváltást n-vel 2-vel.

n = 1010 1110 n >>> 2 = 0010 1011 n ^ (n >>> 2) = 1000 0101 n = n ^ (n >>> 2) = 1000 0101 (n is just assigned to the result)

Most koncentráljon a jobb szélső 2bitekre, és felejtse el a bal szélső 6biteket. Helyezzük jobbra a számot 1:

n = 1000 0101 n >>> 1 = 0100 0010 n ^ (n >>> 1) = 1100 0111 n = n ^ (n >>> 1) = 1100 0111 (n is just assigned to the result)

Nem kell, hogy jobb Shift többé, csak most kivonat a LSB bit, amely 1a fenti esetben & visszatér az eredmény: result = (short) n & 1.

Ránézésre a megoldás kissé zavarosnak tűnhet, de működik. Hogyan? Egyébként tudjuk, hogy van 0 xor 1vagy 1 xor 0van . Tehát, amikor egy szám bináris ábrázolását hossza szerint két egyenlő felre osztjuk és közöttük tesszük, akkor az összes különböző bitpár halmazállapotú bitekké alakul az xor-ed számban.10xor

Mivel a paritás akkor fordul elő, ha páratlan számú készlet bit van a bináris ábrázolásban, a xorművelettel ellenőrizhetjük, 1létezik-e ott páratlan szám . Ennélfogva jobbra xortoljuk a számot a teljes számjegy felével, mi pedig eltoltuk a számot az eredeti számmal, a xor-ed eredményt az eredeti számhoz rendeljük és csak a szám jobb szélére koncentrálunk. Tehát egyszerre csak a számok felét xorozzuk és csökkentjük az xor hatókörét. Mert 64bites számok kezdünk XOR logikai és 32kicsit félre, akkor 16bit fele, akkor 8, 4, 2, 1ill.

Lényegében a szám paritása a szám xorbináris ábrázolásának egyenlő felének paritását jelenti . A kritikus pontja az algoritmus koncentrálni jobb szélső 32bit először, majd 16, 8, 4, 2, 1bitek és figyelmen kívül hagyja más bal oldali bit. A következő a kód:

Előnyök:

  1. Nincs külön szóköz szószintű műveletekkel az eredmény kiszámításához.

Hátrányok:

  1. Kicsit nehezen érthető a fejlesztők számára.

Idő összetettsége:

O(log n)hol nvan a bináris reprezentáció bitjeinek teljes száma.

A következő a teljes működési kód:

import java.util.Arrays; public class ParityOfNumber { private static short computeParityBruteForce(long no) { int result = 0; while(no != 0) { if((no & 1) == 1) { result ^= 1; } no >>>= 1; } return (short) (result & 0x1); } private static short computeParityBasedOnClearingSetBit(long no) { int result = 0; while (no != 0) { no = no & (no - 1); result ^= 1; } return (short) (result & 0x1); } private static short computeParityWithCaching(long no) { int[] cache = new int[(int) Math.pow(2, 16)]; Arrays.fill(cache, -1); int WORD_SIZE = 16; int mask = 0xFFFF; int masked1 = (int) ((no >>> (3 * WORD_SIZE)) & mask); checkAndSetInCache(masked1, cache); int masked2 = (int) ((no >>> (2 * WORD_SIZE)) & mask); checkAndSetInCache(masked2, cache); int masked3 = (int) ((no >>> WORD_SIZE) & mask); checkAndSetInCache(masked3, cache); int masked4 = (int) (no & mask); checkAndSetInCache(masked4, cache); int result = (cache[masked1] ^ cache[masked2] ^ cache[masked3] ^ cache[masked4]); return (short) (result & 0x1); } private static void checkAndSetInCache(int val, int[] cache) { if(cache[val] >> 32); no ^= (no >>> 16); no ^= (no >>> 8); no ^= (no >>> 4); no ^= (no >>> 2); no ^= (no >>> 1); return (short) (no & 1); } public static void main(String[] args) { long no = 1274849; System.out.println("Binary representation of the number: " + Long.toBinaryString(no)); System.out.println("Is Parity [computeParityBruteForce]: " + computeParityBruteForce(no)); System.out.println("Is Parity [computeParityBasedOnClearingSetBit]: " + computeParityBasedOnClearingSetBit(no)); System.out.println("Is Parity [computeParityMostEfficient]: " + computeParityMostEfficient(no)); System.out.println("Is Parity [computeParityWithCaching]: " + computeParityWithCaching(no)); } }

Tanulás ebből a gyakorlatból:

  1. Bár alapvető ismeretekről van szó, meg akarom említeni, hogy a szószintű bitenkénti műveletek időben állandóak.
  2. Egy skálán alkalmazhatjuk a gyorsítótárat úgy, hogy a bináris ábrázolást megfelelő szóméretű felekre bontjuk, hasonlóan esetünkhöz, 16hogy az összes lehetséges számot el tudjuk helyezni a memóriában. Mivel állítólag több millió számot kell kezelnünk, végül a bache 16csoportokat újból felhasználjuk a gyorsítótárból a számok között. A szó méretének nem feltétlenül kell lennie 16, ez a követelményektől és a kísérletektől függ.
  3. A szám működtetéséhez nem szükséges egy szám bináris reprezentációját tárolnia a külön tömbben, inkább a bitenkénti műveletek okos használata segíthet a cél elérésében.

Referenciák:

[1]. //stackoverflow.com/questions/2811319/difference-between-and

[2]. //gist.github.com/kousiknath/b0f5cd204369c5cd1669535cc9a58a53