حل مشكلة الخوارزمية: كيفية حساب تكافؤ تدفق الأرقام بكفاءة

عرض المشكلة:

أنت تحصل على دفق من الأرقام (لنقل longأرقام النوع) ، احسب تكافؤ الأرقام. من الناحية الافتراضية ، عليك أن تقدم نطاقًا ضخمًا مثل مليون رقم في الدقيقة. تصميم خوارزمية تأخذ في الاعتبار هذا النطاق. تكافؤ رقم هو 1 إذا كان العدد الإجمالي للبتات المحددة في التمثيل الثنائي للرقم هو تكافؤ فردي ، وإلا يكون التكافؤ 0

المحلول:

المقاربة 1 - القوة الغاشمة:

بيان المشكلة يوضح ما هو التكافؤ. يمكننا حساب العدد الإجمالي للبتات المحددة في التمثيل الثنائي للرقم المحدد. إذا كان العدد الإجمالي للبت تعيين الغريب، والتكافؤ هو 1آخر 0. لذا فإن الطريقة الساذجة هي الاستمرار في إجراء تحول صحيح قليلاً على الرقم المحدد والتحقق من أقل بت حالي (LSB) لتتبع النتيجة.

في مقتطف الشفرة أعلاه ، نتصفح جميع البتات في whileالحلقة واحدة تلو الأخرى. مع الشرط ((no & 1) == 1)، نتحقق مما إذا كان LSB الحالي هو ، 1أو 0إذا 1فعلنا ذلك result ^= 1. resultيتم تهيئة المتغير إلى 0. لذلك عندما نجري xor (^)العملية بين القيمة الحالية لـ result& 1، resultفسيتم تعيين القيمة 1إذا كانت resultحاليًا 0، وإلا 1.

إذا كان هناك عدد زوجي من البتات المحددة ، resultفستصبح في النهاية 0لأن xorبين الكل 1’sسيلغي بعضها البعض. إذا كان هناك رقم فردي 1’s، resultفستكون القيمة النهائية لـ 1. no >&gt ؛> 1 يمينًا ينقل البتات بمقدار 1.

>؛ >> هو عامل النقل الصحيح المنطقي في جافا والذي يغير بت الإشارة (أهم بت في رقم موقّع) أيضًا. هناك عملية إزاحة أخرى لليمين er- >> والتي تسمى عامل الارتفاع الأيمن الحسابي [انظر المرجع 1 في الجزء الأول من الصفحة]. لا يقوم بإزاحة بتة الإشارة في التمثيل الثنائي - تظل بتة الإشارة سليمة في ition. Finalالنتيجة النهائية الخاصة بها & 0x1 ترجع 1 إذا كان هناك eتكافؤ أو 0 بخلاف ذلك.

مزايا:

  1. الحل سهل الفهم والتنفيذ.

سلبيات:

  1. نحن نعالج جميع البتات يدويًا ، لذا فإن هذا الأسلوب بالكاد يكون فعالًا على نطاق واسع.

تعقيد الوقت:O(n) أين nهو العدد الإجمالي للبتات في التمثيل الثنائي للرقم المحدد.

النهج 2 - امسح كل وحدات البت واحدة تلو الأخرى:

هناك عنق زجاجة في الحل أعلاه: whileالحلقة نفسها. إنها تمر عبر كل الأجزاء واحدة تلو الأخرى ، هل نحتاج حقًا إلى القيام بذلك؟ ينصب اهتمامنا على البتات المحددة ، لذلك لا نحصل على أي فوائد من خلال تجاوز البتات أو 0البتات غير المحددة. إذا تمكنا من تجاوز البتات المحددة فقط ، فسيصبح الحل الذي نقدمه أكثر تحسينًا. في الحساب الأحادي ، إذا تم إعطاؤنا رقمًا n، فيمكننا مسح أقصى مجموعة بت بالعملية التالية:

n = n & (n-1)

نأخذ مثالا على ذلك: يقول n = 40، تمثيل ثنائي في شكل 8 بت هو: 00101000.

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

