रेडिस या मोंगो यह निर्धारित करने के लिए कि कोई संख्या सीमा के भीतर आती है या नहीं?

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

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

इस प्रकार की समस्या को हल करने के लिए, एक समर्पित अनुक्रमण संरचना की आवश्यकता है। आप इस पर एक नज़र डालना चाहेंगे:

http://en.wikipedia.org/wiki/Segment_treeorhttp://en.wikipedia.org/wiki/Interval_tree

यदि चिंता स्थान पर गति की है, तो सूचकांक को समतल करना दिलचस्प हो सकता है। उदाहरण के लिए, आइए निम्नलिखित श्रेणियों पर विचार करें (चर्चा को सरल बनाने के लिए केवल पूर्णांकों का उपयोग करके):

A 2-8
B 4-6
C 2-9
D 7-10

गैर अतिव्यापी खंडों को अनुक्रमित करते हुए एक विरल संरचना का निर्माण किया जा सकता है।

0  []
2  [A C]
4  [A C B]
7  [A C D]
9  [C D]
10 [D]
11 []

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

5 से मेल खाने वाली श्रेणियों को खोजने के लिए, हम पहली प्रविष्टि की तलाश करते हैं जो 5 से कम या बराबर हो (यह इस उदाहरण में 4 होगी) और श्रेणियों की सूची प्रदान की जाती है ( [ए सी बी])

इस डेटा संरचना के साथ, प्रश्नों की जटिलता वास्तव में ओ (लॉग एन) है। हालांकि इसे बनाना और बनाए रखना मामूली (और महंगा) नहीं है। इसे मोंगोडब और रेडिस दोनों के साथ लागू किया जा सकता है।

यहां रेडिस के साथ एक उदाहरण दिया गया है:

> rpush range:2 2-8 2-9
(integer) 2
> rpush range:4 2-8 2-9 4-6
(integer) 3
> rpush range:7 2-8 2-9 7-10
(integer) 3
> rpush range:9 2-9 7-10
(integer) 2
> rpush range:10 7-10
(integer) 1
> zadd range_index 0 range:0 2 range:2 4 range:4 7 range:7 9 range:9 10 range:10
(integer) 6
> zrevrangebyscore range_index 5 0 LIMIT 0 1
1) "range:4"
> lrange range:4 0 -1
1) "2-8"
2) "2-9"
3) "4-6"