मोबाइल विकास और एल्गोरिदम के जंक्शन पर प्रोग्राम कैसे लिखें? यैंडेक्स प्रतियोगिता और कहानियां

10 से 22 सितंबर तक, Yandex.Blitz मोबाइल विकास प्रतियोगिता आयोजित की जाएगी। पंजीकरण खुला है । ब्लिट्ज यैंडेक्स का एक छोटा तरीका है: शीर्ष 5 प्रतिभागियों को नौकरी की पेशकश प्राप्त करने के लिए मानक चार के बजाय साक्षात्कार के एक भाग को सफलतापूर्वक पास करना होगा।

प्रतियोगिता के अवसर पर, हमने उन सहयोगियों के साथ दिलचस्प कार्यों के बारे में बात की जो मोबाइल प्लेटफ़ॉर्म और एल्गोरिदम पर तुरंत लागू होते हैं। आज हम हबर के पाठकों के साथ उनकी कहानियाँ साझा करेंगे।



यह माना जाता है कि मोबाइल एप्लिकेशन का विकास कुछ खास है, सामान्य अर्थों में प्रोग्रामिंग से दूर है, और एंड्रॉइड और आईओएस के लिए लिखने वाले विशेषज्ञ एल्गोरिदम-गहन कार्यों को हल करने में कभी भी मुठभेड़ नहीं करते हैं, खुद को तैयार पुस्तकालयों को जोड़ने के लिए सीमित करते हैं, स्क्रीन को टाइप करते हैं, सरल व्यापार तर्क लिखते हैं। एक विशिष्ट प्लेटफॉर्म के बग पर शोध करना। लेकिन इतना सरल नहीं है।

मोबाइल उपकरणों के लिए सॉफ्टवेयर बनाना हमेशा सीमाओं से परे होता है। यहां तक ​​कि उच्च अंत उपकरणों में, सीपीयू और जीपीयू उतने शक्तिशाली नहीं हैं और एक आधुनिक कंप्यूटर में उतनी मेमोरी नहीं है। इसी समय, बाजार का मुख्य हिस्सा कमज़ोर हार्डवेयर वाले बजट स्मार्टफोन हैं। उनके मालिक संसाधनों की कमी से विशेष रूप से प्रभावित हैं।

एक जटिल प्रतिस्पर्धी परियोजना का विकास उन समाधानों के उपयोग के बिना असंभव है जो एक द्विघात समय की तुलना में तेजी से कार्यों का सामना करते हैं। उपयोगकर्ता किसी प्रतियोगी के पास जा सकते हैं यदि वे काम की गति पसंद नहीं करते हैं या आपके आवेदन में बैटरी की खपत कितनी है।

ऐतिहासिक रूप से, ब्लिट्ज एल्गोरिदम के ज्ञान और कोड में समाधान के विचार का अनुवाद करने की क्षमता के लिए एक प्रतियोगिता है। ब्लिट्ज, जो सितंबर में आयोजित किया जाएगा, अपवाद नहीं होगा। हमने एंड्रॉइड और आईओएस के लिए वास्तविक परियोजनाओं में यैंडेक्स मोबाइल डेवलपर्स द्वारा उपयोग किए जाने वाले एल्गोरिदम के साथ कार्यों का चयन करने की कोशिश की।

सुगम ब्राउज़र को गति देना

मिखाइल एफिमोव, प्रमुख डेवलपर :

- मैंने ऑम्निबॉक्स किया - ब्राउज़र सर्च स्ट्रिंग। ऑटोफिल इसमें काम करता है - बस शब्द की शुरुआत दर्ज करें, और हम पूरे शब्द की पेशकश करेंगे। प्रारंभिक कार्य को निम्नलिखित के लिए सरल बनाया जा सकता है: एक इनपुट स्ट्रिंग प्राप्त करने के बाद, पूर्वनिर्धारित सेट से सभी शब्द ढूंढें जिसमें इनपुट स्ट्रिंग एक विकल्प के रूप में दिखाई देता है। ऐसा करने के लिए, हम शब्द के सभी प्रत्ययों को लेते हैं - सभी सब्सट्रिंग जिसके साथ यह समाप्त होता है। उदाहरण के लिए, शब्द "टेबल" के लिए यह "टेबल" और "टोल" होगा। एक या दो वर्णों के प्रत्यय - यहाँ हमारे पास "ol" और "l" होगा - ध्यान में न रखें, क्योंकि इनके माध्यम से कचरा संप्रदाय में चला जाता है।

