1 व्यक्ति-माह के लिए मार्गों की खोज करें

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

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



मैं किसी सेवा को विकसित करने की प्रक्रिया के बारे में बात करूंगा।

ग्राफ के बारे में।

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

इसके अतिरिक्त, तर्क और / या यातायात नियमों द्वारा लगाए गए आंदोलन प्रतिबंधों के साथ एक अलग फ़ाइल है। प्रत्येक प्रतिबंध सड़क सेगमेंट (पहली फ़ाइल से) के लिए पहचानकर्ताओं का एक वेक्टर है, जिसके लिए अनुक्रमिक आंदोलन निषिद्ध है।

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

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

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

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

हम इसके साथ आए (इसके बाद C ++ कोड):
1. ग्राफ के किनारों के लिए एक कंटेनर बनाया:

typedef size_t EdgeID; typedef size_t VertexID; struct EdgeDesc { VertexID vtxSrc, vtxDest; EdgeInfo info; }; typedef std::unordered_multimap<EdgeID, EdgeDesc> EdgeMap; 

एक मल्टीमैप, क्योंकि हमने ग्राफ़ के सेगमेंट / किनारों के लिए नए पहचानकर्ताओं को पेश नहीं करने का निर्णय लिया है, और आगे और पीछे के किनारों के बारे में जानकारी को समान पहचानकर्ताओं के साथ संग्रहीत करते हैं। यह शायद सही निर्णय नहीं था, क्योंकि मेरी राय में यह कुछ प्रक्रियाओं के तर्क को जटिल करता है, लेकिन शुरुआत में ऐसा लगता था कि यह सामान्य होगा।


चित्र 1।

2. समन्वय विमान को वर्ग मीटर प्रति मीटर (छवि 1) में विभाजित किया गया था।
प्रत्येक शीर्ष एक कुंजी के साथ जुड़ा हुआ है:

 static_assert(sizeof(size_t) >= 8, "size_t type should be 64 bit or larger"); auto keyPartX = [this](double x) { return (size_t)(x - bound_.first.x) + 1; }; auto keyPartY = [this](double y) { return (size_t)(y - bound_.first.y) + 1; }; auto getKey = [](size_t x, size_t y) { return x << (sizeof(size_t) / 2 * 8) | y; }; auto getKeyXY = [&keyPartX, &keyPartY, &getKey](double x, double y) { return getKey(keyPartX(x), keyPartY(y)); }; 

3. एक हैश कंटेनर बनाया

 typedef size_t CellKey; typedef std::unordered_map<CellKey, std::vector<VertexID>> SPHash; 

स्ट्रीट नेटवर्क सेगमेंट की सूची देखते समय, हम प्रारंभिक और अंतिम कोने के पहचानकर्ता, किनारे के पहचानकर्ता और संबंधित जानकारी वाले तत्वों की एक सूची बनाते हैं, जो वास्तव में आसन्न कोने की सूची के रूप में एक ग्राफ है।

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

सही बिंदु, जिनके बीच की दूरी 1 मीटर से कम है, उनमें अलग-अलग चाबियां हो सकती हैं, इसलिए हम कंटेनर को न केवल गणना की गई कुंजी से, बल्कि 8 पड़ोसी लोगों द्वारा भी जांचते हैं:

 std::vector<size_t> near; size_t xPart = keyPartX(px); size_t yPart = keyPartY(py); near.clear(); merge(near, getKey(xPart, yPart)); merge(near, getKey(xPart + 1, yPart)); merge(near, getKey(xPart - 1, yPart)); merge(near, getKey(xPart, yPart + 1)); merge(near, getKey(xPart, yPart - 1)); merge(near, getKey(xPart + 1, yPart + 1)); merge(near, getKey(xPart + 1, yPart - 1)); merge(near, getKey(xPart - 1, yPart + 1)); merge(near, getKey(xPart - 1, yPart - 1)); 

मर्ज () वेक्टर में निकटतम बिंदुओं के पहचानकर्ताओं को सूचीबद्ध करता है।
पड़ोसियों (वास्तव में, एक शीर्ष में विलय के लिए उम्मीदवार) के पहचानकर्ताओं की सूची प्राप्त करने के बाद, हम उनके बीच सटीक यूक्लिडियन दूरी की गणना करते हुए, अंक की तुलना करते हैं। और यदि यह निर्दिष्ट से कम है, तो हम मानते हैं कि अंक समान हैं और एक वर्टेक्स में विलय कर दिया गया है (चित्र में समान रंग चित्रित किया गया है), getKey कुंजी (xPart, yPart) के साथ सेल में पहले से ही एक उपयुक्त शीर्ष की पहचानकर्ता को लौटाता है।
शुरुआत में, इस प्रसंस्करण में लगभग 1 सेकंड लगता है, जो हमें सूट करता है।

