Declarație problemă:

Obțineți un flux de numere (să spunem long numerele de tip), calculați paritatea numerelor. Ipotetic, trebuie să serviți o scară imensă, cum ar fi 1 milion de numere pe minut. Proiectați un algoritm având în vedere o astfel de scară. Paritatea unui număr este 1 dacă numărul total de biți stabiliți în reprezentarea binară a numărului este impar, altfel paritatea este 0.

Soluţie:

Abordarea 1 – Forța brută:

Declarația problemei afirmă clar ce este paritatea. Putem calcula numărul total de biți stabiliți în reprezentarea binară a numărului dat. Dacă numărul total de biți setați este impar, paritatea este 1 altceva 0. Deci, metoda naivă este să continuați să faceți o schimbare dreaptă pe un anumit număr și să verificați bitul actual cel mai puțin semnificativ (LSB) pentru a urmări rezultatul.

Rezolvarea algoritmica a problemelor Cum se calculeaza eficient paritatea unui

În fragmentul de cod de mai sus, parcurgem toți biții din while bucla unul câte unul. Cu condiția ((no & 1) == 1) , verificăm dacă LSB curent este 1 sau 0 , dacă 1 , noi facem result ^= 1 . Variabila result este inițializat la 0 . Deci, atunci când o facem xor (^) operație între valoarea curentă a result & 1 , result va fi setat la 1 dacă result este în prezent 0 , in caz contrar 1 .

Dacă există un număr par de biți stabiliți, în cele din urmă result va deveni 0 deoarece xor între toți 1’s se vor anula reciproc. Dacă există un număr impar de 1’s, valoarea finală a result va fi 1. no >>> 1 dreapta deplasează biții cu 1.

>; >> este operatorul de deplasare dreapta logic în java care schimbă și bitul de semn (cel mai semnificativ bit dintr-un număr semnat). Există o altă opțiune de schimbare la dreaptaerator – >> care se numește drept aritmetic soperator rapid [see reference 1 at the last of the page]. Nu deplasează bitul de semn în reprezentarea binară – bitul de semn rămâne intact la poziția saition. FinalRezultatul & 0x1 returnează 1 dacă existăe este paritate sau 0 altfel.

Avantaje:

  1. Soluția este foarte ușor de înțeles și implementat.

Dezavantaje:

  1. Procesăm toți biții manual, astfel încât această abordare este dificilă la scară.

Complexitatea timpului: O(n) Unde n este numărul total de biți din reprezentarea binară a numărului dat.

Abordarea 2 – Ștergeți toți biții setați unul câte unul:

Există un blocaj în soluția de mai sus: while bucla în sine. Pur și simplu trece prin toți biții unul câte unul, chiar avem nevoie să facem asta? Preocuparea noastră este legată de biții setați, deci nu obținem niciun beneficiu trecând peste biții nesetați sau 0 biți. Dacă putem trece doar peste biți stabiliți, soluția noastră devine puțin mai optimizată. În calcul biți, dacă ni se dă un număr n, putem șterge bitul din dreapta setat cu următoarea operație:

n = n & (n-1)

Luați un exemplu: spuneți n = 40, reprezentarea binară în format pe 8 biți este: 00101000.

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

Am șters cu succes cel mai mic bit setat (al 4-lea bit din partea dreaptă). Dacă continuăm să facem acest lucru, numărul n va deveni 0 la un moment dat. Pe baza acestei logici, dacă calculăm paritatea, nu este nevoie să scanăm toți biții. Mai degrabă scanăm numai k biți unde k este numărul total de biți stabiliți în numărul & k <= length of the binary representation. Următorul este codul:

1612032728 653 Rezolvarea algoritmica a problemelor Cum se calculeaza eficient paritatea unui

Avantaje:

  1. Simplu de implementat.
  2. Mai eficient decât soluția de forță brută.

Dezavantaje:

  1. Nu este cea mai eficientă soluție.

Complexitatea timpului:

O(k) Unde k este numărul total de biți stabiliți în număr.

Abordarea 3 – Caching:

Uitați-vă încă o dată la enunțul problemei, cu siguranță există o preocupare cu privire la scară. Soluțiile noastre anterioare se pot extinde pentru a servi milioane de cereri sau există încă posibilități de a face mai bine?

Probabil putem face soluția mai rapidă dacă putem stoca rezultatul în memorie – cache. În acest fel putem salva unele cicluri de procesor pentru a calcula același rezultat. Deci, dacă numărul total de biți este 64 , de câtă memorie avem nevoie pentru a salva toate numerele posibile? 64 biți ne vor conduce să avem Math.pow(2, 64) posibile numere semnate (bitul cel mai semnificativ este utilizat pentru a stoca numai semn). Dimensiunea unui long numărul de tip este 64 biți sau 8 octeți, astfel încât dimensiunea totală a memoriei necesare este: 64 * Math.pow(2, 64) biți sau 134217728 TeraBytes. Acest lucru este prea mult și nu merită pentru a stoca o cantitate atât de mare de date. Putem face mai bine?

Putem sparge 64 numărul de biți într-un grup de 16 biți, preluați paritatea grupului individual de biți din cache și combinați-i. Această soluție funcționează deoarece 16 împarte 64 în 4 părți egale și suntem preocupați doar de numărul total de biți stabiliți. Deci, în măsura în care obținem paritatea grupului individual de biți, putem xor rezultatele lor între ele, din moment ce xor este asociativ și comutativ. Ordinea în care preluăm acele grupe de biți și le operăm nu contează nici măcar.

Dacă le stocăm 16 numere de biți ca număr întreg, memoria totală necesară este: Math.pow(2, 16) * 32 bits = 256 Kilo Bytes.