इस प्रकार, एक शब्द के बजाय, हमें दो मिलते हैं। यदि इसमें पाँच अक्षर शामिल होते हैं, तो उन्हें तीन आदि मिलेंगे। इसके अलावा, उदाहरण के लिए, आप एक प्रसिद्ध डेटा संरचना ट्राइ का निर्माण कर सकते हैं, जो आपको उनके लिए खोज करने की अनुमति देता है। लेकिन इस संरचना में एक खामी है - यह बहुत सारे मेमोरी स्पेस ले सकती है।

हम, बदले में, प्रत्ययों की एक क्रमबद्ध सूची - प्रत्यय सरणी रखते थे। सरणी में तत्व संपूर्ण प्रत्यय नहीं है - तब संरचना बहुत अधिक मेमोरी, एक द्विघात राशि लेती है - लेकिन सिर्फ एक जोड़ी बिंदु। उनमें से पहला उस शब्द या वाक्यांश को इंगित करता है जिसे आप उपयोग करना चाहते हैं, दूसरा - शब्द या वाक्यांश में वह प्रतीक जिसके साथ प्रत्यय शुरू होता है। यह दृष्टिकोण स्मृति को बचाता है। हमारे पास केवल दो बिंदु हैं, बहुत लंबे शब्दों के बजाय दो आठ-बाइट संख्या है।

अगला सवाल यह है कि पहले से ही सॉर्ट की गई सूची को कैसे स्टोर किया जाए। इसे एक सरल सरणी के रूप में संग्रहीत किया जा सकता है - लेकिन फिर बहुत लंबे समय तक इसमें नई प्रविष्टियां डाली जाएंगी। इसलिए, मैंने "संवर्धित" बाइनरी सर्च ट्री को स्टोर करने के लिए चुना - संवर्धित बाइनरी सर्च ट्री। एक कुंजी के रूप में, पेड़ में प्रत्येक नोड में एक निश्चित शब्द के लिए एक निश्चित प्रत्यय होता है, और "पूरक" के रूप में, प्राथमिकताओं पर जानकारी नोड्स में संग्रहीत होती है। आपको बस उस पेड़ के नोड को ढूंढना है जो दर्ज किए गए उपसर्ग से मेल खाता है। इसके अलावा, आप इसे और पड़ोसी नोड्स को समझने के लिए विश्लेषण कर सकते हैं कि किस शब्द को जारी करने के लिए उपयोग किया जा सकता है।

उनमें से, उच्च प्राथमिकता वाले लोगों का चयन किया जाता है। प्राथमिकता शब्द की शुरुआत से प्रत्यय की लंबाई की लंबाई से प्रभावित होती है। शून्य इंडेंटेशन वाले शब्दों के लिए, प्राथमिकता अधिक है - कहते हैं, यदि उपयोगकर्ता "सेंट" में प्रवेश करता है, तो "पुल" शब्द की तुलना में "टेबल" शब्द प्राथमिकता में बहुत अधिक होगा। लेकिन सिद्धांत रूप में, आप वर्णों का ऐसा क्रम दर्ज कर सकते हैं कि प्रतिक्रिया में ब्राउज़र उस शब्द को सलाह देगा जहाँ यह क्रम मध्य या अंत में होता है। उदाहरण के लिए, यदि कोई शब्द नहीं है जो इस क्रम से शुरू होता है।

मोबाइल Yandex.Maps पर सीसीटीवी कैमरों का प्रदर्शन

सर्गेई कुज़नेत्सोव, प्रमुख डेवलपर :

- हमारे पास एक एल्गोरिथ्म था जो एक मानचित्र पर कैमरे प्रदर्शित करता था। उन्होंने बहुत तेज नहीं, द्विघात समय में काम किया। एक विचार था कि इसे सुधार किया जा सकता है, बिना किसी तामझाम के।

