Αλγοριθμική επίλυση προβλημάτων: Πώς να υπολογίσετε αποτελεσματικά την ισοτιμία μιας ροής αριθμών

Δήλωση προβλήματος:

Λαμβάνετε μια ροή αριθμών (ας πούμε longαριθμούς τύπου), υπολογίστε την ισοτιμία των αριθμών. Υποθετικά πρέπει να εξυπηρετήσετε μια τεράστια κλίμακα όπως 1 εκατομμύριο αριθμοί ανά λεπτό. Σχεδιάστε έναν αλγόριθμο λαμβάνοντας υπόψη τέτοια κλίμακα. Η ισοτιμία ενός αριθμού είναι 1 εάν ο συνολικός αριθμός των καθορισμένων bits στη δυαδική αναπαράσταση του αριθμού είναι περίεργος αλλιώς η ισοτιμία είναι 0.

Λύση:

Προσέγγιση 1 - Brute Force:

Η δήλωση προβλήματος αναφέρει σαφώς τι είναι η ισοτιμία. Μπορούμε να υπολογίσουμε τον συνολικό αριθμό των set bit στη δυαδική αναπαράσταση του δεδομένου αριθμού. Εάν ο συνολικός αριθμός των set bit είναι μονός, η ισοτιμία είναι 1διαφορετική 0. Έτσι, ο αφελής τρόπος είναι να συνεχίσετε να κάνετε μια σωστή στροφή δεξιά στον δεδομένο αριθμό και να ελέγξετε το τρέχον λιγότερο σημαντικό bit (LSB) για να παρακολουθείτε το αποτέλεσμα.

Στο παραπάνω απόσπασμα κώδικα, περνάμε όλα τα bit του whileβρόχου ένα προς ένα. Με τον όρο ((no & 1) == 1), ελέγχουμε αν το τρέχον LSB είναι 1ή 0, εάν 1, το κάνουμε result ^= 1. Η μεταβλητή resultαρχικοποιείται σε 0. Έτσι, όταν κάνουμε xor (^)μεταξύ της τρέχουσας αξίας resultκαι 1, το resultθα οριστεί 1αν το resultσήμερα 0, διαφορετικά 1.

Εάν υπάρχει ένας ζυγός αριθμός σετ bits, τελικά resultθα γίνει 0επειδή xorμεταξύ τους 1’sθα ακυρωθούν μεταξύ τους. Εάν υπάρχει μονός αριθμός 1’s, η τελική τιμή του resultθα είναι 1. no >>> 1 δεξιά αλλάζει τα bit κατά 1.

>; >> είναι λογικός χειριστής δεξιάς μετατόπισης σε java που μετατοπίζει επίσης το bit (το πιο σημαντικό bit σε έναν υπογεγραμμένο αριθμό). Υπάρχει μια άλλη επιλογή δεξιάς αλλαγής er- >> που ονομάζεται αριθμητικός χειριστής δεξιάς αλλαγής [βλ. Αναφορά 1 στο τμήμα της σελίδας]. Δεν μετατοπίζει το δυαδικό ψηφίο στη δυαδική αναπαράσταση - το δυαδικό ψηφίο παραμένει άθικτο στο ition. Finalαποτέλεσμα του και το 0x1 επιστρέφει 1 εάν υπάρχει eισοτιμία ή 0 διαφορετικά.

Πλεονεκτήματα:

  1. Η λύση είναι πολύ εύκολη στην κατανόηση και την εφαρμογή.

Μειονεκτήματα:

  1. Επεξεργαζόμαστε όλα τα κομμάτια με μη αυτόματο τρόπο, επομένως αυτή η προσέγγιση είναι σχεδόν αποδοτική σε κλίμακα.

Χρόνος πολυπλοκότητας:O(n) πού nείναι ο συνολικός αριθμός bit στη δυαδική αναπαράσταση του δεδομένου αριθμού.

Προσέγγιση 2 - Εκκαθάριση όλων των ρυθμίσεων bits ένα προς ένα:

Υπάρχει μια συμφόρηση στην παραπάνω λύση: ο whileίδιος ο βρόχος. Περνάει όλα τα κομμάτια ένα προς ένα, πρέπει πραγματικά να το κάνουμε αυτό; Η ανησυχία μας αφορά τα set bit, οπότε δεν παίρνουμε κανένα όφελος από την υπέρβαση των bit που δεν έχουν οριστεί 0. Εάν μπορέσουμε να ξεπεράσουμε μόνο τα κομμάτια, η λύση μας γίνεται λίγο πιο βελτιστοποιημένη. Στον bitwise υπολογισμό, εάν μας δοθεί ένας αριθμός n, μπορούμε να καθαρίσουμε το πιο δεξιό bit με την ακόλουθη λειτουργία