لقد نجحنا في مسح أقل مجموعة بت (بت 4 من الجانب الأيمن). إذا واصلنا القيام بذلك ، nفسيصبح الرقم 0في وقت معين. بناءً على هذا المنطق ، إذا قمنا بحساب التكافؤ ، فلن نحتاج إلى مسح كل البتات. بدلاً من ذلك ، نقوم بمسح kالبتات فقط حيث kيكون العدد الإجمالي للبتات المحددة في الرقم & k <= length of the binary representation. فيما يلي الكود:

مزايا:

  1. سهل التنفيذ.
  2. أكثر كفاءة من حل القوة الغاشمة.

سلبيات:

  1. إنه ليس الحل الأكثر فعالية.

تعقيد الوقت:

O(k)أين kهو العدد الإجمالي للبتات المحددة في العدد.

النهج 3 - التخزين المؤقت:

انظر إلى بيان المشكلة مرة أخرى ، هناك بالتأكيد قلق بشأن الحجم. هل يمكن أن تتسع حلولنا السابقة لخدمة ملايين الطلبات أم لا يزال هناك أي مجال للقيام بعمل أفضل؟

ربما يمكننا جعل الحل أسرع إذا تمكنا من تخزين النتيجة في الذاكرة - التخزين المؤقت. بهذه الطريقة يمكننا حفظ بعض دورات وحدة المعالجة المركزية لحساب نفس النتيجة. لذا إذا كان العدد الإجمالي للبتات هو 64، ما مقدار الذاكرة التي نحتاجها لحفظ كل الأرقام الممكنة؟ 64ستقودنا وحدات البت إلى الحصول على Math.pow(2, 64)أرقام موقعة محتملة (يتم استخدام البت الأكثر أهمية لتخزين الإشارة فقط). حجم longرقم النوع هو 64بت أو 8بايت ، لذا فإن إجمالي حجم الذاكرة المطلوب هو: 64 * Math.pow(2, 64)بت أو 134217728 TeraBytes. هذا كثير جدًا ولا يستحق تخزين مثل هذا الكم الهائل من البيانات. هل يمكننا أن نفعل ما هو أفضل؟

يمكننا تقسيم 64رقم البتات إلى مجموعة من 16البتات ، وجلب التكافؤ بين تلك المجموعة الفردية من البتات من ذاكرة التخزين المؤقت ودمجها. يعمل هذا الحل لأنه 16ينقسم 64إلى 4أجزاء متساوية ونحن مهتمون فقط بالعدد الإجمالي للبتات المحددة. وبقدر ما نحصل على التكافؤ بين تلك المجموعة الفردية من البتات ، فيمكننا أن نحصل xorعلى نتائج مع بعضنا البعض ، نظرًا لأنها xorترابطية وتبادلية. الترتيب الذي نحضر به تلك المجموعة من البتات ونعمل عليها لا يهم حتى.

إذا نقوم بتخزين تلك 16الأرقام قليلا كعدد، تتطلب الذاكرة الإجمالية هو: Math.pow(2, 16) * 32 bits = 256 Kilo Bytes.

في المقتطف أعلاه ، نحول مجموعة من 16البتات حسب i * WORD_SIZEالمكان

0 ≤ i ≤ 3ونفّذ ANDعملية البت ( &) باستخدام mask = 0xFFFF( 0xFFFF = 1111111111111111 ) حتى نتمكن فقط من استخراج 16البتات الموجودة في أقصى اليمين كمتغيرات عددية مثل masked1, masked2الخ ، نقوم بتمرير هذه المتغيرات إلى طريقة checkAndSetInCacheتحسب تكافؤ هذا الرقم في حالة عدم توفره في ذاكرة التخزين المؤقت. في النهاية ، نقوم xorبعملية فقط على نتيجة هذه المجموعة من الأرقام التي تحدد التكافؤ النهائي للرقم المحدد.

