रेडिस: भारित निर्देशित ग्राफ लागू करें

Question

रेडिस का उपयोग करके भारित ग्राफ को लागू करने का सबसे अच्छा तरीका क्या है?

हम ज्यादातर ग्राफ़ पर कम से कम पथ के लिए खोज करेंगे

वर्तमान में हम

Redis के लिए प्रत्येक नोड के लिए किनारों को जोड़ने पर विचार किया (शायद डिज्कस्ट्रा कलन विधि का उपयोग), हम nodeId कुंजी के रूप में होगा और संदर्भित नोड्स की कुंजियों की एक क्रमबद्धता क्रमबद्ध सेट में प्रत्येक नोड आईडी का स्कोर किनारे का वजन है।

आपको क्या लगता है? मुझे सही अगर मैं गलत हूँ लेकिन यहाँ केवल बहुत बेकार एक sortedset में अगले नोड के लिए प्रत्येक क्वेरी के लिए हम ओ (logn) का भुगतान कि हे (1) के बजाय है ...

http://redis.io/commands/zrange

Answer 1

अगले हो रही है एक क्रमबद्ध सेट में आइटम केवल ओ (लॉग (एन)) है यदि आप उन्हें एक समय में बाहर निकाल रहे हैं, तो इस मामले में रेडिस के कनेक्शन की विलंबता ऑपरेशन की जटिलता की तुलना में अधिक समस्या होगी।

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

Answer 2

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

Graph = { node1 : { nodeX : edge_weight, nodeY : edge_weight, other_info: bla..}, 
      node2 : { nodeZ : edge_weight, nodeE : edge_weight, other_info: bla..}, 
      bla bla... 
     } 

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