Algoritmiline ülesannete lahendamine: kuidas arvude voo pariteeti tõhusalt arvutada

Probleemipüstituses:

Saate numbrivoo (ütleme longtüübinumbrid), arvutage numbrite pariteet. Hüpoteetiliselt peate teenima suurt hulka, näiteks 1 miljon numbrit minutis. Koostage selline skaala järgi algoritm. Numbri pariteet on 1, kui arvu binaarses esituses olevate bittide koguarv on paaritu, muidu on pariteet 0.

Lahendus:

1. lähenemine - jõhker jõud:

Probleemilause ütleb selgelt välja, mis on pariteet. Saame arvutada hulga bittide koguarvu antud numbri kahendobjektis. Kui määratud bittide koguarv on paaritu, on pariteet 1muu 0. Niisiis on naiivne viis jätkata antud numbri jaoks natuke mõistlikku parempoolset nihet ja tulemuse jälgimiseks kontrollida praegust kõige vähem olulist bitti (LSB).

Ülaltoodud koodijupis läbime kõik whilesilmus olevad bitid ükshaaval. Tingimusega ((no & 1) == 1)kontrollime, kas praegune LSB on, 1või 0kui 1, siis on result ^= 1. Muutuja resultlähtestatakse väärtusele 0. Nii et kui me teeme xor (^)operatsiooni vahel praegune väärtus resultja 1on resultseatakse 1kui resulton praegu 0, muidu 1.

Kui seatud bitte on paarisarv, siis lõpuks resultmuutub see 0seetõttu, xoret kõigi vahel 1’stühistatakse üksteist. Kui on paaritu arv 1’s, lõplik väärtus resulton 1. no >>> 1 paremal nihutab bitte 1 võrra.

>; >> on Java-s loogiline parempoolse nihkeoperaator, mis nihutab ka märgibitti (kõige olulisem bit allkirjastatud numbris). On veel üks parempoolse nihke op erator - >>, mida nimetatakse aritmeetiliseks parempoolse nihkeoperaatoriks (vt viidet 1 lehe lõpus ). See ei nihku märk natuke binaarsete - märk natuke jääb puutumata selle pos ition. Finally tulemuseks & 0x1 tagastab 1, kui seal eon pariteedi või 0 teisiti.

Eelised:

  1. Lahendust on väga lihtne mõista ja rakendada.

Puudused:

  1. Töötleme kõiki bitte käsitsi, nii et see lähenemine on mastaabis vaevalt tõhus.

Aja keerukus:O(n) kus non antud arvu binaarse esituse bittide koguarv.

2. lähenemine - tühjendage kõik määratud bitid ükshaaval:

Ülaltoodud lahenduses on kitsaskoht: whilesilmus ise. See lihtsalt läbib kõik bitid ükshaaval, kas me peame seda tõesti tegema? Meie mure on seatud bittide pärast, nii et me ei saa mingeid eeliseid, kui läheme üle määramata 0bittidest. Kui saame lihtsalt üle minna ainult seatud bitti, muutub meie lahendus veidi optimeeritumaks. Kui meile antakse number n, saab bitipõhises arvutuses järgmise operatsiooniga kustutada parempoolseima hulga biti:

n = n & (n-1)

Võtke näiteks: öelda n = 40, binaarsete 8-bit on: 00101000.

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

Oleme edukalt tühjendanud madalaima seatud biti (4. bit paremalt küljelt). Kui me hoiame seda teed arv nmuutub 0teatud ajahetkel. Selle loogika põhjal ei pea pariteedi arvutamisel kõiki bitte skannima. Pigem skannime ainult neid kbitte, kus kon määratud bittide koguarv arvus & k <= length of the binary representation. Järgmine on kood:

Eelised:

  1. Lihtne rakendada.
  2. Tõhusam kui toore jõu lahendus.

Puudused:

  1. See pole kõige tõhusam lahendus.

Aja keerukus:

O(k)kus kon arvus olevate määratud bitide koguarv.

3. lähenemine - vahemällu salvestamine:

Vaadake veel kord probleemi avaldust, mure on kindlasti mastaapsuse pärast. Kas meie varasemad lahendused suudavad teenida miljoneid taotlusi või on ikka veel võimalusi paremat teha?

Tõenäoliselt suudame lahenduse kiiremini teha, kui suudame tulemuse mällu salvestada - vahemällu salvestamine. Nii saame sama tulemuse arvutamiseks salvestada mõned protsessori tsüklid. Nii et kui bittide koguarv on 64, siis kui palju mälu on vaja kõigi võimalike arvude salvestamiseks? 64bittide abil on meil Math.pow(2, 64)võimalikud allkirjastatud numbrid (kõige olulisemat bitti kasutatakse ainult märgi salvestamiseks). Tüübinumbri suurus longon 64bitti või 8baiti, seega on vajalik kogu mälumaht: 64 * Math.pow(2, 64)bitti või 134217728 TeraBytes. See on liiga palju ja pole seda väärt, et nii tohutult palju andmeid salvestada. Kas saaksime paremini hakkama?

Saame jagada 64bittide arvu bittide rühmaks 16, tuua vahemälust nende üksikute bittide rühma pariteedi ja kombineerida neid. See lahendus töötab, sest 16jagab 64arvesse 4võrdsetes osades ja oleme mures peaaegu koguarvust komplekt bitti. Niipalju kui saame üksikute bittide rühma pariteeti, saame xornende tulemusi omavahel kasutada, kuna see xoron assotsiatiivne ja kommutatiivne. See, millises järjekorras me nende bittide rühma toome ja neid opereerime, pole isegi oluline.