4. परिणामस्वरूप, हम प्राप्त करते हैं कि किसी दिए गए सीमा की तुलना में पड़ोसी बिंदु एक पहचानकर्ता प्राप्त करते हैं।
अब हमारे पास आसन्न कोने की एक सूची है। इस तरह की सूची प्राप्त करने की समय जटिलता लंबवत संख्याओं पर निर्भर करती है, क्योंकि हम हर एक को ठीक 1 बार संसाधित करते हैं, और हैश कंटेनर में खोज और सम्मिलित संचालन में असमान रूप से निरंतर जटिलता होती है।

जैसा कि आपने देखा होगा, हम बहुभुज सड़क खंड के मध्यवर्ती कोने को संसाधित नहीं करते हैं, क्योंकि वे ग्राफ टोपोलॉजी को प्रभावित नहीं करते हैं (खंड के बीच में कोई पैंतरेबाज़ी नहीं की जा सकती है, किसी भी मामले में हमारे पास कोई डेटा नहीं है)।

यदि हम पॉलीलाइन को उन खंडों में विभाजित करते हैं जो इसे बनाते हैं और प्रत्येक खंड को एक किनारे मानते हैं, तो लगभग 140,000 किनारों के बजाय पहले से ही ग्राफ में लगभग 600,000 किनारे होंगे। पथ के लिए खोज समय में काफी वृद्धि होगी, अंत में मैं पूर्ण मूल्यों में यह अंतर दिखाऊंगा।

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

मैं एक उदाहरण दूंगा:

अंजीर। 2

लाल तीर निषिद्ध पैंतरेबाज़ी का संकेत देते हैं, संख्या खंड पहचानकर्ताओं को दर्शाते हैं। वास्तव में, डेटा में, यह प्रतिबंध {e1, e4} जैसा दिखता है।

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

ऐसा करने के लिए, हमने निषिद्ध पैंतरेबाज़ी में शामिल चोटियों की नकल की। और पसलियों को इस तरह से डुप्लिकेट किए गए शिखरों के माध्यम से लटका दिया गया था ताकि अनुमत युद्धाभ्यास बनाया जा सके, और निषिद्ध पैंतरेबाज़ी के लिए, इस तरह का मार्ग बस नहीं बनाया जा सकता था।

जब किसी शीर्ष पर क्लोन किया जाता है, तो इसकी ज्यामितीय स्थिति समान रहती है (आकृति में दिखाया गया वर्टिकल v6 और v5 वास्तव में एक ही स्थान पर ज्यामितीय होते हैं और सुविधा के लिए आकृति में स्थित होते हैं), निश्चित रूप से, नए शीर्ष के लिए एक नया पहचानकर्ता आवंटित किया जाता है।

मैं यह स्पष्ट करूँगा कि ऊपर दिए गए निषिद्ध बाएं मोड़ के साथ चौराहे के उदाहरण पर क्या कहा गया था:

अंजीर 3।

यह देखा जा सकता है कि परिवर्तित टोपोलॉजी के साथ ग्राफ पर, चौराहे पर निषिद्ध पथ के साथ एक बाएं मोड़ बनाना संभव नहीं है, जबकि सभी अनुमत युद्धाभ्यास संभव हैं।

2 से अधिक किनारों से बाधाओं को एक ही सिद्धांत के अनुसार संसाधित किया जाता है, लेकिन अधिक नए कोने और किनारों को उत्पन्न करते हैं, ये परिवर्तन ग्राफ़ के आकार को प्रभावित करते हैं, लेकिन महत्वपूर्ण रूप से (किनारों की संख्या में लगभग 5% की वृद्धि)। हमारे डेटा में, दो खंडों से लगभग 5000 प्रतिबंध हैं और तीन से लगभग 400)।

यहाँ इस बात का चित्रण है कि एक ग्राफ 3 किनारों की बाधा के तहत कैसे बदलता है:
यह था:

अंजीर ४।

यह बन गया:

अंजीर ५।

मुझे कहना होगा कि ग्राफ परिवर्तन एल्गोरिथ्म का कार्यान्वयन सभी कार्यों का सबसे कठिन चरण बन गया (इसमें लगभग 30% समय लगा) और यह वहाँ था कि सबसे बड़ी संख्या में बग थे। यह आंशिक रूप से तथाकथित अच्छी तरह से विकसित डेटा भंडारण संरचना के कारण है। इसलिए अगर कुछ समझ में नहीं आया - यह डरावना नहीं है, तो यह वास्तव में आसान नहीं था, सवाल पूछें, जवाब देने की कोशिश करें।

साधनों के बारे में।

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

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

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

इस सूचकांक का उपयोग करते हुए, हम जल्दी से निकटतम उम्मीदवारों को ढूंढते हैं, जिनमें से सटीक एल्गोरिदम दिए गए बिंदु के निकटतम खंड को निर्धारित करता है।

