المتوسط ​​السريع بدون قسمة

Question

لدي حلقة بحث ثنائية يتم ضربها عدة مرات في مسار التنفيذ.

يوضح ملف التعريف أن جزء التقسيم من البحث (العثور على الفهرس الأوسط بالنظر إلى المؤشرات العالية والمنخفضة لنطاق البحث) هو في الواقع الجزء الأكثر تكلفة من البحث، بعامل يبلغ حوالي 4.

(على ما أعتقد) ليس من الأهمية بمكان بالنسبة للبحث الثنائي الفعال العثور على القيمة الوسطى الدقيقة، بل مجرد قيمة قريبة من المنتصف والتي لا يوجد بها تحيز في أي من الاتجاهين.

هل هناك خوارزمية صغيرة لاستبدالها mid = (low + high) / 2 مع شيء أسرع بكثير؟

يحرر:اللغة هي C#، ولكن عملية البت المكافئة صالحة في أي لغة (على الرغم من أنها قد لا تكون ذات فائدة في الأداء)، ولهذا السبب تركت علامة C# معطلة.

Answer 1

int mid = (low + high) >>> 1;

انتبه إلى استخدام "(منخفض + مرتفع) / 2" لحسابات نقطة المنتصف لن تعمل بشكل صحيح عندما يصبح تجاوز عدد صحيح مشكلة.

Answer 2

فيما يلي نسخة مخترقة قليلاً من المتوسط ​​الذي لا يعاني من مشكلة الفائض:

unsigned int average (unsigned int x, unsigned int y)
{
  return (x&y)+((x^y)>>1);
}

Answer 3

يمكنك استخدام تبديل البت والتغلب أيضًا على مشكلة تجاوز السعة المحتملة:

low + ((high-low) >> 1)

ومع ذلك، يجب أن أعترف بأنني أتوقع من المترجمين والمترجمين الفوريين المعاصرين إجراء القسمة على 2 (أو القسمة على أي قوة ثابتة أخرى تبلغ 2) كتحويل للبت، لذا لست متأكدًا مما إذا كان ذلك سيساعد حقًا - جربه.

Answer 4

لمزيد من التوسع في إجابة نيلز ريتشارد شروبل اخترع هذا.

http://www.inwap.com/pdp10/hbaker/hakmem/boolean.html#item23

البند 23 (شروبل):

(أ و ب) + (أ أو ب) = أ + ب = (أ XOR ب) + 2 (أ و ب).

(A + B)/2 = ((A XOR B) + 2(A AND B))/2
          =  (A XOR B)/2  + (A AND B)
          =  (A XOR B)>>1 + (A AND B)


avg(x,y){return((x^y)>>1)+(x&y);}

(A AND B) + (A OR B) = A + B لأن A AND B يعطي مجموع القوى المشتركة (بين A و B) لاثنين، A OR B يعطي كلا من تلك المشتركة وتلك التي ليست كذلك، وبالتالي:

(A AND B) + (A OR B) = 
   (sum of shared powers of two) + 
   ((sum of shared powers of two) + (sum of unshared powers of two)) = 
     (sum of shared powers of two) + 
     ((sum of shared powers of two) + (sum of powers of two of A only) + 
     (sum of powers of two of B only)) = 
       ((sum of shared powers of two) + (sum of powers of two of A only)) + 
       ((sum of shared powers of two) + (sum of powers of two of B only)) 
= A + B. 

A XOR B يعطي خريطة لتلك البتات التي تختلف بين A وB.لذلك،

A XOR B = (sum of powers of two of A only) + (sum of powers of two of B only). 

وهكذا:

2(A AND B) + (A XOR B) = 
       ((sum of shared powers of two) + (sum of powers of two of A only)) + 
       ((sum of shared powers of two) + (sum of powers of two of B only)) 
= A + B.

Answer 5

إذا كنت أتذكر بشكل صحيح، هناك بعض الحالات التي يمكن أن يكون فيها استخدام منتصف المصفوفة أبطأ بالفعل.الحل هو اختيار الفهرس بشكل عشوائي حيث تقوم بتشطر المصفوفة.وينطبق الشيء نفسه على الخوارزمية لتحديد متوسط ​​​​المصفوفة.

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

Answer 6

جرب منخفض + ((مرتفع - منخفض) / 2)).من المفترض أن ينجح هذا لأنك تأخذ متوسط ​​رقمين فقط.سيؤدي هذا إلى تقليل مقدار الوقت الذي تستغرقه الخوارزمية إذا كانت قائمة البحث الثنائية كبيرة إلى حد ما، نظرًا لأن الارتفاع - المنخفض أصغر بكثير من الارتفاع + المنخفض.