أسرع طريقة للتحقق من الشرط l+1<r لـ int l,r في Java

Question

ما هي أسرع طريقة للتحقق من الحالة

l + 1 < r

ل int l,r في جاوة؟

l و r ليست ثابتة وأنا أعلم ذلك l <= r.المقارنة هي شرط التوقف ل while حلقة في تنفيذ البحث الثنائي.أقوم بالطبع بقياس الكود الخاص بي، سواء في اختبار منفصل (البحث في مصفوفة كبيرة) أو في الكود الذي يستخدمه.

ما أبحث عنه، كما أتخيل، هو نوع من العمليات التي ستكون أسرع من الوضع الحالي.لكنني لا أعرف.

Answer 1

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

و(لا علاقة لها: المثير للاهتمام أن نرى "ديف ضليع في الرياضيات" استخدام جافا راجع للشغل لا يحدث في كثير من الأحيان)

Answer 2

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

Answer 3

حسنًا، يجب أن تكون المقارنة الأساسية إما:

أضف 1 إلى l، وقارن النتيجة بـ r

أو

اطرح 1 من r وقارن النتيجة بـ l

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

الطريقة الوحيدة التي سيكون لها أي تأثير هي إذا:

أحد الثوابت l أو r معروفة في وقت الترجمة.على سبيل المثال.

l + 1 < 5
5 + 1 < r

في هذه الحالة، قد لا يدرك المترجم الضعيف الذي يعمل على تحسين الأداء أنه يمكنه تحويل الأول إلى l < 4

لكن الجميع مطلوب من مترجمي جافا اكتشاف أن الحالة الثانية هي 6 < r

والآخر هو إذا كان نوعي البيانات l و r مختلفين.

عملية :

1. إضافة/طرح النقطة العائمة ثم المقارنة بـ int
   الآيات
2. الجمع/الطرح التكاملي ثم المقارنة مع المضاعفة قد تكون مختلفة.

من العدل أن نقول إن فرص أن تكون هذه مشكلة خطيرة في طلبك ضئيلة للغاية نظرًا لأن تكلفة دورة أي منها صغيرة مقارنة بتدفق خط الأنابيب لأي توقعات خاطئة فرعية مرتبطة بالقرار.

كما يمكن لـ JIT اللائق إجراء جميع أنواع التحسينات فيما يتعلق بالكود المحيط الذي يفوق التحسين الجزئي الذي تم إجراؤه.

Answer 4

ويكون lr1 المتغير الذي يساوي دائما (l - r + 1). كلما زيادة أو إنقاص l، تفعل الشيء نفسه بالنسبة lr1. وبالمثل لr.

وبعد ذلك يصبح الاختبار (lr1 < 0)، وتعليمات لتعديل lr1 يتم تنفيذ أي أكثر في كثير من الأحيان أكثر من اللازم.

وأشعر سخيفة قليلا مما يتيح لك الأمثل الصغير، الذي هو بيني وبين الحكمة والجنيه أحمق، في معظم الحالات. مثل إذا كنت مقارنة السلاسل، وسوف تغرق تماما في هذا الاختبار.

وأضاف: منذ تفعلونه البحث الثنائي، وأود أن أذكر الفتح جون بنتلي بارد من البحث الثنائي. أولا عليك وحة A الجدول تصل إلى قوة 2، مثل 1024. ثم تكتب شيئا مثل هذا:

i = 0;
if (X >= A[i+512]) i += 512;
if (X >= A[i+256]) i += 256;
   . . .
if (X >= A[i+  1]) i +=   1;

وواختبار أخيرا إذا (X == A[i]). أو، إذا كنت لا ترغب في وسادة، والسماح البيانات if يكون شيء من هذا القبيل
if (i+512 < N && X >= A[i+512]) i += 512;

Answer 5

وماذا قال عن هؤلاء الرجال. المترجم هو الذهاب الى تحسين هذا بعيدا عنك. الكتابة عنها بحيث يبدو ويقرأ بشكل صحيح لك وعلى هذه الخطوة.

Answer 6

وأفضل رهان هو قرص JVM بدلا من رمز - نظرا إلى أن هذا هو عنق الزجاجة بك

وحاول بدء JVM مع -server -XX:+AggressiveOpts الحجج.

Answer 7

وماذا عن التحرك اختبار المساواة بك خارج حلقة في حين، لذلك عليك التحقق <م> .equals () إلا بعد إنهاء الخدمة. راجع للشغل لم أجد أي بت twiddling طرق لاختبار ما إذا كان ل + 1 <ص. إذا تعرف أطوال مجموعة الخاصة بك لتكون أقل من أحجام معينة، ما إذا كنت تستخدم نوع بيانات مختلفة لمؤشرات؟ شار / القصير / بايت؟