Algoritmisko problēmu risināšana: kā efektīvi aprēķināt skaitļu plūsmas paritāti

Problēmas izklāsts:

Jūs saņemat skaitļu straumi (teiksim longtipa numurus), aprēķiniet skaitļu paritāti. Hipotētiski jums ir jāapkalpo milzīgs mērogs, piemēram, 1 miljons numuru minūtē. Izstrādājiet algoritmu, ņemot vērā šādu mērogu. Skaitļa paritāte ir 1, ja kopējais iestatīto bitu skaits skaitļa binārajā attēlojumā ir nepāra, pārējā paritāte ir 0.

Risinājums:

1. pieeja - brutāls spēks:

Problēmas izklāstā skaidri norādīts, kas ir paritāte. Mēs varam aprēķināt kopējo iestatīto bitu skaitu norādītā skaitļa binārā attēlojumā. Ja kopējais iestatīto bitu skaits ir nepāra, paritāte ir 1cita 0. Tātad naivais veids ir turpināt veikt mazliet gudru labo nobīdi uz norādītā numura un pārbaudīt pašreizējo vismazāk nozīmīgo bitu (LSB), lai sekotu rezultātam.

Iepriekš minētajā koda fragmentā mēs whilepa vienam pārdzīvojam visus cilpas bitus . Ar nosacījumu ((no & 1) == 1)mēs pārbaudām, vai pašreizējais LSB ir, 1vai 0, ja 1mēs to darām result ^= 1. Mainīgais resulttiek inicializēts 0. Tātad, kad mēs veiksim xor (^)darbību starp pašreizējo vērtību result& 1, resulttiks iestatīta vērtība, 1ja resultpašreiz ir 0, pretējā gadījumā 1.

Ja iestatīto bitu skaits ir pāra skaitlis, galu galā resulttas kļūs, 0jo xorstarp visiem 1’sviens otru atcels. Ja ir nepāra skaitlis 1’s, galīgā vērtība resultbūs 1. no >>> 1 pa labi pārvieto bitus par 1.