Kui me salvestada neid 16natuke numbreid täisarv, kokku vajatava mälu on: Math.pow(2, 16) * 32 bits = 256 Kilo Bytes.

Eespool katkendi muudame rühm 16bitti i * WORD_SIZE, kus

0 ≤ i ≤ 3ja teha bitwise ANDoperatsiooni ( &) koos mask = 0xFFFF( 0xFFFF = 1111111111111111 ), et saaksime lihtsalt eraldada parempoolsem 16bitti nagu täisarv muutujad nagu masked1, masked2jne, võtame need muutujad meetodit checkAndSetInCache, mis arvutab paarsuse see number, kui see ei ole kättesaadav vahemälu. Lõpuks teeme lihtsalt xornende arvude rühma tulemuse, mis määrab antud numbri lõpliku pariteedi.

Eelised:

  1. Vahemälu suhteliselt väikese mälu hinnaga saame parema efektiivsuse, kuna taaskasutame sisendites 16-bitiste arvude rühma.
  2. Selle lahendusega saab hästi hakkama, kui teenindame miljoneid numbreid.

Puudused:

  1. Kui see algoritm tuleb rakendada ülimadalas mäluseadmes, tuleb ruumi keerukus eelnevalt hästi läbi mõelda, et otsustada, kas tasub sellesse ruumi mahutada.

Aja keerukus:

O(n / WORD_SIZE)kus non binaarses esinduses olevate bitide koguarv. Kõik parempoolsed / vasakpoolsed nihked ja bitipidi &, |, ~jne toimingud on sõnataseme operatsioonid, mida protsessor teeb äärmiselt tõhusalt. Seega peaks nende ajaline keerukus olema O(1).

Lähenemisviis 4 - XOR- ja Shifting-toimingute kasutamine:

Vaatleme seda 8-bitine kahendkujul: 1010 0100. Selle numbri pariteet on 1. Mis juhtub, kui teeme sellele numbrile parema nihke 4& xori võrra, ise numbri järgi?

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)

In parempoolsemale 4bitti, kõik bitid, mis on erinev n& n >&gt;> 4. Keskendume nüüd sellele paremale neljal juhul ts o: 1110, unustagem muud b its. Now n is 1010 1110 & me oleme lihtsalt keskendunud ekõige madalamale 4 b, its st. 1110. Teeme n-l 2-ga parempoolse parema snihke .

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)

Keskenduge lihtsalt parempoolsematele 2bitidele ja unustage vasakpoolsed 6bitid. Nihutame numbrit paremale 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)

Me ei pea paremale nihe enam, me just praegu väljavõtte LSB bitist mis on 1eespool nimetatud kohtuasjas ja tagastab tulemuse: result = (short) n & 1.

Lühidalt võib lahendus tunduda veidi segane, kuid see töötab. Kuidas? Me teame seda 0 xor 1või 1 xor 0on 1, muidu 0. Niisiis, kui jagame arvu binaarse esituse pikkuse järgi kaheks võrdseks pooleks ja me teeme nende xorvahel, siis kõik erinevad bittide paarid moodustavad x-ed-arvus hulga bitte.

Kuna pariteet tekib siis, kui binaaresinduses on paaritu arv määratud bitte, saame xoroperatsiooni abil kontrollida, kas seal on paaritu arv 1. Seega nihutame numbrit paremal poole numbri koguarvust, meie, xorkes nihutasime numbri koos algse numbriga, määrasime x-ed-i tulemuse algsele numbrile ja keskendume nüüd ainult numbri parempoolsemale poolele. Seega xorime lihtsalt pooled arvud korraga ja vähendame xori ulatust. Sest 64natuke numbreid, hakkame xoring koos 32natuke pooleks, siis 16bitt pooleks, siis 8, 4, 2, 1vastavalt.

Põhimõtteliselt tähendab arvu pariteet xorselle numbri binaarse esituse võrdsete poolte pariteeti . Tuum algoritm on keskenduda parempoolsem 32bitti, seejärel 16, 8, 4, 2, 1bitid ja ignoreerida teisi vasakul küljel bitti. Järgmine on kood:

Eelised:

  1. Ükski lisaruum ei kasuta tulemuse arvutamiseks sõnataseme operatsioone.

Puudused:

  1. Arendajatele võib see olla pisut raskesti mõistetav.

Aja keerukus:

O(log n)kus non binaarses esinduses olevate bitide koguarv.

Järgmine on täielik töökood:

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)); } }

Sellest harjutusest õppimine:

  1. Kuigi see on põhiteadmine, tahan mainida, et sõnataseme bitipõhised toimingud on ajas konstantsed.
  2. Skaalal saame vahemälu rakendada, jagades binaarse kujutise võrdse poolega sobivast sõnamõõdust nagu 16meie puhul, et saaksime mällu mahutada kõik võimalikud numbrid. Kuna me peaksime käsitsema miljoneid numbreid, kasutame lõpuks 16vahemälu bitirühmi numbrite vahel. Sõna suurus ei pea tingimata olema 16, see sõltub teie nõudest ja katsetest.
  3. Selle kasutamiseks ei pea numbri binaarset esindust eraldi massiivi salvestama, pigem võib bitipõhiste toimingute nutikas kasutamine aidata teil eesmärgi saavutada.

Viited:

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

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