यदि हम समस्या के बयान के बारे में बात करते हैं, तो हमारे पास बहुत सारे कैमरे थे जिन्हें प्रदर्शित करने की आवश्यकता है। नक्शे के उच्च पैमानों पर, वे एक-दूसरे के साथ प्रतिच्छेद कर सकते थे, और यह बदसूरत था - कई प्रतिच्छेदन के बजाय एक कैमरा प्रदर्शित करना आवश्यक था।

यदि हम इस समस्या को औपचारिक रूप देते हैं, तो यह निम्नलिखित पर उबलता है: समतल पर समन्वय अक्षों के समानांतर पक्षों के साथ समान समरूप वर्ग होते हैं, और आपको उनसे इतनी बड़ी संख्या में वर्ग चुनने की आवश्यकता होती है, ताकि वे इसके अंदर प्रतिच्छेद न करें, और अन्य सभी वर्ग कम से कम एक वर्ग को प्रतिच्छेद करें। मूल सेट के वर्ग। सबसे सरल समाधान एल्गोरिदम - जब हमने एक वर्ग का चयन किया और इसे अन्य सभी के साथ जोड़ दिया - एन ^{2 के} लिए काम किया। लेकिन समस्या को एन * लॉग (एन) में हल किया जा सकता है, एक निश्चित वर्ग के एल्गोरिदम का उपयोग करके, जिसे साहित्य में "स्कैनिंग" कहा जाता है। यदि आप इस दृष्टिकोण के बारे में नहीं जानते हैं, तो यह समस्या, निश्चित रूप से हल हो सकती है, लेकिन यदि आप जानते हैं, तो इसे बहुत आसान हल किया जा सकता है। आपको तुरंत पता चल जाता है कि किस दिशा में सोचना है।

_{^{मोबाइल मैप्स पर कैमरे। यदि आप ज़ूम आउट करते हैं, तो केवल एक आइकन रहता है}}

सुगम ब्राउज़र के स्रोतों में से एक से डेटा प्राप्त करना

अलेक्जेंडर यशकिन, पोर्टल बैकएंड समूह के प्रमुख :

- सुझावों के कई "भारी" स्रोत हैं जो ऑम्निबॉक्स ब्राउज़र में टाइप करते समय प्रदर्शित होते हैं। ऐसा ही एक स्रोत उपयोगकर्ता का स्थानीय इतिहास है। इतिहास से युक्तियां एक ऐतिहासिक प्रदाता द्वारा अपलोड की जाती हैं - क्रोमियम से एक घटक हमारे पास आया। सर्वग्राही के बारे में क्या खास है? यह बहुत तेज होना चाहिए, तुरंत टाइप करें, जैसा कि आप टाइप करते हैं, इसलिए स्रोत ज्यादातर तुल्यकालिक हैं। जब ब्राउज़र शुरू होता है, तो प्रदाता पिछले सप्ताह के दौरान इतिहास युक्तियों का एक त्वरित सूचकांक बनाता है। क्रोमियम में, ऑम्निबॉक्स के लिए इतिहास सूचकांक में सी ++ मानक पुस्तकालय से सहयोगी कंटेनरों का उपयोग किया जाता है :: सेट और एसटीडी :: नक्शा। ऐसे कंटेनरों के अंदर डेटा स्टोर करने के लिए, आमतौर पर लाल-काले रंग की लकड़ी का उपयोग किया जाता है।

हमारा कार्य सर्वव्यापी में इतिहास की खोज को गति देना था। उपयोगकर्ताओं के हिस्टोग्राम से, हमने देखा कि ऐतिहासिक खोज में सबसे अधिक समय लगता है, और धीमी गति से कंप्यूटर पर लोग वास्तव में पीड़ित होते हैं। कुछ के लिए, उम्मीद एक सेकंड का दसवां हिस्सा थी - जब आप जल्दी से ऑम्निबॉक्स में पात्रों को टाइप करते हैं, तो यह बहुत लंबा है, और यह और भी खराब हो सकता है।

