في الفترة من 10 إلى 22 سبتمبر ، ستقام مسابقة تطوير الهاتف المحمول Yandex.Blitz. التسجيل
مفتوح . إن Blitz عبارة عن طريق قصير إلى Yandex: سيتعين على أفضل 5 مشاركين اجتياز مقطع واحد من المقابلة بنجاح بدلاً من الأربعة القياسيين للحصول على عرض عمل.
بمناسبة المسابقة ، تحدثنا مع الزملاء حول المهام المثيرة للاهتمام التي تنطبق على المنصات والخوارزميات المحمولة. اليوم سوف نشارك قصصهم مع قراء هبر.
يُعتقد أن تطوير تطبيقات الهاتف المحمول هو شيء خاص ، بعيدًا عن البرمجة بالمعنى العام ، ولا يواجه المتخصصون الذين يكتبون لأجهزة Android و iOS حل المهام المكثفة للخوارزميات ، ويقتصرون على ربط المكتبات الجاهزة ، وتنضيد الشاشات ، وكتابة منطق الأعمال البسيط و البحث عن أخطاء في نظام أساسي محدد. ولكن ليس بهذه البساطة.
دائمًا ما يكون إنشاء برامج للأجهزة المحمولة محفوفًا بالقيود. حتى في الأجهزة المتطورة ، فإن وحدات المعالجة المركزية ووحدات معالجة الرسومات ليست قوية وليست بالذاكرة نفسها الموجودة في أجهزة الكمبيوتر الحديثة. في الوقت نفسه ، فإن الجزء الرئيسي من السوق هو الهواتف الذكية ذات الميزانية المحدودة التي تحتوي على أجهزة أضعف. يتأثر أصحابها بشكل خاص بنقص الموارد.
من المستحيل تطوير مشروع تنافسي معقد بدون استخدام الحلول التي تتعامل مع المهام بشكل أسرع من الوقت التربيعي. يمكن للمستخدمين الانتقال إلى منافس إذا لم يعجبهم سرعة العمل أو كيف يستهلك تطبيقك طاقة البطارية.
تاريخياً ، يعد Blitz منافسة على معرفة الخوارزميات والقدرة على ترجمة فكرة الحل إلى تعليمات برمجية. لن يكون Blitz ، الذي سيعقد في سبتمبر ، استثناءً. لقد حاولنا تحديد المهام باستخدام الخوارزميات المشابهة لتلك التي يستخدمها مطورو Yandex للهواتف المحمولة في مشاريع حقيقية لنظامي التشغيل Android و iOS.
تسريع متصفح سوجر
ميخائيل إيفيموف ، مطور رئيسي :
- فعلت المربع متعدد الاستخدامات - سلسلة بحث المتصفح. يعمل الملء التلقائي فيه - فقط أدخل بداية الكلمة ، وسوف نقدم الكلمة بأكملها. يمكن تبسيط المهمة الأولية إلى ما يلي: بعد استلام سلسلة إدخال ، ابحث عن جميع الكلمات من مجموعة محددة مسبقًا تظهر فيها سلسلة الإدخال على أنها سلسلة فرعية. للقيام بذلك ، نأخذ كل لاحقات الكلمة - جميع السلاسل الفرعية التي تنتهي بها. على سبيل المثال ، بالنسبة لكلمة "جدول" ، ستكون كلمة "جدول" و "طول". لا تأخذ في الاعتبار اللواحق المكونة من حرف أو حرفين - هنا سيكون لدينا "ol" و "l" ، لأن القمامة تدخل من خلالهم.
وهكذا ، بدلاً من كلمة واحدة ، نحصل على كلمتين. إذا كان يتألف من خمسة أحرف ، فستحصل على ثلاثة ، وما إلى ذلك. علاوة على ذلك ، على سبيل المثال ، يمكنك بناء بنية بيانات معروفة جيدًا ، مما يسمح لك بالبحث عنها. لكن هذه البنية لها عيب - يمكن أن تشغل مساحة كبيرة من الذاكرة.
نحن ، بدورنا ، احتفظنا بقائمة مرتبة من اللواحق - صفيف اللاحقة. ليس العنصر في الصفيف هو اللاحق بالكامل - ثم ستشغل البنية الكثير من الذاكرة ، ومقدار تربيعي - ولكن مجرد زوج من المؤشرات. يشير الأول منهم إلى الكلمة أو العبارة التي تريد استخدامها ، والثاني - الرمز في الكلمة أو العبارة التي تبدأ بها اللاحقة. هذا النهج يوفر الذاكرة. لدينا فقط مؤشرين ، رقمين ثمانية بايت بدلاً من الكلمات الطويلة جدًا.
السؤال التالي هو كيفية تخزين قائمة تم فرزها بالفعل. يمكن تخزينه كمصفوفة بسيطة - ولكن بعد ذلك سيتم إدراج إدخالات جديدة فيه لفترة طويلة جدًا. لذلك ، اخترت تخزين شجرة البحث الثنائية "المعززة" - شجرة البحث الثنائية المعززة. كمفتاح ، تحتوي كل عقدة في الشجرة على لاحقة معينة لكلمة معينة ، وكمكمل ، يتم تخزين المعلومات المتعلقة بالأولويات في العقد. كل ما عليك فعله هو العثور على عقدة الشجرة التي تطابق البادئة المدخلة. علاوة على ذلك ، يمكنك تحليل هذا والعقد المجاورة لفهم أي الكلمات التي يمكن استخدامها لإصدارها.
من بينها ، يتم اختيار أولئك الذين لديهم أولوية أعلى. تتأثر الأولوية بطول المسافة البادئة لللاحقة من بداية الكلمة. بالنسبة إلى الكلمات التي لا تحتوي على مسافة بادئة صفرية ، تكون الأولوية أعلى - لنفترض مثلاً أنه إذا أدخل المستخدم "st" ، فستكون كلمة "table" أعلى بكثير من الكلمة "Bridge". ولكن من حيث المبدأ ، يمكنك إدخال تسلسل من الأحرف بحيث يقوم المستعرض في الرد بإبلاغ الكلمة التي يحدث فيها هذا التسلسل في المنتصف أو النهاية. على سبيل المثال ، إذا لم تكن هناك كلمة تبدأ بهذا التسلسل.
عرض كاميرات الدوائر التلفزيونية المغلقة على Yandex.Maps المحمول
سيرجي كوزنتسوف ، المطور الرئيسي :- كان لدينا خوارزمية تعرض الكاميرات على الخريطة. كان يعمل في التربيعية ، ليس بسرعة كبيرة. كانت هناك فكرة أنه يمكن تحسينه ، دون اللجوء إلى أي رتوش.
إذا تحدثنا عن بيان المشكلة ، فلدينا الكثير من الكاميرات التي يجب عرضها. في المقاييس العالية للخريطة ، يمكن أن تتقاطع مع بعضها البعض ، وكان ذلك قبيحًا - كان مطلوبًا عرض كاميرا واحدة بدلاً من العديد من التقاطعات.
إذا قمنا بإضفاء الطابع الرسمي على هذه المشكلة ، فإنها تتلخص في ما يلي: على المستوى هناك n مربعات متطابقة مع جوانب متوازية مع محاور الإحداثيات ، وتحتاج إلى الاختيار من بينها مثل هذا العدد الكبير من المربعات التي لا تتقاطع داخلها ، وجميع المربعات الأخرى تتقاطع على الأقل من مربعات المجموعة الأصلية. أبسط خوارزمية الحل - عندما اخترنا مربعًا وتقاطعناه مع جميع العناصر الأخرى - عملت في n 2 . ولكن يمكن حل المشكلة في n * log (n) ، باستخدام فئة معينة من الخوارزميات ، والتي تسمى في الأدب "خط المسح". إذا كنت لا تعرف عن هذا النهج ، فيمكن بالطبع حل هذه المشكلة ، ولكن إذا كنت تعرف ، يمكن حلها بسهولة أكبر. أنت تعرف على الفور في أي اتجاه للتفكير.
كاميرات على خرائط الجوال. إذا قمت بالتصغير ، يبقى رمز واحد فقط
الحصول على البيانات من أحد مصادر متصفح سوغيست
ألكسندر ياشكين ، رئيس مجموعة الواجهة الخلفية للبوابة :- هناك العديد من مصادر النصائح "الثقيلة" التي يتم عرضها عند الكتابة في متصفح المربع متعدد الاستخدامات. أحد هذه المصادر هو التاريخ المحلي للمستخدم. يتم تحميل نصائح من التاريخ بواسطة مزود تاريخي - جاء إلينا مكون من Chromium. ما هو المميز في المربع متعدد الاستخدامات؟ يجب أن يكون سريعًا جدًا ، وموجهًا فورًا ، أثناء الكتابة ، لذا تكون المصادر متزامنة في الغالب. عندما يبدأ المتصفح ، يقوم الموفر بإنشاء فهرس سريع لنصائح المحفوظات خلال الأسبوع الماضي. في Chromium ، استخدم فهرس محفوظات المربّع متعدد الاستخدامات حاويات الاقتران std :: set و std :: map من مكتبة C ++ القياسية. لتخزين البيانات داخل هذه الحاويات ، عادة ما يتم استخدام الخشب الأحمر والأسود.
كانت مهمتنا هي تسريع البحث عن التاريخ في المربع متعدد الاستخدامات. من الرسوم البيانية من المستخدمين ، رأينا أن البحث التاريخي يستغرق معظم الوقت ، وعلى أجهزة الكمبيوتر البطيئة يعاني الناس حقًا. بالنسبة للبعض ، كان التوقع هو عُشر الثانية - عندما تكتب الأحرف بسرعة في المربع متعدد الاستخدامات ، فهي طويلة جدًا ويمكن أن تكون أسوأ.
لقد صنعت العديد من المناهج والتحسينات في المنبع في Chromium. في نفس الوقت أجرى تغييرات على رمزنا. ثم انتقلت المهمة إلى المطور دينيس ياروشيفسكي. إنه مطور متحمس إلى حد ما - فهو مهتم بـ C ++ و STL والخوارزميات. بعد التفتت ، اقترح العمل بشكل جذري: استبدل std :: set بـ flat_set ، و std :: map بـ flat_map. أي ، فقط قم بتغيير البنية الأساسية. std :: set و std :: map قم بتخزين عناصرها في عقد الشجرة ، و flat_set و flat_map ، في الواقع ، مغلفان فوق ناقل الفرز. تعتبر الحاويات المسطحة واحدة من أكثر الحاويات شيوعًا التي ليست جزءًا من مكتبة C ++ القياسية. ربما في المعيار التالي ، ما زالوا سيقعون فيه.
في البداية كان هناك بعض عدم الثقة: بدا المسار المقترح بسيطًا للغاية ، ملقى على السطح. لإثبات الفعالية ، قمنا باختبار الأداء: أخذنا ملف تعريف أحد زملائنا ، وقمنا ببناء فهرس للتاريخ منه وأجرينا استفسارات شائعة عليه. اخترنا 10 استعلامات وعدنا الأوقات. أظهر لي دينيس النتيجة ، وكانت التحسينات واضحة ، كما أنني آمنت بفكرته.
كانت المشكلة التي تم العثور عليها ليست خاصة بـ Yandex.Browser. لقد أثرت على أي متصفح يعتمد على Chromium ، لذلك أولاً ، بصفتنا مشاركين في مشروع Chromium ، قررنا إجراء عملية تنقيب. ولكن في Chromium هناك العديد ممن يرتكبون ، وبعض الأفكار المقترحة متوحشة. يتمتع مطورو Chromium بموقف حذر إلى حد ما تجاه كل من يعرض تغيير شيء ما من الخارج ، بشكل أكثر جذرية. في البداية لم يرغبوا في أخذ رقعتنا. اقترحوا قبل ذلك لإثبات الفعالية وكتابة مستند تصميم مصغر حتى يتمكنوا من فهم الفكرة والاستفادة وانتقاد الاقتراح.
بالإضافة إلى ذلك ، قالوا: بمجرد الحاجة ، اكتب وأضف تطبيقات منفصلة للحاويات المسطحة. لا تقم بإضافة أي مكتبات جديدة إلى مشروعنا - فالتطبيقات موجودة بالفعل في التعزيز ، إيستل. تضاف الحاويات المسطحة إلى المكونات الأساسية للكروم. هذا نظير للمكتبة القياسية ، والناس الكروم قلقون للغاية حتى لا يدخل شيء غير ضروري فيه.
قام دينيس ياروشيفسكي بكل هذا ، وقضى بعض الوقت في كتابة مستند تصميم ، وكتب تنفيذ مجموعة مسطحة في قوالب C ++ ، وطبّق الكثير من سحر القوالب ، وكتب اختبارات تغطي وظائف الحاويات ، وأنشأ اختبارًا صناعيًا آخر للعطور - لم نتمكن من إرسال اختبار الأداء بشكل حقيقي ملف تعريف زميل. جادل دينيس مع مالكي كود الأساس والمربع متعدد الاستخدامات ، وأعاد صياغة الرمز بشكل كبير بناءً على نتائج المراجعة - وفي النهاية تغلب عليهم وحمّل الرمز إلى Chromium.
استمرت هذه الملحمة بأكملها ستة أشهر. ثم كتب الكروم: "نعم ، لقد رأينا بالفعل تحسنًا بنسبة 10-20٪ في جميع الرسوم البيانية. رائع ، شكرًا! " منهم بالفعل من خلال المصب جاء إلينا في المتصفح ، ثم نهاية سعيدة. في الواقع ، تسارع المؤشر التاريخي بشكل ملحوظ في جميع التكوينات ، على جميع المنصات. في هذا المؤشر ، مزايا الحاويات المسطحة أفضل بكثير من العيوب.
بعد استخدام المنبع ، تم تعيين flat_set و flat_map في كثير من الأحيان - الآن في الكود يمكنك العثور على عدة مئات من الأماكن التي تشارك فيها. الأخلاق - الصبر والعمل سيطحنان كل شيء ، ويختاران بعناية ليس فقط خوارزميات لتعليماتك البرمجية ، ولكن أيضًا هياكل بيانات مناسبة.
انظر الجانب الأيسر من الرسم البياني. يرجع الانخفاض الحاد في وقت تحميل نتائج المربع متعدد الاستخدامات في بداية عام 2017 بالتحديد إلى الانتقال إلى خريطة مسطحة وخريطة مسطحة
تسريع واحدة من HashMap في Chromium
أوليغ ماكسيمينكو ، المطور الرئيسي :"كان الهدف هو تسريع تخزين صفحات HTML العادية في أحد مشاريعنا الفرعية." لقد استخدمت الوسائل القياسية لتحديد ملف التعليمات البرمجية - نظرت إلى أجزاء التعليمات البرمجية "الساخنة" في عملية الحفظ. صادفت مكانًا غير متوقع. أي أن هذا ليس المنطق الرئيسي ، ولكن مجرد بحث في حاوية HashMap ، والتي يجب أن تشغل نسبة صغيرة من الوقت الإجمالي. بدلاً من ذلك ، كانت هناك تكاليف قوية حقًا.
قررت استبدال التنفيذ الحالي. لقد كانت HashMap داخلية من Chromium. لقد استبدلته وحصلت على الفوز عدة مرات. ثم ذهبت إلى أبعد من ذلك قليلاً وتأكدت من أن هذا لم يكن خطأ من الرجال من Google ، وأنه لم يكن الأمر يتعلق بتطبيق خريطة HashMap بأكملها ، ولكن وظيفة تجزئة. هذا شيء خارجي. واتضح أنه كان لديهم تجزئة تافهة في الرمز الذي استخدمناه ، تم استخدام العنوان في الذاكرة كتجزئة. ربما ، بسبب بعض الميزات ، على سبيل المثال ، حجم صغير ، مثل هذا الحل يناسبهم. ربما لم تكن HashMap الخاصة بهم نقطة ساخنة ، لكنها أصبحت لنا عندما طبقنا هذا الهيكل. ببساطة عن طريق استبدال وظيفة التجزئة الساذجة والتافهة بـ std :: hash حصلنا على زيادة في السرعة بمقدار 3-10 مرات. ونتيجة لذلك ، اختفى هذا النداء لذاكرة التجزئة من قائمة النقاط الساخنة ، فقد بدأ في احتلال نسبة مئوية صغيرة ، كما كان متوقعًا في البداية. أصبح كل شيء جيدًا وجميلًا.