Algoritmisk problemløsning: Sådan beregnes pariteten af en strøm af tal effektivt
Problemformulering:
Du får en strøm af tal (sig long
typetal), beregn pariteten af tallene. Hypotetisk skal du tjene en enorm skala som 1 million numre i minuttet. Design en algoritme, der overvejer en sådan skala. Paritet af et tal er 1, hvis det samlede antal sætbits i den binære repræsentation af tallet er ulige, ellers er paritet 0.
Opløsning:
Tilgang 1 - Brute Force:
Problemangivelsen angiver klart, hvad paritet er. Vi kan beregne det samlede antal sæt bits i den binære repræsentation af det givne antal. Hvis det samlede antal sæt bits er ulige, er paritet 1
andet 0
. Så den naive måde er at fortsætte med at gøre et lidt klogt højre skift på det givne nummer og kontrollere den nuværende mindst signifikante bit (LSB) for at holde styr på resultatet.

I ovenstående kodestykke gennemgår vi alle bitene i while
sløjfen en efter en. Med betingelsen ((no & 1) == 1)
kontrollerer vi, om den aktuelle LSB er, 1
eller 0
hvis 1
vi gør det result ^= 1
. Variablen result
initialiseres til 0
. Så når vi xor (^)
opererer mellem den aktuelle værdi af result
& 1
, result
vil den blive indstillet til, 1
hvis den result
er i øjeblikket 0
, ellers 1
.
Hvis der er et lige antal, der er bits, i sidste ende det result
vil blive 0
, fordi xor
mellem alle 1’s
vil udligne hinanden. Hvis der er et ulige antal 1’s
, vil den endelige værdi result
være 1
. no >&
gt;> 1 højre skifter bitene med 1.
>
; >> er logisk højre skiftoperatør i java, som også skifter tegnbiten (den mest betydningsfulde bit i et underskrevet nummer). Der er en anden højre er
skifteoperator - >>, der kaldes aritmetisk højre s liftoperator [se reference 1 sidst på siden]. Det skifter ikke tegnbiten i den binære repræsentation - tegnbiten forbliver intakt ved sit ition. Final
aktuelle resultat, og 0x1 returnerer 1, hvis der
e
er paritet eller 0 på anden måde.
Fordele:
- Løsningen er meget let at forstå og implementere.
Ulemper:
- Vi behandler alle bits manuelt, så denne tilgang er næppe effektiv i skala.
Tidskompleksitet:O(n)
hvor n
er det samlede antal bits i den binære repræsentation af det givne nummer.
Fremgangsmåde 2 - Ryd alle sætbit en efter en:
Der er en flaskehals i ovenstående løsning: selve while
sløjfen. Det går bare gennem alle bits en efter en, skal vi virkelig gøre det? Vores bekymring handler om sætbits, så vi får ingen fordele ved at gå over usættede bits eller 0
bits. Hvis vi bare kan gå over kun sæt bits, bliver vores løsning lidt mere optimeret. Ved bitvis beregning, hvis vi får et tal n
, kan vi rydde den længst indstillede bit med følgende handling:
n = n & (n-1)
Tag et eksempel: sige n = 40
, den binære repræsentation i 8-bit format er: 00101000
.
n = 0010 1000 n - 1 = 0010 0111 n & (n - 1) = 0010 0000
Vi har med succes ryddet den laveste indstillede bit (4. bit fra højre side). Hvis vi holder gør dette, at antallet n
vil blive 0
på et bestemt tidspunkt. Baseret på denne logik, hvis vi beregner paritet, behøver vi ikke scanne alle bits. Snarere scanner vi kun k
bits, hvor k
er det samlede antal sæt bits i antallet & k <= length of the binary representation
. Følgende er koden:

Fordele:
- Enkel at implementere.
- Mere effektiv end brute force-løsning.
Ulemper:
- Det er ikke den mest effektive løsning.
Tidskompleksitet:
O(k)
hvor k
er det samlede antal sæt bits i antallet.
Fremgangsmåde 3 - Cache:
Se igen på problemopgørelsen, der er bestemt bekymring for skala. Kan vores tidligere løsninger skaleres til at betjene millioner af anmodninger, eller er der stadig mulighed for at gøre det bedre?
Vi kan sandsynligvis gøre løsningen hurtigere, hvis vi kan gemme resultatet i hukommelse - cache. På denne måde kan vi gemme nogle CPU-cyklusser for at beregne det samme resultat. Så hvis det samlede antal bits er 64
, hvor meget hukommelse har vi brug for for at gemme alle mulige tal? 64
bits får os til at have Math.pow(2, 64)
mulige underskrevne numre (den mest betydningsfulde bit bruges til kun at gemme tegn). Størrelsen på et long
typenummer er 64
bits eller 8
bytes, så den krævede samlede hukommelsesstørrelse er: 64 * Math.pow(2, 64)
bits eller 134217728 TeraBytes
. Dette er for meget og det er ikke det værd at gemme en så enorm mængde data. Kan vi gøre det bedre?
Vi kan bryde 64
bitsnummeret i en gruppe af 16
bits, hente pariteten af de individuelle grupper af bits fra cachen og kombinere dem. Denne løsning fungerer, fordi den 16
opdeles 64
i 4
lige store dele, og vi er bekymrede for det samlede antal sæt bits. Så vidt vi får paritet af de enkelte grupper af bits, kan vi xor
deres resultater med hinanden, da det xor
er associerende og kommutativt. Den rækkefølge, hvor vi henter den gruppe af bits og opererer dem, betyder ikke engang.
Hvis vi gemme disse 16
bit tal som et heltal, samlet hukommelse kræves er: Math.pow(2, 16) * 32 bits = 256 Kilo Bytes
.