SHP फ़ाइलों को पढ़ने के लिए हमने GDAL लाइब्रेरी का उपयोग किया, भौगोलिक समन्वय प्रणालियों के बीच रूपांतरण के लिए (हम शहर की स्थानीय प्रणाली में काम करते हैं, यह ऐतिहासिक रूप से हुआ है), और यह उपयोगकर्ता के लिए GPS (WGS84) निर्देशांक का उपयोग करने के लिए अधिक सुविधाजनक है, हमने proj4 पुस्तकालय लिया, और पाठ एन्कोडिंग iconv के कार्यों के लिए।

विवरण के बारे में।

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


अंजीर ६।

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

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

2) एक निरर्थक ग्राफ बनाना: सड़क नेटवर्क के सभी ज्यामितीय कोने ग्राफ के कोने में बदल जाते हैं।
प्लस: लागू करने के लिए आसान है
विपक्ष: दिज्क्स्ट्रा एल्गोरिथ्म के काम के समय में एक महत्वपूर्ण वृद्धि, कुछ मामलों में यह समस्या को हल नहीं करता है (लंबे समय तक सड़क पर चलने)

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

हमने तीसरा रास्ता चुना है। टूटे हुए खंड और 2 किनारों पर स्थित उपयोगकर्ता बिंदु के सबसे करीब एक वर्टेक्स (खंड के कुछ हिस्सों से शुरू और अंत तक, या उनमें से केवल एक, यदि सेगमेंट एक-तरफा है) अस्थायी रूप से ग्राफ में जोड़ दिए जाते हैं, तो इन वर्टेक्स और किनारों को जोड़ दिया जाता है ग्राफ, एक खोज की जाती है, जिसके बाद अस्थायी कोने और किनारों को ग्राफ से हटा दिया जाता है।

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

- मल्टीथ्रेडिंग
यहां सब कुछ सरल है। हमारा कार्यक्रम 1 थ्रेड में चलता है। लेकिन अगर आपको वास्तव में सर्वर के सभी कर्नेल को लोड करने की आवश्यकता है, तो आप प्रत्येक कोर के लिए 1 उदाहरण चला सकते हैं, क्योंकि 1 प्रक्रिया को ग्राफ़ को संग्रहीत करने के लिए लगभग 300 एमबी की आवश्यकता होती है (और इस आकार को 2-3 गुना कम किया जा सकता है, लेकिन हमने अभी तक यह कार्य स्वयं निर्धारित नहीं किया है अनावश्यक)। प्रक्रियाओं द्वारा अनुरोध कैसे वितरित करें? चूंकि हमारे पास एक बाह्य प्रेषण कार्यक्रम है, यह कार्य प्रक्रियाओं के अनुरोधों के वितरण के साथ-साथ उनके प्रदर्शन की निगरानी कर सकता है, आदि।
सभी कोर लोड करने के लिए एक और विकल्प: C ++ में एक बहु-थ्रेडेड प्रोग्राम बनाना, हमें अधिक कठिन लग रहा था। सबसे पहले, हमें C ++ में नेटवर्क कोड लिखना होगा (लगभग परियोजना का पूरा सर्वर हिस्सा n.js पर लिखा गया था और हम जानते थे कि इस पर नेटवर्क के साथ काम करना बहुत आसान है), या बाहरी डिस्पैचर के लिए एक अधिक जटिल इंटरफ़ेस बनाना stdin / stdout की तुलना में। दूसरे, हमारे पास अस्थाई छोरों और किनारों के कारण केवल-पढ़ने के लिए ग्राफ़ नहीं है, जिसका अर्थ है कि हमें वर्कफ़्लोज़ को बहुत सावधानी से सिंक्रनाइज़ करना होगा ताकि एक तरफ प्रदर्शन को न मारें और दूसरी तरफ मल्टीथ्रेड कोड कोड की संबंधित समस्याओं में न चलें। ऐसा करने के लिए इस समय (इस समय) दृष्टिकोण के साथ लाभ मिला।

निष्कर्ष में, कुछ आँकड़े:
पूरा कार्यक्रम केवल 1,500 लाइनें निकला, साथ ही नोड.जेएस पर डिस्पैचर की कई दर्जन लाइनें, 1 व्यक्ति कोडिंग में लगा हुआ था, लगभग 1 महीने का समय लगा + एक सहकर्मी ने विचारों और डिबगिंग में मदद की। यह हमारे लिए बहुत अच्छा लगता है इस तरह के सबसे प्राथमिक कार्य नहीं है।

औसत मार्ग खोज समय (कोर i7 3.4 Ghz पर) लगभग 60-65 एमएस है। वैसे, मैंने ग्राफ़ पर ऑपरेटिंग समय कहने का वादा किया था, जहां टूटी सड़क के प्रत्येक खंड को ग्राफ़ के एक अलग किनारे में बदल दिया जाता है, यह लगभग 250 एमएस है, एक ध्यान देने योग्य अंतर है, सहमत हूं।

जो अंत तक पढ़े हैं, उन पर ध्यान देने के लिए आपका धन्यवाद।