कोर के प्रति सेकंड हजारों मार्गों के सैकड़ों। Yandex। अनुभव

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

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

पांच हजार आदेशों के साथ समस्या को हल करने के लिए, आपको सभी बिंदुओं के बीच की दूरी और यात्रा के समय को जानना होगा। ये 5000x5000 के आयाम के साथ संख्याओं के दो मैट्रिक्स हैं। हम पूरे दिन के लिए कूरियर मार्गों की योजना बनाते हैं, और सुबह में कूरियर एक समय में बिंदु से बिंदु तक पहुंच जाएगा, और शाम को - दूसरे के लिए। तो, आपको दिन के प्रत्येक घंटे के लिए समय और दूरी के मैट्रिक्स की गणना करने की आवश्यकता है। दिन के सभी घंटे अद्वितीय नहीं हैं, लेकिन कॉर्क समय (सुबह और शाम) को अच्छी तरह से कवर करने की आवश्यकता है। इसलिए, हम तेरह घंटे के स्लाइस के साथ एक कॉन्फ़िगरेशन में आए। कुल में, हमें प्रत्येक 13x5000x5000 के दो क्यूब्स (समय और दूरी) की आवश्यकता होती है। ये 325 मिलियन मार्ग हैं, जिनकी गणना वास्तविक रोड ग्राफ के अनुसार की जाती है, जिसमें 165 मिलियन किनारे हैं। Yandex.Maps टीम के एक अच्छी तरह से अनुकूलित एल्गोरिथ्म में एक मार्ग की गणना कुल 900 घंटों की गणना के लिए लगभग 10 एमएस लेती है।यहां तक ​​कि 900 सीपीयू के समानांतर होने पर, आपको 1 घंटे इंतजार करना होगा। हम ऐसी सेवा शुरू नहीं कर सकते, हमें एक अधिक उपयुक्त एल्गोरिथ्म की आवश्यकता थी।

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



एक साक्षात्कार में साक्षात्कार के लिए लगभग हर उम्मीदवार को इस तरह के कार्य को अनुकूलित करने में पहला कदम पता होता है: आप लहर को दो तरफ से शुरू कर सकते हैं और जब तरंगें मिलती हैं तो खोज को समाप्त कर सकते हैं। आधा त्रिज्या की दो तरंगों का कुल क्षेत्रफल एक बड़े से कम है।



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

कार्ड राउटर टीम ने काफी समय से इस तरह के अनुकूलन किए हैं। यह वे थे जिन्होंने दो बिंदुओं के बीच एक मार्ग खोजने के लिए 10 एमएस हासिल करना संभव बना दिया था। :) तो अब के लिए, हम अपनी समस्या को हल करने के करीब नहीं आए हैं।

चूंकि बिंदु-से-बिंदु खोज मोड पहले से ही बेहद अनुकूलित है, इसलिए हम मैट्रिक्स में श्रृंखला की गणना को अनुकूलित कर सकते हैं। एक पंक्ति एक बिंदु से अन्य सभी की दूरी है। जबकि हम दूर के बिंदु की दूरी की तलाश कर रहे हैं, हम एक साथ दूरियों की गणना करते हैं। इसलिए, श्रृंखला की गणना करना सबसे दूर के बिंदु की दूरी की गणना करने के बराबर है।



हम इस एल्गोरिथ्म का उपयोग करके श्रृंखला की गणना के समय को देखते हैं और याद करते हैं कि 5000 मार्गों की क्रमिक गणना लगभग 5000 * 10 ms / 50 होगी:


ग्राफ विभिन्न एन (वास्तविक डेटा के अनुसार) के लिए आकार 1 * एन की दूरी मैट्रिक्स में एक पंक्ति की गणना समय को दर्शाता है। यह देखा जा सकता है कि हमारे लिए 1 * 5000 के आकार की पंक्ति की गणना 1.3 सेकंड में फिट हो जाती है। चार्ट में एक ट्रेंड लाइन जोड़ी गई है, जो बताती है कि गणना का समय एन में रैखिक रूप से थोड़ा अधिक धीरे-धीरे बढ़ रहा है, एन ** 0.74 का क्रम

पहले से ही खराब नहीं है! इस एल्गोरिथ्म के साथ, हम अपने घन की गणना 13 * 5000 * 1.3 s = 84 500 s = लगभग 24 घंटे में कर सकते हैं। यह पंक्तियों में आसानी से समानता रखता है, और 50 सीपीयू का उपयोग करते समय, आधे घंटे में दूरी की गणना की जाती है। घन गणना एल्गोरिथ्म की जटिलता आदेश हे (एन ** 1.74):


13 N*N 50 CPU ( 13*N/50). , 5000 , . 10 000, : .

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

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


समय। जटिलता ओ (एन ** 1,1) के आदेश पर प्राप्त की जाती है। हाई एनएस को ट्रेंड लाइन से बाहर खटखटाया जाता है, क्योंकि उत्तर की पीढ़ी और इसके नेटवर्क पर डाउनलोडिंग पहले से ही समय को प्रभावित कर रहे हैं।

सिंगल कोर का उपयोग करके 5000x5000 मैट्रिक्स प्रति 115 सेकंड और एन फिक्शन पर लगभग रैखिक निर्भरता एक वास्तविकता बन गई है! एल्गोरिथ्म का विचार ऊपर वर्णित दो विचारों को जोड़ता है: श्रृंखला और पदानुक्रमित खोज के लिए दिक्जस्त्र। जाहिर है, दूसरी पंक्ति की गणना करना शुरू करना, कुछ बिंदु पर हम फिर से ग्राफ के उसी क्षेत्र के चारों ओर घूमेंगे जो हमने पिछली पंक्ति की गणना करते हुए गुजरे थे। इसलिए, हमें पदानुक्रमित ग्राफ़ के नोड्स पर सभी गंतव्यों के लिए कम से कम दूरी याद करें। जब हम अगली श्रृंखला की गणना करना शुरू करते हैं, तो, इस तरह के नोड तक पहुंचने के बाद, हम तुरंत अन्य बिंदुओं के लिए लगभग सभी दूरी प्राप्त करेंगे।



डेढ़ साल पहले, इसने हमें ई के साथ आधे घंटे का समय बचाने की अनुमति दीरसद और लोहे के सेवन को काफी कम करना। पहले, एक बड़े अनुरोध के लिए, हमें आधे घंटे के लिए 50 कोर चाहिए थे, लेकिन अब - 2 मिनट के लिए 13 कोर। यह लगभग 200,000 मार्ग प्रति सेकंड प्रति कोर है। वह दुर्लभ मामला जब नया एल्गोरिथम केवल समस्याओं की श्रेणी को बंद नहीं करता है, लेकिन संभव के बारे में हमारे विचारों का विस्तार करता है।

---

_{^{* अनुच्छेद "परिवहन नेटवर्क में मार्ग नियोजन", पैराग्राफ 2.7.2 "सबसे छोटा रास्ता देखें "}}