Algoritmisk problemløsning: Sådan beregnes pariteten af ​​en strøm af tal effektivt

Problemformulering:

Du får en strøm af tal (sig longtypetal), 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 1andet 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 whilesløjfen en efter en. Med betingelsen ((no & 1) == 1)kontrollerer vi, om den aktuelle LSB er, 1eller 0hvis 1vi gør det result ^= 1. Variablen resultinitialiseres til 0. Så når vi xor (^)opererer mellem den aktuelle værdi af result& 1, resultvil den blive indstillet til, 1hvis den resulter i øjeblikket 0, ellers 1.

Hvis der er et lige antal, der er bits, i sidste ende det resultvil blive 0, fordi xormellem alle 1’svil udligne hinanden. Hvis der er et ulige antal 1’s, vil den endelige værdi resultvære 1. no >>> 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 erskifteoperator - >>, 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. Finalaktuelle resultat, og 0x1 returnerer 1, hvis der eer paritet eller 0 på anden måde.

Fordele:

  1. Løsningen er meget let at forstå og implementere.

Ulemper:

  1. Vi behandler alle bits manuelt, så denne tilgang er næppe effektiv i skala.

Tidskompleksitet:O(n) hvor ner 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 whileslø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 0bits. 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 nvil blive 0på et bestemt tidspunkt. Baseret på denne logik, hvis vi beregner paritet, behøver vi ikke scanne alle bits. Snarere scanner vi kun kbits, hvor ker det samlede antal sæt bits i antallet & k <= length of the binary representation. Følgende er koden:

Fordele:

  1. Enkel at implementere.
  2. Mere effektiv end brute force-løsning.

Ulemper:

  1. Det er ikke den mest effektive løsning.

Tidskompleksitet:

O(k)hvor ker 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? 64bits 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 longtypenummer er 64bits eller 8bytes, 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 64bitsnummeret i en gruppe af 16bits, hente pariteten af ​​de individuelle grupper af bits fra cachen og kombinere dem. Denne løsning fungerer, fordi den 16opdeles 64i 4lige 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 xorderes resultater med hinanden, da det xorer associerende og kommutativt. Den rækkefølge, hvor vi henter den gruppe af bits og opererer dem, betyder ikke engang.

Hvis vi gemme disse 16bit 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 16bits efter i * WORD_SIZEhvor

0 ≤ i ≤ 3og udfør bitvis ANDbetjening ( &) med a mask = 0xFFFF( 0xFFFF = 1111111111111111 ), så vi bare kan udtrække de længste 16bit som heltalsvariabler som masked1, masked2osv. Vi sender disse variabler til en metode, checkAndSetInCacheder beregner pariteten af ​​dette nummer, hvis det ikke er tilgængeligt i cachen. I sidste ende udfører vi bare xorresultatet af denne gruppe af tal, der bestemmer den endelige paritet af det givne nummer.

Fordele:

  1. 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.
  2. Denne løsning kan skaleres godt, da vi betjener millioner af numre.

Ulemper:

  1. 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 ner 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 4bitene 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 its. Now n is 1010 1110 & vi er bare koncentreret om de elaveste 4 b its dvs. 1110. Lad os lave en lidt sklø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 2bitene til højre lige & glem alt om 6bitene 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 1i 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 1eller 1 xor 0er 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 xormellem 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 xoroperationen til at kontrollere, om der findes et ulige antal 1der. Derfor skifter vi højre til højre med halvdelen af ​​det samlede antal cifre, vi, xorder 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 64bit tal, begynder vi xor-behandling med 32bit-halvdele, så 16bit halvdele, så 8, 4, 2, 1hhv.

I det væsentlige betyder paritet af et tal paritet xormed lige store halvdele af den binære repræsentation af dette tal. Det centrale i algoritmen er at koncentrere sig om yderste højre 32bits først, derefter 16, 8, 4, 2, 1bits & ignorere andre venstre side bits. Følgende er koden:

Fordele:

  1. Intet ekstra mellemrum bruger operationer på ordniveau til at beregne resultatet.

Ulemper:

  1. Det kan være lidt svært at forstå for udviklere.

Tidskompleksitet:

O(log n)hvor ner 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:

  1. Selvom det er grundlæggende viden, vil jeg nævne, at bitvise operationer på ordniveau er konstant i tiden.
  2. På en skala kan vi anvende caching ved at nedbryde den binære repræsentation i lige store halvdele af passende ordstørrelse som 16i 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 bitgrupper 16fra cache på tværs af tal. Ordstørrelsen behøver ikke nødvendigvis at være 16, det afhænger af dit krav og eksperimenter.
  3. 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