1612032728 469 Rezolvarea algoritmica a problemelor Cum se calculeaza eficient paritatea unui

În fragmentul de mai sus, schimbăm un grup de 16 bucăți de i * WORD_SIZE Unde
0 ≤ i ≤ 3 și faceți bitwise AND Operațiune (&) cu mask = 0xFFFF (0xFFFF = 1111111111111111 ) astfel încât să putem extrage cel mai dreapta 16 biți ca variabile întregi precum masked1, masked2 etc, trecem aceste variabile la o metodă checkAndSetInCache care calculează paritatea acestui număr în cazul în care nu este disponibil în cache. La final, o facem xor operație asupra rezultatului acestor grupe de numere care determină paritatea finală a numărului dat.

Avantaje:

  1. Cu prețul memoriei relativ mici pentru cache, obținem o eficiență mai bună, deoarece reutilizăm un grup de numere de 16 biți între intrări.
  2. Această soluție poate crește bine, deoarece servim milioane de numere.

Dezavantaje:

  1. Dacă acest algoritm trebuie implementat într-un dispozitiv de memorie ultra-scăzut, complexitatea spațiului trebuie să fie bine gândită în prealabil pentru a decide dacă merită să găzduiți o astfel de cantitate de spațiu.

Complexitatea timpului:

O(n / WORD_SIZE) Unde n este numărul total de biți din reprezentarea binară. Toate dreapta / stânga shift & bitwise &, |, ~ operațiile etc sunt operații la nivel de cuvânt care sunt realizate extrem de eficient de către CPU. Prin urmare, ar trebui să fie complexitatea lor de timp O(1).

Abordarea 4 – Utilizarea operațiunilor XOR și Shifting:

Să luăm în considerare această reprezentare binară pe 8 biți: 1010 0100. Paritatea acestui număr este 1. Ce se întâmplă când facem o schimbare dreaptă pe acest număr până la 4 & xor asta cu numărul în sine?

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)

În dreapta 4 biți, sunt setați toți biții care sunt diferiți în n & n >&gt;> 4. Acum să ne concentrăm asupra acestui drept majoritatea celor 4 bits only: 1110, să uităm de alte bits. Now n is 1010 1110 și suntem doar concentrați pe the cel mai mic 4 bits adică; 1110. Haideți să facem corect shift pe n de 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)

Concentrează-te doar pe cel din dreapta 2 biți acum și uitați de cel din stânga 6 biți. Să schimbăm dreapta numărul cu 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)

Nu mai trebuie să schimbăm dreapta, ci acum extragem bitul LSB care este 1 în cazul de mai sus și returnează rezultatul: result = (short) n & 1 .

Dintr-o privire, soluția ar putea părea puțin confuză, dar funcționează. Cum? Noi stim aia 0 xor 1 sau 1 xor 0 este 1, in caz contrar 0. Deci, atunci când împărțim reprezentarea binară a unui număr în două jumătăți egale cu lungimea și facem xor între ele, toate perechile diferite de biți rezultă în biți stabiliți în numărul xor-ed.

Deoarece paritatea apare atunci când există un număr impar de biți stabiliți în reprezentarea binară, putem folosi xor operație pentru a verifica dacă există un număr impar de 1 există acolo. Prin urmare, deplasăm dreapta numărul la jumătate din numărul total de cifre, noi xor acel număr mutat cu numărul original, atribuim rezultatul xor-ed la numărul original și ne concentrăm acum doar pe jumătatea din dreapta a numărului. Așadar, tocăm doar jumătate din numere la un moment dat și ne reducem domeniul de aplicare al xor. Pentru 64 numere de biți, începem să xoringăm cu 32 jumătăți de biți, atunci 16 jumătăți de biți, atunci 8, 4, 2, 1 respectiv.

În esență, paritatea unui număr înseamnă paritatea lui xor a jumătăților egale ale reprezentării binare a acelui număr. Punctul esențial al algoritmului este să ne concentrăm pe partea dreaptă 32 biți mai întâi, apoi 16, 8, 4 , 2 , 1 biți și ignorați alți biți din partea stângă. Următorul este codul:

1612032728 725 Rezolvarea algoritmica a problemelor Cum se calculeaza eficient paritatea unui

Avantaje:

  1. Niciun spațiu suplimentar nu folosește operații la nivel de cuvânt pentru a calcula rezultatul.

Dezavantaje:

  1. Ar putea fi puțin dificil de înțeles pentru dezvoltatori.

Complexitatea timpului:

O(log n) Unde n este numărul total de biți din reprezentarea binară.

Următorul este codul complet de lucru:

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] < 0) {
            cache[val] = computeParityBasedOnClearingSetBit(val);
        }
    }

    private static short computeParityMostEfficient(long no) {
        no ^= (no >>> 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));
    }
}

Învățând din acest exercițiu:

  1. Deși este vorba de cunoștințe de bază, vreau să menționez că operațiunile la nivel de cuvânt în mod biți sunt constante în timp.
  2. La o scară, putem aplica cache-ul prin descompunerea reprezentării binare în jumătăți egale cu dimensiunea cuvântului adecvat, cum ar fi 16 în cazul nostru, astfel încât să putem găzdui toate numerele posibile în memorie. Din moment ce ar trebui să gestionăm milioane de numere, vom ajunge să le refolosim 16 grupuri de biți din memoria cache între numere. Dimensiunea cuvântului nu trebuie neapărat să fie 16, depinde de cerințele și experimentele dvs.
  3. Nu este nevoie să stocați reprezentarea binară a unui număr în matricea separată pentru a opera pe acesta, o utilizare mai inteligentă a operațiilor în biți vă poate ajuta să vă atingeți ținta.

Referințe:

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

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