I ovenstående uddrag skifter vi en gruppe 16
bits efter i * WORD_SIZE
hvor
0 ≤ i ≤ 3
og udfør bitvis AND
betjening ( &
) med a mask = 0xFFFF
( 0xFFFF = 1111111111111111
), så vi bare kan udtrække de længste 16
bit som heltalsvariabler som masked1, masked2
osv. Vi sender disse variabler til en metode, checkAndSetInCache
der beregner pariteten af dette nummer, hvis det ikke er tilgængeligt i cachen. I sidste ende udfører vi bare xor
resultatet af denne gruppe af tal, der bestemmer den endelige paritet af det givne nummer.
Fordele:
- På bekostning af relativt lille hukommelse til cachen får vi bedre effektivitet, da vi genbruger en gruppe på 16-bit tal på tværs af input.
- Denne løsning kan skaleres godt, da vi betjener millioner af numre.
Ulemper:
- Hvis denne algoritme skal implementeres i en ultra-lav hukommelsesenhed, skal pladskompleksiteten overvejes på forhånd for at afgøre, om det er det værd at rumme en sådan mængde plads.
Tidskompleksitet:
O(n / WORD_SIZE)
hvor n
er det samlede antal bits i den binære repræsentation. Alle højre / venstre skift & bitvise &, |, ~
osv operationer er ord niveau operationer, der udføres ekstremt effektivt af CPU. Derfor skal deres tidskompleksitet være O(1)
.
Metode 4 - Brug af XOR & Shifting-operationer:
Lad os betragte denne 8-bit binær repræsentation: 1010 0100
. Pariteten af dette tal er 1
. Hvad sker der, når vi foretager et højre skift på dette nummer ved at 4
& xor det med selve nummeret?
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)
I 4
bitene til højre er alle bitene indstillet, som er forskellige i n
& n >&
gt;> 4. Lad os nu koncentrere os om dette højre mest 4 gange ts o
: 1110, lad os glemme andre b i
ts. Now n is
1010 1110 & vi er bare koncentreret om de e
laveste 4 b its
dvs. 1110. Lad os lave en lidt s
kløft til højre ved n med 2.
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)
Bare koncentrer dig om 2
bitene til højre lige & glem alt om 6
bitene til venstre . Lad os højre skifte nummeret med 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)
Vi behøver ikke at rette skift længere, vi bare nu udtrække LSB bit, som er 1
i ovennævnte tilfælde og returnere resultatet: result = (short) n & 1
.
På et øjeblik ser løsningen måske lidt forvirrende ud, men den fungerer. Hvordan? Vi ved det 0 xor 1
eller 1 xor 0
er 1
, ellers 0
. Så når vi deler den binære repræsentation af et tal i to lige store halvdele efter længde, og vi gør xor
mellem dem, resulterer alle forskellige bitpar i sætbits i det xor-ed tal.
Da paritet opstår, når et ulige antal sætbits er der i den binære repræsentation, kan vi bruge xor
operationen til at kontrollere, om der findes et ulige antal 1
der. Derfor skifter vi højre til højre med halvdelen af det samlede antal cifre, vi, xor
der skiftede nummer med det oprindelige nummer, tildeler vi det xor-ed-resultat til det oprindelige nummer, og vi koncentrerer os kun om den højre halvdel af nummeret nu. Så vi xorer kun halvdelen af numrene ad gangen og reducerer vores omfang af xor. For 64
bit tal, begynder vi xor-behandling med 32
bit-halvdele, så 16
bit halvdele, så 8
, 4
, 2
, 1
hhv.
I det væsentlige betyder paritet af et tal paritet xor
med lige store halvdele af den binære repræsentation af dette tal. Det centrale i algoritmen er at koncentrere sig om yderste højre 32
bits først, derefter 16
, 8
, 4
, 2
, 1
bits & ignorere andre venstre side bits. Følgende er koden:

Fordele:
- Intet ekstra mellemrum bruger operationer på ordniveau til at beregne resultatet.
Ulemper:
- Det kan være lidt svært at forstå for udviklere.
Tidskompleksitet:
O(log n)
hvor n
er det samlede antal bits i den binære repræsentation.
Følgende er den fulde arbejdskode:
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)); } }
At lære af denne øvelse:
- Selvom det er grundlæggende viden, vil jeg nævne, at bitvise operationer på ordniveau er konstant i tiden.
- På en skala kan vi anvende caching ved at nedbryde den binære repræsentation i lige store halvdele af passende ordstørrelse som
16
i vores tilfælde, så vi kan rumme alle mulige tal i hukommelsen. Da vi formodes at håndtere millioner af numre, ender vi med at genbruge bitgrupper16
fra cache på tværs af tal. Ordstørrelsen behøver ikke nødvendigvis at være16
, det afhænger af dit krav og eksperimenter. - Du behøver ikke at gemme den binære repræsentation af et nummer i det separate array for at fungere på det, snarere smart brug af bitvise operationer kan hjælpe dig med at nå dit mål.
Referencer:
[1]. //stackoverflow.com/questions/2811319/difference-between-and
[2]. //gist.github.com/kousiknath/b0f5cd204369c5cd1669535cc9a58a53