मैंने क्रोमियम में कई दृष्टिकोण, अनुकूलन, ऊपर की ओर किए। उसी समय हमारे कोड में बदलाव किए। तब कार्य हमारे डेवलपर डेनिस यारोशेवस्की को दे दिया गया। वह एक उत्साही डेवलपर है - वह सी ++, एसटीएल, एल्गोरिदम में रुचि रखता है। इधर-उधर की अफवाहों के बाद, उन्होंने मौलिक रूप से कार्य करने का प्रस्ताव दिया: std को बदलें: flat_set के साथ सेट करें, और flat_map के साथ std :: map यही है, बस मूल संरचना को बदलना है। std :: set और std :: मानचित्र अपने तत्वों को पेड़ के नोड्स में संग्रहीत करते हैं, और flat_set और flat_map, वास्तव में, सॉर्ट किए गए वेक्टर पर आवरण होते हैं। फ्लैट कंटेनर सबसे लोकप्रिय कंटेनरों में से एक हैं जो C ++ मानक पुस्तकालय का हिस्सा नहीं हैं। शायद अगले मानक में वे अभी भी इसमें गिरेंगे।

पहले तो कुछ अविश्वास था: प्रस्तावित रास्ता बहुत सरल लग रहा था, सतह पर पड़ा हुआ था। प्रभावशीलता को साबित करने के लिए, हमने एक पूर्ण परीक्षण किया: हमने अपने एक सहयोगी की प्रोफाइल ली, उसमें से एक इतिहास सूचकांक बनाया और उस पर लोकप्रिय प्रश्नों को चलाया। हमने 10 प्रश्न चुने और समय गिना। डेनिस ने मुझे परिणाम दिखाया, सुधार स्पष्ट थे, और मुझे भी उनके विचार पर विश्वास था।

पाया गया समस्या Yandex.Browser के लिए विशिष्ट नहीं थी। यह किसी भी क्रोमियम-आधारित ब्राउज़र को प्रभावित करता है, इसलिए सबसे पहले, क्रोमियम प्रोजेक्ट में भाग लेने वालों के रूप में, हमने एक अपस्ट्रीम करने का फैसला किया। लेकिन क्रोमियम में कई ऐसे हैं जो प्रतिबद्ध हैं, और प्रस्तावित विचारों में से कुछ जंगली हैं। क्रोमियम डेवलपर्स का उन सभी के प्रति नाज़ुक रवैया है जो बाहर से कुछ बदलने की पेशकश करते हैं, सभी अधिक मौलिक हैं। पहले तो वे हमारा पैच नहीं लेना चाहते थे। उन्होंने इससे पहले सुझाव दिया था कि प्रभावशीलता साबित करने और एक मिनी-डिज़ाइन-डॉक लिखने के लिए ताकि वे प्रस्ताव को विचार, लाभ और आलोचना समझ सकें।

इसके अलावा, उन्होंने कहा: एक बार जब आप की आवश्यकता होती है, तो फ्लैट कंटेनरों के अलग-अलग कार्यान्वयनों को लिखें और जोड़ें। हमारी परियोजना में किसी भी नए पुस्तकालय को न जोड़ें - कार्यान्वयन पहले से ही बढ़ावा में मौजूद हैं, पूर्व। क्रोमियम के आधार घटकों में फ्लैट कंटेनर जोड़े जाने थे। यह मानक पुस्तकालय का एक एनालॉग है, और क्रोमियम लोग बहुत चिंतित हैं ताकि इसमें कुछ भी नहीं हो।

डेनिस यरोशेवस्की ने यह सब किया, एक डिज़ाइन दस्तावेज़ लिखने में समय बिताया, C ++ टेम्प्लेट्स में फ्लैट_सेट कार्यान्वयन लिखा, बहुत सारे टेम्प्लेट जादू लागू किए, कंटेनरों की कार्यक्षमता को कवर करने वाले परीक्षण लिखे, एक और सिंथेटिक पूर्ण परीक्षण बनाया - हम वास्तविक परीक्षण के लिए सही परीक्षण नहीं भेज सके। एक सहकर्मी की प्रोफाइल। डेनिस ने आधार और ऑम्निबॉक्स कोड के मालिकों के साथ तर्क दिया, समीक्षा के परिणामों के आधार पर कोड को काफी हद तक फिर से काम किया - और अंत में उन्हें ओवरकैम किया और कोड को क्रोमियम पर अपलोड किया।