n = n & (n-1)

Πάρτε ένα παράδειγμα: ας πούμε n = 40, η δυαδική αναπαράσταση σε μορφή 8-bit είναι: 00101000.

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

Διαγράψαμε με επιτυχία το χαμηλότερο σετ bit (4ο bit από τη δεξιά πλευρά). Αν συνεχίσουμε να κάνουμε αυτό, ο αριθμός nθα γίνει 0σε μια συγκεκριμένη χρονική στιγμή. Με βάση αυτήν τη λογική, αν υπολογίσουμε την ισοτιμία, δεν χρειάζεται να σαρώσουμε όλα τα bit. Αντίθετα, σαρώνουμε μόνο kbits όπου kείναι ο συνολικός αριθμός των set bit στον αριθμό & k <= length of the binary representation. Ακολουθεί ο κωδικός:

Πλεονεκτήματα:

  1. Απλό στην εφαρμογή.
  2. Πιο αποτελεσματική από τη λύση ωμής δύναμης.

Μειονεκτήματα:

  1. Δεν είναι η πιο αποτελεσματική λύση.

Χρόνος πολυπλοκότητας:

O(k)πού kείναι ο συνολικός αριθμός των σετ bit στον αριθμό.

Προσέγγιση 3 - Προσωρινή αποθήκευση:

Κοιτάξτε για άλλη μια φορά τη δήλωση προβλήματος, σίγουρα υπάρχει ανησυχία για την κλίμακα. Μπορούν οι προηγούμενες λύσεις μας να εξυπηρετήσουν εκατομμύρια αιτήματα ή εξακολουθεί να υπάρχει περιθώριο να κάνουμε καλύτερα;

Μπορούμε πιθανώς να κάνουμε τη λύση γρηγορότερη αν μπορούμε να αποθηκεύσουμε το αποτέλεσμα στη μνήμη - προσωρινή αποθήκευση. Με αυτόν τον τρόπο μπορούμε να αποθηκεύσουμε μερικούς κύκλους CPU για να υπολογίσουμε το ίδιο αποτέλεσμα. Αν λοιπόν ο συνολικός αριθμός bits 64, πόση μνήμη χρειαζόμαστε για να αποθηκεύσουμε όλους τους πιθανούς αριθμούς; 64Τα bits θα μας οδηγήσουν να έχουμε Math.pow(2, 64)πιθανούς υπογεγραμμένους αριθμούς (το πιο σημαντικό bit χρησιμοποιείται για την αποθήκευση μόνο σημείου). Το μέγεθος ενός longαριθμού τύπου είναι 64bits ή 8byte, οπότε το συνολικό μέγεθος μνήμης που απαιτείται είναι: 64 * Math.pow(2, 64)bits ή 134217728 TeraBytes. Αυτό είναι πάρα πολύ και δεν αξίζει τον κόπο να αποθηκεύσετε τόσο τεράστια ποσότητα δεδομένων. Μπορούμε να κάνουμε καλύτερα;

Μπορούμε να χωρίσουμε τον 64αριθμό bit σε μια ομάδα 16bits, να πάρουμε την ισοτιμία αυτών των μεμονωμένων ομάδων bit από την προσωρινή μνήμη και να τα συνδυάσουμε. Αυτή η λύση λειτουργεί επειδή 16χωρίζεται 64σε 4ίσα μέρη και μας ενδιαφέρει ακριβώς ο συνολικός αριθμός των set bit. Όσο παίρνουμε την ισοτιμία αυτών των μεμονωμένων ομάδων bits, μπορούμε να έχουμε xorτα αποτελέσματά τους μεταξύ τους, δεδομένου ότι xorείναι συσχετιστική και μεταδοτική. Η σειρά με την οποία παίρνουμε αυτήν την ομάδα bits και λειτουργεί σε αυτά δεν έχει σημασία.

Αν αποθηκεύσετε αυτούς τους 16αριθμούς λίγο ως ακέραιος, απαιτείται συνολική μνήμη είναι: Math.pow(2, 16) * 32 bits = 256 Kilo Bytes.

Στο παραπάνω απόσπασμα, αλλάζουμε μια ομάδα 16bits από i * WORD_SIZEπού

