Andrei Alexandrescu هو أسطورة حية حقيقية. هذا هو الشخص الذي قدم مساهمة كبيرة في تاريخ لغات البرمجة الحديثة وتقنيات التعميم والمخططات. كم عدد النسخ التي تم كسرها في مناقشات
تصميم C ++ الحديث ومعايير الترميز 101 (مكتوبة باستخدام شعار Sutter's استثنائي C ++ Coat of Arms) ، وغيرها من
الكتب والمقالات . بصفته مؤلفًا مشاركًا
للغة د ، فقد أتيحت له الفرصة ليس فقط للتنظير ، ولكن أيضًا لجعل حلمه حقيقة - وهو ما يميزه.
الآن أنت تحمل بين يديه
تقريرًا من مؤتمر DotNext 2018 Piter ، الذي يتحدث عن تقنيات التحسين الحديثة. ما علاقة .NET به؟ هذا تقرير أساسي من شخص كان يعمل على تحسين حياته كلها. إذا كان الأداء مهمًا بالنسبة لك ، فأنت بحاجة إلى مشاهدته (أو قراءة هذا المقال). مرحبًا بك في القط!
فن القياس
أود أن أناقش معك العديد من الموضوعات المتعلقة بقياس الأداء. للبدء ، دعنا نكرر بعض الأشياء الأساسية.
يعد قانون أمدل جزءًا من كلاسيكيات علوم الكمبيوتر ، ويستخدم بشكل أساسي في الحوسبة المتوازية ، ولكنه يعمل في أي نظام معقد. إذا أردنا تحسين عمل نظام معين ، فعلينا أن نبدأ حيث تتركز المشاكل الرئيسية لهذا النظام. القانون نفسه واضح: إذا كان المكون هو 20 ٪ من النظام ، فإن الحد الأقصى للتحسين في أداء النظام الذي يمكن تحقيقه من خلال تحسين تشغيل هذا المكون فقط هو 20 ٪. في كثير من الأحيان يجب أن أقابل أشخاصًا (بالطبع ، لا ينتمي القراء إليهم) الذين يقومون بأشياء مثل تحسين تحليل سطر الأوامر. تستغرق هذه العمليات أول 10 ميكروثانية من برنامجك ، ويحلل الناس تعقيدها الخوارزمي ويصابون بالرعب إذا كان الوقت تربيعيًا.
كما تعلم على الأرجح ، قبل البدء في التحسين ، من الضروري تحديد الملف الشخصي للتطبيق وتحديد النقاط الساخنة فيه. هنا يجب أن يقال عن
قانون Ladma (هذا ليس لقبًا حقيقيًا ، و Amdal ، يقرأ للخلف). تحتاج إلى تركيز جهودك على المكون الذي يؤدي إلى أكبر استثمار للوقت. يجب نقله خارج التطبيق ، والقيام بالعمل الضروري ، والعودة والاختبار مرة أخرى. السبب وراء قيامك بذلك هو أنه في كثير من الأحيان يكون تحسين الأداء بنسبة 20٪ نتيجة عشرة تحسينات بنسبة 2٪. وفي إطار نظام كبير ، من المستحيل قياس مثل هذا التحسن الصغير. لهذا ، يجب اختبار المكون في مجموعة اختبار. يمكن أن يعني التحسن بنسبة 20٪ في أداء أحد المكونات الرئيسية للنظام تحسنًا بنسبة 5٪ للنظام ككل ، وهذه نتيجة ممتازة لبعض المناطق. لا تنس أن التحسينات يمكن أن يكون لها عدد من التأثيرات العالمية ، لذلك بناءً على نتائج القياس الانتقائي ، يجب أن تكون حذرًا جدًا في استخلاص الاستنتاجات حول تشغيل النظام ككل.
خطأ أنا متأكد من أن قرائنا لا يرتكبونه ، ولكن هذا أمر شائع جدًا: يقيس الناس سرعة تجميع التصحيح. لا يجب أن يتم ذلك أبداً. يشبه هذا الانزعاج بسبب انخفاض سرعة الحلزون في السباقات: فهو غير مخصص لمثل هذه المنافسة ، ولديه أهداف أخرى في الحياة. خطأ آخر ، أقل وضوحًا إلى حد ما: يقوم الناس أولاً بقياس الأداء الأساسي للنظام ، وبعد ذلك مباشرة يقومون بأداء القياس. ولكن بعد جمع خط الأساس ، يتم تسخين العديد من الموارد. على سبيل المثال ، يتم تخزين الملفات المفتوحة مؤقتًا وتظل في الذاكرة (على الأقل في Linux). وبالتالي ، سيكون الاختبار الثاني أسرع لأنه يتم إطلاقه بعد الأول. يحدث هذا حتى مع مكالمات malloc. بعد هذه المكالمات ، لا يعود النظام إلى حالته الأصلية حتى إذا تم إجراء مكالمات تحرير الذاكرة. يسمح التكوين الداخلي ، والتخزين المؤقت ، والميزات التي يستخدمها مخصص الذاكرة بتشغيل مكالمات malloc التالية بشكل أسرع. حتى من دون الأخذ في الاعتبار تأثير ذاكرة التخزين المؤقت ، يتذكر malloc ، على سبيل المثال ، أن بعض الوظائف تخصص ذاكرة لكائنات 4 كيلوبايت عدة مرات ، مما يعني أنك بحاجة إلى قائمة مجانية بحجم عنصر 4 كيلوبايت. أو مثال آخر: يتم تخزين عمليات بحث DNS مؤقتًا لإعادة استخدامها بعد الاستعلام الأول. إذا كان ذلك ممكنًا ، أثناء قياس الأداء ، تحتاج إلى إعادة تشغيل العملية بالكامل في كل مرة ، من البداية إلى النهاية.
على سبيل المثال ، من أجل إعادة النظام بالكامل إلى حالته الأصلية ، في حالة الملفات ، يجب فتحها على قرص منفصل ، والذي ، بعد اكتمال الاختبار ، يجب إزالته (كما أفهمه ، يمكن القيام بذلك تحت Windows). العملية ليست سهلة ، لكنها ضرورية في معظم الحالات.
من خلال مواصلة المحادثة حول الأخطاء أثناء التحسين ، كان علي التعامل مع مثل هذه الحالات عندما يتم تضمين تكاليف printf في نتائج الاختبار. هناك أخطاء إجرائية عندما يتم تغيير أكثر من شيء واحد قبل كل قياس ، وهو ما ينتهك المبادئ الأساسية للتجربة العلمية ، لأنه ليس من الواضح أي تأثير تقيسه. خطأ خطير آخر هو عندما يتم تحسين بعض الحالات النادرة ، مما يؤدي إلى التشاؤم في مواقف أخرى.
هنا مثال مع Stack Overflow. غالبًا ما يقوم المؤلف بفرز البيانات التي تم فرزها بالفعل ويفاجأ ، لأن الوظيفة "is_sorted" من الواضح أنها أسرع بكثير من الفرز. فلماذا إذاً في "فرز السطر الأول ليس" إذا تم إرجاعه؟ أنت تقوم بتحسين حالة نادرة للغاية ، وبيانات مصنفة بالكامل ، وسيتعين على أي شخص آخر لديه عنصر واحد على الأقل غير مصنف فرز تكاليف هذا التحسين. هذا لا يستحق القيام به.
أعتقد أنني لست مضطرًا لإثبات لفترة طويلة أن البنى المتنافسة اليوم معقدة للغاية: تغيير التردد الديناميكي ، الانقطاع بسبب العمليات الأخرى ، الافتراضية ، وما إلى ذلك. لذلك ، يكاد يكون من المستحيل الحصول على نفس الوقت عند القياس ، وسوف ترتجف مؤشراتك دائمًا. لذلك ، لا ينبغي للمرء أن يعتمد على الأشياء التي تبدو واضحة. قل ، قد يبدو لنا واضحًا أن عددًا أقل من التعليمات يعني رمزًا أسرع ، وهذا ليس صحيحًا دائمًا. قد يبدو أيضًا أن استخدام البيانات المخزنة سيكون دائمًا أسرع من إعادة إجراء العمليات الحسابية ، لذلك إذا قمت بتخزين النتائج مؤقتًا ، فستكون على ما يرام. كما في الحالة السابقة ، لا يمكن ذكره بشكل لا لبس فيه ، تمامًا كما لا يمكن ذكر العكس دون قيد أو شرط - كل هذا يتوقف على السياق. من الواضح أنه يجب أن يكون لديك شيء واحد فقط: كل شيء يحتاج إلى القياس. إذا قمت بقياس كل شيء ، فستحصل على نتائج أفضل من الخبراء ذوي المعرفة الذين لا يأخذون القياسات.
هناك عدد من الممارسات الموثوقة إلى حد ما ، والتي قد تقودك مناقشتها إلى أفكار مثيرة للاهتمام. يجب أن نبدأ بحقيقة أن الرياضيات لن تخذلك. يجعل من الممكن إظهار أن الأنظمة بسرعات مختلفة يمكن أن تكون متكافئة. تعطي الرياضيات قواعد لإظهار تكافؤ بعض الأشياء وتحديد بعض الخصائص ، وفي حين أنها غير متحيزة ، لا يهم أي الأشياء مثيرة للاهتمام وأيها ليس كذلك. يعتقد الكثير من الناس أن التحسين يعتمد على معرفة كود الآلة والعمل مع البتات ، ولكنه في الواقع يحتوي على الكثير من الرياضيات ، لأنك تثبت أن النظام الأسرع يعادل نظام أبطأ.
قاعدة عامة أخرى هي أن أجهزة الكمبيوتر تحب الأشياء لتكون مملة. هل تحتاج إلى ضرب بعضها البعض في متجهين ، مليار عنصر في كل منهما؟ هذه مهمة مثالية لجهاز الكمبيوتر ، حيث يتم شحذ جميع المعدات الموجودة فيه خصيصًا لهذا النوع من المهام. لتحليل هذه البيانات ، بناءً عليها لبناء تعبير عادي - لا أريد القيام بذلك. أجهزة الكمبيوتر لا تحب أشياء مثل الفروع ، والتبعيات ، والمكالمات غير المباشرة ، باختصار - فهي لا تحب الشفرة الذكية ، لكنها تحب الشفرة المملة. لا تحب أجهزة الكمبيوتر التسجيل غير المباشر - وهي مشكلة معقدة يعاني منها الأشخاص المشاركون في الحديد منذ فترة طويلة ولا يمكنهم حلها.
قاعدة أخرى هي أنه يجب عليك إعطاء الأفضلية للعمليات عند أدنى مستوى ممكن ، وبعبارة أخرى ، تفضل إضافة إلى الضرب ، والضرب على الأسي. مرة أخرى ، الرياضيات مفيدة هنا.
أخيرا ، القاعدة الأخيرة - الأصغر والأكثر جمالا. يتيح الحجم الصغير لأجهزة الكمبيوتر تحقيق مزاياها على أفضل وجه ، لأنها تفضل أن تكون البيانات ، وخاصة التعليمات ، قريبة من بعضها البعض. نتائج عدة قياسات لسرعة التطبيق ستختلف دائمًا ، سيكون لديك بعض توزيع النتائج. عادة نأخذ فقط متوسط هذه النتائج القليلة. لكن المشكلة هي أنه بسبب تفاصيل أجهزة الكمبيوتر ، فإن المتوسط سيشمل الكثير من الضوضاء. عندما يركب بيل غيتس حافلة ، في المتوسط ، يكون كل راكب في حافلة ملياردير. يبدو الأمر رائعًا ، ولكن القليل من الراحة لشخص بلا مأوى يركب نفس الحافلة. يحدث موقف مماثل مع الانقطاعات: تستغرق عملية الضرب نانو ثانية ، ولكن عند إجراء العديد من القياسات لمثل هذه العمليات ، فإن أحدها سيقطع حتمًا مليوني ثانية. الفرق هو ثلاثة أوامر من الحجم ، ومع ذلك ، لا يأخذ المطورون هذا الأمر دائمًا في الاعتبار.
لذلك ، أكرر: الضوضاء في أجهزة الكمبيوتر دائمًا ما تكون مضافة ؛ بالنسبة للناس ، قد يبدو الأمر غير مهم ، ولكن بالنسبة إلى وضع العلامات الدقيقة ، فإن المتوسط الحسابي سيشمل الكثير من الضوضاء. بدلاً من المتوسط ، تحتاج إلى مؤشر يقيس الوقت الذي يمكنك التأثير فيه بطريقة أو بأخرى. إذا تناولنا هذه المسألة من وجهة نظر الرياضيات ، فسوف نرى أننا بحاجة إلى إيجاد قيمة تتوافق مع أكبر عدد من القياسات التي قمنا بها. وبعبارة أخرى ، نحن بحاجة إلى تعديل. هذا يقودنا على الفور إلى المشكلة: ماذا يحدث إذا كنت تأخذ تعديل سريع؟ إذا كانت الخوارزمية احتمالية أو إذا كانت البيانات عشوائية ، فلن تكون هناك أي موضة تقريبًا. ستكون كثافة القيم هي نفسها تقريبًا عبر الطيف. في هذه الحالة ، نتجاهل ببساطة 5 ٪ من أكبر القياسات وبعد ذلك نأخذ متوسط القيمة - أو الحد الأقصى ، في الحالة الأخيرة سيكون لدينا سقف لن يتم تجاوزه في 95 ٪ من الحالات. دائمًا تقريبًا سيكون هناك أي موضوع واحد يجلس في الطابق السفلي القديم مع مودم بطيء ، حيث يتم تحميل كل صفحة لمدة ساعة. الإنسان البحت ، نحن بالطبع نتعاطف معه ، ولكن لا يمكننا مساعدة الجميع تقنيًا - لذلك ، يجب تجاهل 5 ٪ من الحالات المتبقية. بشكل عام ، عند حل مشاكل الشبكة ، غالبًا ما نركز على النسبة المئوية 95 ، لأنه من المستحيل التركيز على المائة. تعني النسبة المئوية المائة أبطأ نتيجة لجميع القياسات المجمعة - وهذا ليس بالمعلومات.
استبدل الفروع بالحساب
كيف آمل أن يكون من الواضح أن القياس ليس مشكلة سهلة. دعونا نلقي نظرة على بعض الأمثلة ونبدأ بمحاولة استبدال التفرع بالحساب. نحن نتحدث عن الحالات التي نحتاج فيها إلى عبارة if ، ولكن استخدامها في كثير من الأحيان أمر غير مرغوب فيه. بدلاً من ذلك ، سوف نقوم بدمج نتيجة الفرع كقيمة 0/1. ستبدو الشفرة خطية ، سيحتاج الكمبيوتر فقط إلى المرور بها من البداية إلى النهاية ، دون التفكير في الخطوة التي عليك اتخاذها بعد ذلك.
دعونا نحاول حل المشكلة التالية: نقل قيعان كل ربع من المصفوفة إلى الربع الأول. بمعنى آخر ، يجب تقسيم المصفوفة إلى أربعة أجزاء ويجب وضع القيمة الدنيا لكل جزء في بداية المصفوفة.
static void min4(double[] p) { int n = p.Length; int i = 0, j = n / 4, k = n / 2, l = 3 * n / 4; for (; i < n / 4; ++i, ++j, ++k, ++l) { int m = p[i] <= p[j] ? i : j; if (p[k] < p[m]) m = k; if (p[l] < p[m]) m = l; Swap(ref p[i], ref p[m]); } }
أعلاه هو الرمز الأساسي. بالمناسبة ، يمكنني أن أفخر بفخر أنني قمت بترجمة هذه الأمثلة إلى C # ، وتم تجميعها بنجاح. الكود نفسه بسيط للغاية: `يتم تعيين m لفهرس أصغر القيمتين الموجودتين في المؤشرين` i و` j ، ثم يتم تكرار مهمة مماثلة مرتين أخريين ، اعتمادًا على المؤشرين الآخرين. أخيرًا ، يتم عكس القيمة في الفهرس `m في الصفيف مع القيمة في الفهرس` i. كما ترون ، نتخطى المصفوفة باستخدام أربعة متغيرات حثيّة.
ستكون مشكلة اختبار مثل هذه الخوارزمية مثيرة للاهتمام وغير واضحة. سنحتاج إلى اختبارها ليس على مجموعة بيانات واحدة ، ولكن على البيانات التي يمكن أن تنشأ في حالات مختلفة. على سبيل المثال ، على البيانات التي تشبه أنابيب العضو: زيادة أولاً ، ثم تقليل ؛ على بيانات عشوائية بتوزيع موحد ؛ على مجموعة عشوائية من الأصفار والأصفار - من البيانات العشوائية فقط هنا ، الفرق هو أنه سيكون هناك العديد من القيم المكررة ؛ على البيانات المصنفة بالفعل ؛ أخيرا ، على البيانات التي تم الحصول عليها من خلال قياسات حقيقية لبعض الظاهرة المادية. سيكون هذا نهجًا جادًا لقياس سرعة الخوارزمية ، وهو مقبول بشكل عام بين الأشخاص الذين يدرسون الخوارزميات.
دعونا نحاول تحسين الشفرة التي التقينا بها للتو.
static void min4(double[] p) { int q = p.Length / 4; int i = 0, j = n / 4, k = n / 2, l = 3 * n / 4; for (; i < q; ++i, ++j, ++k, ++l) { int m = p[i] <= p[j] ? i : j; if (p[k] < p[m]) m = k; if (p[l] < p[m]) m = l; Swap(ref p[i], ref p[m]); } }
كأول تحسين ، سنحاول تجنب التكرار المفرط للعمليات ، لهذا نخرج العديد من عمليات القسمة من الحلقة - قسمة `n على 2 و 4 وقسمة 3 *` n على 4. ولكن بعد هذا التحسين ، اكتشفنا أن الحسابات لم تكن ل لنا المشكلة الرئيسية: لن يصبح الكود أسرع ، على الرغم من أنه سيكون أكثر إحكاما. في أفضل الأحوال ، سنحقق تحسنًا بنسبة نصف بالمائة.
static void min4(double[] p) { int q = p.Length / 4; int i = 0, j = q, k = 2 * q, l = 3 * q; for (; i < q; ++i, ++j, ++k, ++l) { int m0 = p[i] <= p[j] ? i : j; int m1 = p[k] <= p[l] ? k : l; Swap(ref p[i], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
التغيير الثاني الذي سنقوم به على الكود هو تقليل التبعيات. في الإصدار السابق من الخوارزمية ، يعتمد تعيين `m إلى` k أو` l على القيمة المعينة لخط m m أعلاه. لتقليل عدد التبعيات `m ، نحسب بشكل منفصل m0 و` m1 ، ثم نقوم بمقارنتها. عندما أجريت هذا التحسين ، كنت آمل في حدوث تحسن كبير في سرعة الخوارزمية ، ولكن في النهاية تبين أنها صفر. ولكن ، في رأيي ، من المهم الحفاظ على عدد التبعيات عند الحد الأدنى ، ولهذا السبب قمت بحفظ الرمز.
static void min4(double[] p) { int q = p.Length / 4; for (int i = 0; i < q; ++i) { int m0 = p[i] <= p[i + q] ? i : i + q; int m1 = p[i + 2 * q] <= p[i + 3 * q] ? i + 2 * q : i + 3 * q; Swap(ref p[i], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
دعونا نحاول الآن تقليل عدد المتغيرات الاستقرائية من أربعة إلى واحد ، وسنقوم بحساب المتغيرات الثلاثة المتبقية حسابيًا ، حيث إنها مرتبطة بشكل مستمر ببعضها البعض. هذا بسيط للغاية: بدلاً من `k ، سيكون لدينا i i q ، بدلاً من المتغيرين الآخرين -` i + 2 * q و` i + 3 * q. كان لدي أيضًا آمال كبيرة في هذا التحسين ، ولكن ، مثل السابق ، لم يعط أي نتائج في الوقت المناسب. هذا يثبت مرة أخرى أهمية القياسات: بدونها يمكنني التفاخر بأنني قد حسنت بشكل كبير من تشغيل الخوارزمية ، ولدي حجج مهمة للغاية.
static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = q; i < q2: ++i) { int m0 = p[i - q] < p[i] ? i - q : i; int m1 = p[i + q2] < p[i + q] ? i + q2 ? i + q; Swap(ref p[i - q], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
كمحاولة رابعة ، نعيد هيكلة الدورة للتخلص من الضرب في 3. وهذا سيعطينا تحسنًا بنسبة 3٪. النتيجة لا تزال غير مثيرة للإعجاب. بعد ذلك ، حاول التخلص من عوامل التشغيل الثلاثية.
للقيام بذلك ، أود أن أقدم لك وظيفة جديدة - `static int اختياري (إشارة منطقية ، قيمة int). يقوم بتحويل القيمة المنطقية للمدخلات إلى Int32 ، ويتكاثر بـ -1 ويمررها إلى عامل تشغيل أحادي المعامل AND مع قيمة الإدخال الثانية. إذا كانت علامة الإدخال خاطئة ، فسيكون في int32 0 ، وبعد كل التحويلات على الإخراج سنظل نحصل على 0. إذا كانت علامة الإدخال صحيحة ، في int32 ستكون 1 ، عند ضربها في -1 نحصل على FFFFFFFF ، والتي بعد البت "و" مع أي رقم سيعطي هذا الرقم الثاني. يرجى ملاحظة أنه لا يوجد بيان إذا كان في أي مكان ، فالشفرة بدون تفرع ، فهي مملة بالنسبة لجهاز كمبيوتر (على الرغم من أنها تبدو معقدة بالنسبة لنا).
static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = q; i < q2; ++i) { int m0 = i - optional(p[i - q] <= p[i], q); int m1 = i + q + optional(p[i + q2] < p[i + q], q); Swap(ref p[i - q], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
سنقوم باستبدال عوامل التشغيل الثلاثية بهذه الوظيفة الاختيارية ، وسندمجها داخل الحساب. نطبقها مرتين ، وفي الحالة الثالثة ، اترك علامة الاستفهام. وبالتالي ، فبدلاً من أربعة فحوصات في هذه الدورة ، سيكون لدي فحص واحد فقط.
من نتائج القياس التي تراها على الشريحة ، يتضح مدى أهمية اختبار الخوارزمية على عدة مجموعات بيانات مختلفة. في مجموعة واحدة لن نفهم أي شيء. بالنسبة للبيانات العشوائية والحقيقية ، لدينا أكثر من تسريع مزدوج ، على أنابيب الأعضاء والبيانات المصنفة ، لدينا تباطؤ طفيف. ويرجع ذلك إلى حقيقة أنه في حالة البيانات المصنفة لمنبئ الانتقال لن تكون هناك مفاجآت ، فسوف تتنبأ بدقة 100٪. في حالة أنابيب الأعضاء ، سيكون لدينا توقع خاطئ واحد في منتصف مجموعة البيانات - مرة أخرى ، دقة عالية جدًا. في المقابل ، مع البيانات العشوائية ، سيكون الفرق بين نهجينا كبيرًا. لقد استبدلنا جميع الشيكات غير المتوقعة بمنطق بسيط. هنا نعود إلى حقيقة بسيطة: أجهزة الكمبيوتر مصممة للحوسبة ، كما يوحي الاسم (الكمبيوتر - الحوسبة). التفريع ، عرض الصور على الشاشة - كل هذا أداءهم أسوأ بكثير. أداء أحادي المعامل "And" بالنسبة لهم أسهل بكثير من تمرير عبارة if.
static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = 0; i < q; ++i) { int m = i + optional(p[i + q] < p[i], q); m += optional(p[i + q2] < p[m], q); m += optional(p[i + q2 + q] < p[m], q); Swap(ref p[i], ref p[m]); } }
بعد أن حققنا في النهاية نتيجة إيجابية من التحسين ، سنحاول استبدال آخر عامل ثلاثي بوظيفتنا `الاختيارية. هذه المرة ستكون الزيادة في السرعة صغيرة. لفهم سبب حدوث ذلك ، تحتاج إلى إلقاء نظرة على التعليمات البرمجية التي تم إنشاؤها. في الإصدار السابق من الكود ، حيث كانت علامة الاستفهام لا تزال موجودة ، وجد المترجم بالفعل طريقة لتنفيذ الكود دون التفرع. وعندما يصل إلى عامل التشغيل الثلاثي ، يمكنه بالفعل توقع ذلك. استبدال هذه القطعة الأخيرة بـ `اختياري سيؤدي إلى كود أسوأ إلى حد ما. لذلك ، أكرر ، من المهم أخذ القياسات في كل مرة.
ميزة أخرى أود أن أوصيك بها هي `` ifelse بدون فروع ، والتي تراها الآن على الشاشة. صحيح ، لم أستطع تحقيق التحسينات في الأداء في مثالنا. إذا تم تمرير 0 كعلامة لها ، فسيكون السطر الأول 0 ؛ في الثانية ، نطرح 1 من 0 في Int32 ونحصل على FFFFFFFF ، وبعد ذلك يتم تمرير هذه القيمة إلى أحادي المعامل "و" جنبًا إلى جنب مع الوسيطة الدالة `v2 ، والتي ستمنحنا هذه الوسيطة نفسها دون تغييرات ؛ وأخيرًا ، يتم تمرير الخطين الأول والثاني إلى أحادي المعامل “OR” ، والذي سيعطينا مرة أخرى `v2. إذا كان العلم 1 ، فسيكون السطر الأول مساويًا لـ v1 ؛ في الثانية ، نطرح 1 من 1 ونحصل على 0 ، ونتيجة لذلك سيكون الخط بأكمله 0 ، و 0 و "v1 في البت" OR "سيعطي" v1.
آمل أن مثل هذه `` ifelse بدون وظيفة متفرعة ستثير اهتمام الأشخاص الذين يشاركون في الواجهة الخلفية - في الوقت الحالي ، لا يستخدم المترجمون الحديثون لهذا النهج. باستخدام هذه الوظائف ، يمكنك إعادة تنظيم الخوارزميات حتى يفهمها المترجمون من أجلك ، لأنك أكثر ذكاءً وإبداعًا من المترجم.
تقاطع مجموعة كبيرة
غيّر موضوع حديثنا قليلاً وانتقل إلى تقاطع مجموعات كبيرة. حتى الآن ، كنا نتحدث عن مشغلين فرديين ، والآن سنقوم بإنشاء خوارزميات جديدة ، لذلك سنحتاج إلى صرف الانتباه عن التفاصيل وفتح عقولنا إلى منظور أكبر. أفترض أنك على دراية بدمج الفرز وضرب متجهين والبحث عن العناصر الشائعة لمتجهين مفروزين. يتم اجتياز مجموعتين مفروزيتين ، وعندما تكون العناصر المتساوية فيها ، يعتبر هذا تطابقًا. إذا كان أحد العنصرين المراد مقارنتهما أصغر ، فإنه يتغير. هذه الخوارزمية بسيطة للغاية ، ولكنها شائعة جدًا - على الأرجح الأكثر استخدامًا في العالم. يتم استخدامه في جميع الاستعلامات من عدة كلمات ، كل مثل هذا الاستعلام هو تقاطع مجموعتين. تستخدم هذه الخوارزمية ، على وجه الخصوص ، Google ، ويجب أيضًا تطبيقها في جميع استعلامات قاعدة البيانات.
int Intersect(double[] a1, double[] a2, double[] t) { if (a1.Length == 0 || a2.Length == 0) return 0; int i1 = 0, i2 = 0, i = 0; for (;;) if (a1[i1] < a2[i2]) { if (++i1 == a1.Length) break; } else if (a2[i2] < a1[i1]) { if (++i2 == a2.Length) break; } else { t[i++] = a1[i1]; if (++i1 == a1.Length || ++i2 == a2.Length) break: } return i; }
ألق نظرة على التطبيق الأساسي لهذه الخوارزمية. إذا كانت مجموعتا الإدخال فارغتين ، فمن الواضح أننا نرجع 0. بعد ذلك ، نبدأ حلقة لا نهائية ، حيث ، إذا كان هناك تطابق ، نقوم بزيادة النتيجة بمقدار 1 والتحقق مما إذا كان يجب إكمال الدورة. بدلاً من حلقة لا نهائية ، يمكن للمرء استخدام العبارة لـ وتحديد الشرط لإنهاء الحلقة فيه. لكن هذا يعني عمل إضافي. في التنفيذ الذي تراه على الشريحة ، في الفرع الأول لدينا `إذا (a1 [i1] <a2 [i2]) ، وبعد ذلك هناك زيادة في` i1 بنسبة 1 ، ولا يمكننا التحقق من `i1 إلا. وبالمثل ، في الفرع الثاني ، نحتاج فقط إلى التحقق من `i2. يجب التحقق من القيمتين فقط في الفرع الثالث. إذا كان هذا الفحص في بداية الدورة ، فسنقوم بالعمل الإضافي.
دعونا نحاول تحسين هذا التنفيذ. في الوقت الحالي ، يكون تعقيدها الخوارزمي خطيًا ، اعتمادًا على وسيطتي إدخال. في التعلم الآلي ، غالبًا ما يجد المرء تقاطع المجموعات المختلفة جدًا عن بعضها البعض في الحجم أو في الإحصائيات. على سبيل المثال ، لديك متجه إدخال طويل ومتجه ميزات قصير تقوم بالتحقق منه. في رمزنا ، يمكن أن يكون هناك مليون تسجيل في `a1 ، وألف في` a2. في هذه الحالة ، لسنا على استعداد لخوض مليون خطوة لاستكمال هذه الخوارزمية. سيكون الحمل الأكبر هنا في سطر التعليمات البرمجية التالي: `if (++ i1 == a1.length) break. قبل ذلك مباشرةً ، تتم المقارنة ، ثم في هذا السطر توجد زيادة في القيمة ؛ هذا ، في جوهره ، هو بحث خطي. نحن نكرر عبر ناقل طويل بحثًا عن عناصر قصيرة. في أسوأ الحالات ، سنقوم بالعديد من عمليات البحث هذه ، ونتحرك ببطء على طول الناقل.
دعونا نحاول تحسين هذه الخوارزمية. حسنًا ، إن لم يكن البحث الخطي ، فالثنائي أفضل ، أليس كذلك؟ دعونا نستخدم ثنائي. ميزته هي أنه يعطي مؤشر أكبر العناصر الصغيرة.
int Intersect(double[] a1, double[] a2, double[] t) { int i1 = 0, i = 0; for (; i1 != a1.Length; ++i1) { auto m = Bsearch(a2, a1[i1]); if (m == a2.Length) continue; --m; if (!(a2[m] < a1[i1])) t[i++] = a1[i1]; } return i; }
الكود أعلاه هو تطبيق لخوارزمية البحث الثنائي. لكنها ليست فعالة للغاية. أسوأ موقف هنا سيكون عندما يفشل البحث الثنائي في كل مرة. وسوف تنشأ في سيناريوهات مهمة للغاية - على سبيل المثال ، عندما تكون المجموعتان متطابقتان. أنت ، مثل الأحمق ، تقطع الدوائر باستخدام البحث الثنائي ، بينما كان عليك فقط خوض الخوارزمية الخطية الأولى. لماذا البحث الثنائي ، عندما يكون العنصر المطلوب - في كل مرة هنا ، الأول في القائمة؟
كيفية جعل الخوارزمية تعمل بنجاح على بيانات متطابقة ومختلفة؟ فحص جميع البيانات سيكون مكلفًا جدًا بالنسبة للموارد. سأحجز أن هذا لا يتعلق بالبيانات المتطابقة تمامًا ، ولكنه متشابه جدًا ، مع إحصائيات مماثلة ، يمكن أن تختلف الأحجام أيضًا. يمكنك التحقق من العناصر القليلة التالية. الحل الواضح هو تقليل البحث. عندما نجري بحثًا ثنائيًا ، بعد أن وجدنا بعض العناصر ، لم نعد مهتمين بعناصر أصغر منه ، حيث يتم فرز المتجه الثاني أيضًا. وبالتالي ، يمكننا في كل مرة تقليل منطقة البحث ، مع تجاهل جميع العناصر الأقل من العنصر الموجود.
int Intersect(double[] a1, double[] a2, double[] t) { int i1 = 0, i2 = 0, i = 0; for (; i1 != a1.Length; ++i1) { auto m = Bsearch(a2, i2, a2.Length, a1[i1]); if (m == i2) continue; if (!(a2[m - 1] < a1[i1])) t[i++] = a1[i1]; i2 = m + 1; } return i; }
هنا تنفيذ هذا النهج. ترى أننا نجري بحثًا ثنائيًا في كل مرة عن جزء من الصفيف الأصلي يبدأ بـ `i2 وينتهي بـ` a2.length. نظرًا لأن `i2 ستزداد مع كل بحث ، سيتم تقليل منطقة البحث.
التحسين التالي الذي أرغب في تنفيذه هنا مرتبط بخوارزمية البحث المتداخل. في الجوهر ، هذا بحث ثنائي بخطوة مختلفة. في حالة البحث الثنائي ، نبدأ في كل مرة من الوسط - ولكن دعنا نفكر عندما نبحث عن اسم في دليل الهاتف ، لا نفتحه في المنتصف؟ إذا بدأ لقب شخص ما ، على سبيل المثال ، في "B" ، فسنفتح الكتاب بالقرب من البداية. يتم تطبيق هذا المبدأ في بحث سريع: نبدأ في الزحف إلى البيانات في الاتجاه التصاعدي بخطوة تتزايد بشكل كبير بعد كل عملية تحقق: أول 1 ، ثم 2 ، ثم 4. وهذا يمنحنا تعقيدًا خوارزميًا جيدًا. إذا نمت الخطوة بشكل خطي ، فسيكون التعقيد من الدرجة الثانية. عندما "نتخطى" العنصر الذي نبحث عنه ، نجري بحثًا ثنائيًا عاديًا على الجزء المتبقي ، والذي سيكون صغيرًا ولن يؤثر بشكل كبير على وقت تنفيذ الخوارزمية. وبالتالي ، فإننا نجمع بين جميع مزايا كلا النهجين. تنفيذ مثل هذه الخوارزمية:
int GBsearch(double[] a, int i, int j, double v) { for (int step = 1;; step *= 2) { if (i >= j) break; if (a[i] > v) break; if (i + step >= j) return Bsearch(a, i + 1, J, v); if (a[i + step] > v) return Bsearch(a, i + 1, i + step, v); i += step + 1; } return i; }
نناقش الآن القياس ، أي محاولة العثور على تقاطع أكثر من مجموعتين. لكل بحث عن عدة كلمات ، سنحتاج إلى العثور على تقاطع عدة مجموعات. للقيام بذلك ، يمكننا ، على سبيل المثال ، مقارنة المجموعتين الأوليين ، ثم تقاطعهما مع المجموعة الثالثة وما إلى ذلك. لكن هذا ليس الحل الأمثل. نحتاج إلى أخذ العناصر الأولى من جميع المجموعات والعثور على أصغرها ، والتي ستحتاج بعد ذلك إلى نقلها. نحن بحاجة إلى بنية بيانات تسمح لنا بالعثور على أصغر العناصر والعديد من التعقيد المستمر. هيكل البيانات هذا حفنة. لكنها ستكون مجموعة غريبة ، ولن تستند إلى مجموعة مادية. سيكون الأمر خياليًا ، ولن ننظم فيه سوى العناصر الأولى لمجموعاتنا. بمجرد العثور على أصغر عنصر في كومة الذاكرة المؤقتة ، لا يزال بإمكاننا البحث في جميع المجموعات الأخرى.
العمل على الموضوعات التي نناقشها في الممارسة العملية اليوم له شكل حرفي إلى حد ما. من الناحية العملية ، سيكون لدينا في الغالب عدة مجموعات ، وليس فقط مجموعتين ، وقد تم كتابة الكثير من العمل حول هذا الموضوع. الخوارزمية الكلاسيكية هنا هي SVS ، حيث نقوم بتجميع المجموعات ، ونأخذ المجموعتين الأصغر ونختار الأقصر كمرشح.
هنا يمكنك العثور على نظرة عامة جيدة حول هذا الموضوع. أصبحت المشاكل المرتبطة بالمجموعات المتداخلة ، والمنتج التدرجي للمتجهات المتفرقة ، والفرز عن طريق الدمج ، وأي أشكال للمقارنة مع الصورة بمرور الوقت أكثر إثارة للاهتمام. لقد أثبتت الخوارزمية التي أظهرتها لك أنها مفيدة جدًا. شكرا لكم على اهتمامكم.
لن يأتي أندريه ألكسندرسكو إلى DotNext 2018 موسكو ، لكن جيفري ريشتر ، جريج يونج ، بافيل يوسيفوفيتش وآخرين سيكونون هناك. يمكن العثور على أسماء المتحدثين وموضوعات التقارير هنا ، وتذاكر هنا . انضم الآن!