यह पूरी गाथा छह महीने तक चली। क्रोमियम ने तब लिखा: “हां, हमने वास्तव में सभी हिस्टोग्राम में 10-20% सुधार देखा है। महान, धन्यवाद! ” उनसे यह पहले ही डाउनस्ट्रीम के माध्यम से ब्राउज़र में हमारे पास आया, और फिर एक सुखद अंत। दरअसल, ऐतिहासिक सूचकांक सभी प्लेटफार्मों पर सभी कॉन्फ़िगरेशन पर काफी तेजी से बढ़ा है। इस सूचकांक में, फ्लैट कंटेनरों के फायदे नुकसान से बहुत बेहतर हैं।

अपस्ट्रीम के बाद, फ्लैट_सेट और फ्लैट_मैप का उपयोग अधिक बार किया जाने लगा - अब कोड में आप कई सौ स्थानों को ढूंढ सकते हैं जहां वे शामिल हैं। नैतिकता - धैर्य और श्रम सब कुछ पीस जाएगा, और सावधानी से न केवल अपने कोड के लिए एल्गोरिदम चुनें, बल्कि उपयुक्त डेटा संरचनाएं भी।

_{^{ग्राफ के बाईं ओर देखें। 2017 की शुरुआत में ऑम्निबॉक्स परिणामों के लोडिंग समय में तेज कमी फ्लैट_सेट और फ्लैटमैप के संक्रमण के कारण ठीक है}}

क्रोमियम में किसी HashMap की गति बढ़ाना

ओलेग मेक्सिमेंको, प्रमुख डेवलपर :

"लक्ष्य हमारे एक उपप्रोजेक्ट में नियमित HTML पृष्ठों के भंडारण को गति देना था।" मैंने कोड को प्रोफाइल करने के मानक साधनों का उपयोग किया - मैंने देखा कि बचत की प्रक्रिया में कोड के कौन से टुकड़े "गर्म" होते हैं। मैं एक अप्रत्याशित जगह पर आया था। यही है, यह मुख्य तर्क नहीं है, लेकिन हाशपॉपर कंटेनर पर सिर्फ एक खोज है, जिसे कुल समय के कुछ छोटे प्रतिशत पर कब्जा करना चाहिए। इसके बजाय, वास्तव में मजबूत लागतें थीं।

मैंने मौजूदा कार्यान्वयन को बदलने का फैसला किया। यह क्रोमियम से एक आंतरिक हैशपॉप था। मैंने उनकी जगह ली और मुझे कई बार जीत मिली। फिर मैं थोड़ा आगे बढ़ा और यह सुनिश्चित किया कि यह Google के लोगों की गलती नहीं थी, कि यह पूरे हाशप को लागू करने का मामला नहीं था, बल्कि एक हैश फ़ंक्शन था। यह एक बाहरी चीज है। और यह पता चला कि उनके पास उस कोड में एक तुच्छ हैश था, जिसका उपयोग हमने मेमोरी में एड्रेस हैश के रूप में किया था। शायद, कुछ विशेषताओं के कारण, उदाहरण के लिए, एक छोटी मात्रा, ऐसा समाधान उनके अनुकूल है। हो सकता है कि उनका हाशपॅप कोई हॉट स्पॉट नहीं था, लेकिन जब हम इस संरचना को लागू करते हैं तो यह हमारा बन गया। बस भोली और तुच्छ हैश फ़ंक्शन को std :: hash से बदलकर हमने 3–10 गुना की गति वृद्धि प्राप्त की है। नतीजतन, हैश मेमोरी के लिए यह अपील गर्म स्थानों की सूची से गायब हो गई, यह कुछ छोटे प्रतिशत पर कब्जा करना शुरू कर दिया, जैसा कि पहले की उम्मीद थी। सब कुछ अच्छा और सुंदर हो गया।