0 ≤ i ≤ 3και κάνουμε τη ANDλειτουργία bitwise ( &) με ένα mask = 0xFFFF( 0xFFFF = 1111111111111111 ) έτσι ώστε να μπορούμε να εξαγάγουμε τα πιο δεξιά 16bit ως ακέραιες μεταβλητές όπως masked1, masked2κλπ., μεταδίδουμε αυτές τις μεταβλητές σε μια μέθοδο checkAndSetInCacheπου υπολογίζει την ισοτιμία αυτού του αριθμού σε περίπτωση που δεν είναι διαθέσιμη στην προσωρινή μνήμη. Στο τέλος, απλώς κάνουμε xorλειτουργία στο αποτέλεσμα αυτής της ομάδας αριθμών που καθορίζει την τελική ισοτιμία του δεδομένου αριθμού.

Πλεονεκτήματα:

  1. Με το κόστος της σχετικά μικρής μνήμης για την προσωρινή μνήμη, έχουμε καλύτερη απόδοση καθώς χρησιμοποιούμε μια ομάδα αριθμών 16-bit στις εισόδους.
  2. Αυτή η λύση μπορεί να κλιμακωθεί καθώς εξυπηρετούμε εκατομμύρια αριθμούς.

Μειονεκτήματα:

  1. Εάν αυτός ο αλγόριθμος πρέπει να εφαρμοστεί σε μια συσκευή εξαιρετικά χαμηλής μνήμης, η πολυπλοκότητα του χώρου πρέπει να μελετηθεί εκ των προτέρων για να αποφασίσει αν αξίζει τον κόπο να φιλοξενήσει τόσο μεγάλο χώρο.

Χρόνος πολυπλοκότητας:

O(n / WORD_SIZE)πού nείναι ο συνολικός αριθμός bits στη δυαδική αναπαράσταση. Όλες οι λειτουργίες δεξιάς / αριστεράς μετατόπισης & bitwise &, |, ~κλπ είναι λειτουργίες επιπέδου λέξεων που γίνονται εξαιρετικά αποτελεσματικά από την CPU Ως εκ τούτου, υποτίθεται ότι είναι η πολυπλοκότητα του χρόνου τους O(1).

Προσέγγιση 4 - Χρήση λειτουργιών XOR & Shifting:

Ας εξετάσουμε αυτό το 8-bit δυαδική αναπαράσταση: 1010 0100. Η ισοτιμία αυτού του αριθμού είναι 1. Τι συμβαίνει όταν κάνουμε μια σωστή μετατόπιση σε αυτόν τον αριθμό από 4& xor με τον ίδιο τον αριθμό;

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)

Στα δεξιότερα 4bit, όλα τα bit έχουν ρυθμιστεί που είναι διαφορετικά στο n& n >&gt;> 4. Τώρα ας επικεντρωθούμε σε αυτό το σωστό περισσότερο 4 φορές ts o: 1110, ας ξεχάσουμε για άλλα b its. Now n is 1010 1110 & είμαστε συγκεντρωμένοι στο eχαμηλότερο 4 b, its δηλαδή; 1110. Ας κάνουμε ένα δεξί δεξί sχτύπημα στο n με το 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)

Απλώς επικεντρωθείτε στα πιο δεξιά 2bit και ξεχάστε τα πιο αριστερά 6bits. Ας αλλάξουμε δεξιά τον αριθμό με 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)

Δεν χρειαζόμαστε προς τα δεξιά μετατόπιση πια, απλά τώρα εξάγει το LSB κομμάτι που είναι 1στην ανωτέρω περίπτωση και να επιστρέψει το αποτέλεσμα: 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. Σε μια κλίμακα, μπορούμε να εφαρμόσουμε την προσωρινή αποθήκευση χωρίζοντας τη δυαδική αναπαράσταση σε ίσα μισά κατάλληλου μεγέθους λέξεων όπως 16στην περίπτωσή μας, έτσι ώστε να μπορούμε να χωρέσουμε όλους τους πιθανούς αριθμούς στη μνήμη. Εφόσον υποτίθεται ότι χειριζόμαστε εκατομμύρια αριθμούς, θα καταλήξουμε να επαναχρησιμοποιήσουμε 16ομάδες bit από την προσωρινή μνήμη σε αριθμούς. Το μέγεθος της λέξης δεν χρειάζεται απαραίτητα 16, εξαρτάται από τις απαιτήσεις και τα πειράματά σας.
  3. Δεν χρειάζεται να αποθηκεύσετε τη δυαδική αναπαράσταση ενός αριθμού στον ξεχωριστό πίνακα για να λειτουργήσετε σε αυτόν, αλλά η έξυπνη χρήση λειτουργιών bitwise μπορεί να σας βοηθήσει να επιτύχετε τον στόχο σας.

Βιβλιογραφικές αναφορές:

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

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