سواء كان ريتشارد هندريكس غبيًا أم بحثًا خطيًا مقابل ثنائي

أعتقد ، على هابري ، أنصار سلسلة وادي السيليكون . هذا الأسبوع ، ولأول مرة في الفصول الستة جميعها ، أظهروا رمزًا كبيرًا - بالطبع ، أود على الفور مناقشته هنا.

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

ريتشارد نفسه لا يجادل بأن الشفرة سيئة. ومع ذلك ، من بين مشاهدي المسلسل ، وجد قراره فجأة مدافعين ، وأنا الآن أتساءل ما الذي يفكر به هبر في موقفه.

يبدو مقتطف الشفرة المعروف ريتشارد كما يلي:

int index = 0; while (!element.equals(sortedList.get(index)) && sortedList.size() > ++index); return index < sortedList.size() ? index : -1; 

هنا ، يتحول البحث الخطي بدوره إلى كل عنصر من عناصر قائمة مرتبة ، حتى يصل إلى القائمة الصحيحة. وكقاعدة عامة ، يفضلون البحث الثنائي عن البيانات المصنفة ، والتي تقسم المجموعة في كل مرة ، مع تجاهل النصف غير المناسب ككل (لأنه مع زيادة حجم البيانات ، يزداد عدد التكرارات في الخطي بشكل أسرع من الرقم الثنائي). ولكن في subreddit / r / SiliconValleyHBO ، ظهر التعليق التالي:

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

هذا التقرير ممتع للغاية ويعرض بعض النتائج المذهلة لقياسات الأداء الحقيقية. "

وأيد أعضاء آخرون في الموضوع المعلق: نعم ، نظريًا ، كل التكرارات متكافئة ، ولكن على الأجهزة الحقيقية ذات التحسينات الحقيقية ، كل شيء مختلف تمامًا. على غرار ، عمل مؤلف السلسلة ، Mike Judge ، في الوادي في الثمانينيات ، عندما لم تكن كل مخابئ L1 والتوقعات الفرعية واضحة بشكل خاص ، لذلك كان سلوك وحدة المعالجة المركزية أقرب إلى النموذج المثالي - وهذا هو المثال في السلسلة.

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

لفهم ، فتحت تقريرًا استشهد به رديت. كما وعدت ، اتضح أنه مثير للاهتمام (ليس مفاجئًا ، نظرًا لأن هذا هو تقرير أعده Andrei Alexandrescu ) ، لكن بعد النظر إلى جزء والنقر على البقية ، لم أر قياسات مقارنة للبحث الثنائي والخطي هناك.

لكنني تذكرت أنه في مؤتمر DotNext ، تحدث نفس Alexandrescu أيضًا عن الأداء. لقد فتحت النسخة النصية من تقريره ، الذي قدمناه لـ Habr ، وبحثت عن كلمة "خطي". لقد اتضح ، من بين أشياء أخرى ، أنه أعطى مثالًا على سيناريو فضولي يكون فيه هذا البحث أكثر فاعلية من البحث الثنائي (البحث عن مطابقة عناصر مجموعتين في الحالة التي تكون فيها هذه المجموعات متطابقة) - لكن هذه حالة محددة للغاية ، ولا يوجد فيها استنتاج عام " يتم التقليل من البحث الخطي ".

غوغلد ما تقوله الإنترنت الحديثة حول هذا - ولكن وجدت أساسا إجابات ل Stack Overflow ، حيث يكتبون ببساطة "استخدام التكرار ، وتقليل التكرارات". كانت هناك أيضًا حالات حاولوا فيها قياس الأداء ، لكنهم لم يبدوا مقنعين للغاية بالنسبة لي.

هنا ، بطبيعة الحال ، فإن الخيار يطرح "عليك تقييم نفسك من أجل رؤية كل شيء بنفسك على الأجهزة الحقيقية."

ولكن إذا كانت كل زياراتي إلى DotNext قد تعلمت شيئًا من اثنين من Andreevs الواعين بالأداء (Alexandrescu و Akinshina ) ، فهذا إدراك لمدى قياس الأشخاص بشكل غير صحيح ومقدار عدم أخذهم في الاعتبار. لذلك ، لدي ثقة منخفضة في مشاركات الإنترنت العشوائية ذات المعايير ، ولكن بنفسي أقل.

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

وإذا لم يكن هناك معلقون على دراية ، فسوف يتعين علي توصيل Akinshin بالبطارية في DotNext التالي وإجراء الاختبار.