مزايا:

  1. على حساب ذاكرة صغيرة نسبيًا لذاكرة التخزين المؤقت ، نحصل على كفاءة أفضل نظرًا لأننا نعيد استخدام مجموعة من الأرقام ذات 16 بت عبر المدخلات.
  2. يمكن لهذا الحل أن يتوسع جيدًا لأننا نخدم ملايين الأرقام.

سلبيات:

  1. إذا كانت هذه الخوارزمية بحاجة إلى أن يتم تنفيذها في جهاز ذاكرة منخفض للغاية ، فيجب التفكير جيدًا في تعقيد المساحة مسبقًا من أجل تحديد ما إذا كان الأمر يستحق استيعاب هذا القدر من المساحة.

تعقيد الوقت:

O(n / WORD_SIZE)أين nهو العدد الإجمالي للبتات في التمثيل الثنائي. جميع عمليات التحول لليمين / اليسار &, |, ~والعمليات الخاصة بالبت وما إلى ذلك هي عمليات على مستوى الكلمات تتم بكفاءة عالية بواسطة وحدة المعالجة المركزية. ومن ثم من المفترض أن يكون تعقيد وقتهم O(1).

النهج 4 - استخدام عمليات XOR & Shifting:

دعونا النظر في هذا تمثيل ثنائي 8 بت: 1010 0100. التكافؤ في هذا الرقم 1. ماذا يحدث عندما نقوم بإزاحة صحيحة على هذا الرقم بواسطة 4& x أو مع الرقم نفسه؟

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)

في 4البتات الموجودة في أقصى اليمين ، يتم تعيين جميع البتات التي تختلف في n& n >&GT ؛> 4. الآن دعونا نركز على هذا بشكل صحيح 4 مرات ts o: 1110 ، دعونا ننسى أمر b its الأخرى . Now n is 1010 1110 ونحن نركز فقط على eأدنى 4 ب its أي ؛ 1110. ودعونا القيام الصحيحة المختصة بالبت shift على ن ب 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)

ركز فقط على 2البتات الموجودة في أقصى اليمين الآن وتنسى 6البتات الموجودة في أقصى اليسار . دعنا نحول الرقم بشكل صحيح من خلال 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.

في لمحة ، قد يبدو الحل مربكًا بعض الشيء ، لكنه يعمل. كيف؟ نحن نعلم ذلك 0 xor 1أو 1 xor 0غير 1ذلك 0. لذلك عندما نقسم التمثيل الثنائي لرقم ما إلى نصفين متساويين حسب الطول ونفعل xorبينهما ، ينتج عن كل زوج مختلف من البتات مجموعة بتات في عدد xor-ed.

نظرًا لأن التكافؤ يحدث عندما يوجد عدد فردي من وحدات البت في التمثيل الثنائي ، يمكننا استخدام xorالعملية للتحقق مما إذا كان هناك عدد فردي من وحدات البت 1. ومن ثم نقوم بتحويل الرقم إلى النصف من العدد الإجمالي للأرقام ، نحن xorالذين قمنا بتغيير الرقم مع الرقم الأصلي ، قمنا بتعيين النتيجة xored إلى الرقم الأصلي ونركز فقط على النصف الأيمن من الرقم الآن. لذلك نحن نقوم فقط بتقليل نصف الأرقام في وقت واحد وتقليل نطاق xor. لل 64أرقام بعض الشيء، ونبدأ xoring مع 32نصفي قليلا، ثم 16بت نصفين، ثم 8، 4، 2، 1على التوالي.

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مجموعات البت من ذاكرة التخزين المؤقت عبر الأرقام. لا يلزم بالضرورة أن يكون حجم الكلمة كذلك 16، فهذا يعتمد على متطلباتك وتجاربك.
  3. لا تحتاج إلى تخزين التمثيل الثنائي لرقم في مصفوفة منفصلة لتعمل عليه ، بدلاً من ذلك ، يمكن أن يساعدك الاستخدام الذكي لعمليات البت في تحقيق هدفك.

المراجع:

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

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