>; >> ir loģisks labās puses maiņas operators java, kas pārvieto arī zīmes bitu (nozīmīgākais bits parakstītā skaitlī). Ir vēl viens labās nobīdes eropors - >>, ko sauc par aritmētisko labo s pārbīdes operatoru [skat. 1. atsauci l . Tas nemaina zīmes bitu binārā attēlojumā - zīmes bits paliek neskarts pēc sava ition. Finalrezultāta un 0x1 atgriež 1, ja tur eir paritāte, vai 0 citādi.

Priekšrocības:

  1. Risinājums ir ļoti viegli saprotams un realizējams.

Trūkumi:

  1. Mēs visus bitus apstrādājam manuāli, tāpēc šī pieeja mērogā diez vai ir efektīva.

Laika sarežģītība:O(n) kur nir kopējais bitu skaits norādītā skaitļa binārā attēlojumā.

2. pieeja - notīriet visus iestatītos bitus pa vienam:

Iepriekš minētajā risinājumā ir whilevājš punkts: pati cilpa. Tas vienkārši iet pa visiem bitiem pa vienam, vai mums tas tiešām ir jādara? Mūsu rūpes ir par iestatītajiem bitiem, tāpēc mēs negūstam nekādas priekšrocības, pārkāpjot nenoteiktus bitus vai 0bitus. Ja mēs varam vienkārši pāriet tikai uz iestatītajiem bitiem, mūsu risinājums kļūst nedaudz optimizētāks. Aprēķinot bitiem, ja mums tiek piešķirts skaitlis n, mēs varam notīrīt labāko iestatīto bitu ar šādu darbību:

n = n & (n-1)

Ņemt piemēru: teikt n = 40, binārā pārstāvība 8 bitu formāts ir šāds: 00101000.

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

Mēs esam veiksmīgi notīrījuši zemāko iestatīto bitu (4. bits no labās puses). Ja turpināsim to darīt, skaitlis nkļūs 0noteiktā laika posmā. Pamatojoties uz šo loģiku, ja mēs aprēķinām paritāti, mums nav nepieciešams skenēt visus bitus. Drīzāk mēs skenējam tikai tos kbitus, kur kir kopējais iestatīto bitu skaits skaitlī & k <= length of the binary representation. Šis ir kods:

Priekšrocības:

  1. Vienkārši īstenojams.
  2. Efektīvāks nekā rupja spēka risinājums.

Trūkumi:

  1. Tas nav visefektīvākais risinājums.

Laika sarežģītība:

O(k)kur kir kopējais iestatīto bitu skaits skaitlī.

3. pieeja - kešatmiņa:

Vēlreiz apskatiet problēmas izklāstu, noteikti ir bažas par mērogu. Vai mūsu agrākie risinājumi var tikt apkalpoti miljoniem pieprasījumu, vai joprojām ir iespējas to darīt labāk?

Iespējams, ka risinājumu varam padarīt ātrāku, ja rezultātu varam saglabāt atmiņā - kešatmiņā. Tādā veidā mēs varam saglabāt dažus CPU ciklus, lai aprēķinātu to pašu rezultātu. Tātad, ja kopējais bitu skaits ir 64, cik daudz atmiņas mums nepieciešams, lai saglabātu visus iespējamos skaitļus? 64biti mums novedīs pie Math.pow(2, 64)iespējamiem parakstītiem numuriem (vissvarīgākais bits tiek izmantots tikai zīmes glabāšanai). longTipa numura lielums ir 64biti vai 8baiti, tāpēc kopējais nepieciešamais atmiņas lielums ir: 64 * Math.pow(2, 64)biti vai 134217728 TeraBytes. Tas ir par daudz un nav tā vērts, lai uzglabātu tik milzīgu datu daudzumu. Vai mēs varam darīt labāk?

Mēs varam sadalīt 64bitu skaitu 16bitu grupā, no kešatmiņas iegūt šo atsevišķo bitu grupas paritāti un apvienot tos. Šis risinājums darbojas, jo 16dala 64uz 4vienādās daļās un mēs esam nobažījušies tikai par kopējo skaitu noteiktos bitiem. Tātad, ciktāl mēs iegūstam šo atsevišķo bitu grupas paritāti, mēs varam xorto rezultātus savā starpā izmantot, jo tas xorir asociatīvs un komutatīvs. Kārtībai, kādā mēs ienesam šīs grupas bitus un operējam tos, pat nav nozīmes.

Ja mēs saglabājam šos 16bitu skaitļus kā vesels skaitlis, kopējā atmiņa nepieciešams, ir: Math.pow(2, 16) * 32 bits = 256 Kilo Bytes.

Iepriekš fragmentu, mēs maiņu grupu 16bitiem ar i * WORD_SIZEkur

0 ≤ i ≤ 3un veiciet ANDoperāciju bitā ( &) ar mask = 0xFFFF( 0xFFFF = 1111111111111111 ), lai mēs varētu vienkārši iegūt labākos 16bitus kā veselus skaitļus, piemēram, masked1, masked2utt., mēs šos mainīgos nododam metodei, checkAndSetInCachekas aprēķina šī skaitļa paritāti, ja tas nav pieejams kešatmiņā. Galu galā mēs vienkārši veicam xoroperāciju ar šīs skaitļu grupas rezultātu, kas nosaka norādītā skaitļa galīgo paritāti.

Priekšrocības:

  1. Par salīdzinoši nelielas kešatmiņas atmiņas cenu mēs iegūstam labāku efektivitāti, jo ievades laikā atkārtoti izmantojam 16 bitu skaitļu grupu.
  2. Šis risinājums var labi mērogot, jo mēs apkalpojam miljoniem numuru.

Trūkumi:

  1. Ja šis algoritms ir jāievieš īpaši zemas atmiņas ierīcē, iepriekš ir labi jāpārdomā telpas sarežģītība, lai izlemtu, vai ir vērts to uzņemt tik daudz vietas.

Laika sarežģītība:

O(n / WORD_SIZE)kur nir kopējais bitu skaits binārā attēlojumā. Visas labās / kreisās maiņas un bitu &, |, ~uc darbības ir vārdu līmeņa darbības, kuras CPU veic ārkārtīgi efektīvi. Tāpēc viņu laika sarežģītībai vajadzētu būt O(1).

4. pieeja - XOR un Shifting operāciju izmantošana:

Apskatīsim šo 8-bit binārā pārstāvību: 1010 0100. Šī skaitļa paritāte ir 1. Kas notiek, kad mēs veicam labo nobīdi šim skaitlim, 4& xor to izdarot ar pašu skaitli?

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 rightmost 4biti, visi biti ir komplekts, kas ir atšķirīgi n& n >&gt;> 4. Tagad koncentrēsimies uz šīm labākajām četrām ts olietām: 1110, aizmirsīsim par citām b its. Now n is 1010 1110 & mēs esam tikai koncentrējušies uz th ezemāko 4 b, its t.i. 1110. sVeicam bitu pa labi nobīdi uz n ar 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)

