रेंज

Question

के साथ कई पैरामीटर द्वारा ऑब्जेक्ट्स को खोजने के लिए कुशल डिज़ाइन मेरे पास मेमोरी में एक ही प्रकार की ऑब्जेक्ट्स का एक सेट है और प्रत्येक में कई अपरिवर्तनीय int गुण हैं (लेकिन केवल उन्हें नहीं)।

मुझे वहां एक वस्तु (या एकाधिक) खोजने की आवश्यकता है, जिनकी गुण निर्दिष्ट मानों के पास छोटी सीमा में हैं। जैसे a == 5+-1 && b == 21+-2 && c == 9 && any d।

ऑब्जेक्ट्स स्टोर करने का सबसे अच्छा तरीका क्या है ताकि मैं उन्हें कुशलता से पुनर्प्राप्त कर सकूं?

मैंने प्रत्येक संपत्ति के लिए SortedList बनाने और BinarySearch का उपयोग करने के बारे में सोचा लेकिन मेरे पास बहुत सारी संपत्तियां हैं इसलिए मैं SortedLists के बजाय अधिक सामान्य तरीका प्राप्त करना चाहता हूं।

यह महत्वपूर्ण है कि सेट स्वयं अपरिवर्तनीय न हो: मुझे वस्तुओं को जोड़ने/निकालने की क्षमता चाहिए।

क्या वस्तुओं के लिए मेमोरी डीबी की तरह कुछ है (केवल डेटा नहीं)?

Answer 1

बस @ j_random_hacker के उत्तर पर विस्तार करने के लिए थोड़ा सा: चुनिंदाता के अनुमानों का सामान्य दृष्टिकोण सूचकांक के लिए हिस्टोग्राम बनाना है। लेकिन, आप पहले से ही जानबूझकर जान सकते हैं कि कौन सा मानदंड "ए == 5 + -1 & & बी == 21 + -2 & & सी == 9" से निर्धारित सबसे प्रारंभिक परिणाम उत्पन्न करने जा रहा है। सबसे अधिक संभावना है कि यह "सी == 9" है जब तक कि 'सी' के लिए संभावित मूल्यों की डुप्लिकेट मानों और छोटे ब्रह्मांड की असाधारण उच्च संख्या न हो।

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

उस बिंदु से, आरडीबीएमएस 'शेष भविष्यवाणियों के लिए फ़िल्टर करने के लिए परिणाम सेट में रिकॉर्ड्स का अनुक्रमिक स्कैन करेगा। यह शायद आपका सबसे अच्छा दृष्टिकोण भी है।

या, स्मृति में कोई भी संख्या है, छोटे पदचिह्न एसक्यूएल-सक्षम डीबीएमएस जो आपके लिए भारी उठाने (eXtremeDB, SQLite, RDM, ...google आपका मित्र है) और/या उसके पास निम्न-स्तरीय इंटरफेस हैं जो आपके लिए सभी काम नहीं करेंगे (अभी भी, अधिकतर) लेकिन आपके लिए एसक्यूएल भी लागू नहीं करेंगे।

Answer 2

सबसे पहले, SortedList एस बहुत खराब डिज़ाइन नहीं है। यह अनिवार्य रूप से तरीका है कि सभी आधुनिक आरडीबीएमएस एक ही समस्या को हल करते हैं।

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

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