Vienkārši koncentrējieties uz labākajiem 2bitiem tagad un aizmirstiet par kreisākajiem 6bitiem. Pārejam pa labi pa labi 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)

Mums nav nepieciešams labo maiņu vairs, mēs tikai tagad ekstrakts LSB mazliet, kas ir 1arī konkrētajā gadījumā un atgriezties rezultāts: result = (short) n & 1.

At a glance, the solution might look a little confusing, but it works. How? We know that 0 xor 1 or 1 xor 0 is 1, otherwise 0. So when we divide the binary representation of a number into two equal halves by length & we do xor between them, all different pair of bits result into set bits in the xor-ed number.

Since parity occurs when an odd number of set bits are there in the binary representation, we can use xor operation to check if an odd number of 1 exists there. Hence we right shift the number by half of the total number of digits, we xor that shifted number with the original number, we assign the xor-ed result to the original number & we concentrate only on the rightmost half of the number now. So we are just xoring half of the numbers at a time & reduce our scope of xor. For 64 bit numbers, we start xoring with 32 bit halves, then 16 bit halves, then 8, 4, 2, 1 respectively.

Essentially, parity of a number means parity of xor of equal halves of the binary representation of that number. The crux of the algorithm is to concentrate on rightmost 32 bits first, then 16, 8, 4 , 2 , 1 bits & ignore other left side bits. Following is the code:

Advantages:

  1. No extra space uses word-level operations to compute the result.

Disadvantages:

  1. Might be little difficult to understand for developers.

Time Complexity:

O(log n) where n is the total number of bits in the binary representation.

Following is the full working code:

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

Learning from this exercise:

  1. Although it’s basic knowledge, I want to mention that word level bitwise operations is constant in time.
  2. Mērogā mēs varam piemērot kešatmiņu, sadalot bināro attēlojumu vienādās pusēs ar piemērotu vārda lielumu tāpat 16kā mūsu gadījumā, lai mēs varētu atmiņā ievietot visus iespējamos skaitļus. Tā kā mums vajadzētu apstrādāt miljoniem numuru, mēs galu galā atkārtoti izmantosim 16bitu grupas no kešatmiņas pāri numuriem. Vārda lielumam nav obligāti jābūt 16, tas ir atkarīgs no jūsu prasībām un eksperimentiem.
  3. Lai to darbinātu, jums nav jāuzglabā skaitļa binārs attēlojums atsevišķā masīvā, drīzāk gudra bitu darbību izmantošana var palīdzēt sasniegt jūsu mērķi.

Atsauces:

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

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