फास्ट इलिप्सिड (एस) चौराहे एल्गोरिदम

Question

मान लें कि मुझे 1 मिलियन मनमाने ढंग से आकार दिया गया है, मनमाने ढंग से उन्मुख एन-आयामी इलिप्सोइड एन-आयामी अंतरिक्ष के माध्यम से यादृच्छिक रूप से बिखरे हुए हैं। एलीपसॉइड के एक उप सेट को देखते हुए, मैं सभी एलीपॉइड्स के सेट को "जल्दी" निर्धारित करना चाहता हूं कि पहले सेट से एलिप्सिपिड्स छेड़छाड़ करता है।

इसके लिए एक एल्गोरिदम होना चाहिए। यह क्या है? यह "ओ" जटिलता क्या है?

Answer 1

"ओ" जटिलता आयाम के अभिशाप से ग्रस्त है यदि आप एन-आयामी डेटा की अनुमति दे रहे हैं। (इसके बारे में अधिक जानकारी के लिए this wikipedia article देखें)। मैं भौतिकी सिमुलेशन से उधार और एक "व्यापक चरण" और एक संकीर्ण चरण में इस समस्या को विभाजित करने की सलाह देते:

• विस्तृत चरण परंपरागत ढंग से संभावित अतिव्यापी दीर्घवृत्त के जोड़े की काफी छोटे सेट पाता है।
• संकीर्ण चरण उन जोड़ों के लिए संभावित रूप से ओवरलैपिंग जोड़े के सेट को ट्रिम करता है जो वास्तव में ओवरलैप करते हैं।

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

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

एक केडी-पेड़ सभी एलिप्सिपिड्स के लिए आपकी समस्याओं को ठीक नहीं करेगा - उदाहरण के लिए, यदि आपके पास आयाम एन का इलिप्सिड है जिसका प्राथमिक अक्ष (0, 0, 0, 0, ...) से है (1, 1, 1, 1, ...) लेकिन छोटे या अपूर्ण माध्यमिक अक्षों के साथ (और अब से अधिक अंतर नहीं करता है) को अभी भी एक नोड होना चाहिए जो सभी एन आयामों में [0,1] को कवर करता है। यदि आपके इलिप्सोइड्स [0,1]^एन में आते हैं, तो प्रत्येक इलिप्सिड उपरोक्त असुविधाजनक एलिप्सिड के साथ छेड़छाड़ के लिए परीक्षण करेगा। हालांकि, असली दुनिया के डेटा के साथ (और यहां तक ​​कि सबसे सिंथेटिक जब तक कि आप वास्तव में केडी-पेड़ को धीमा करने के लिए कड़ी मेहनत नहीं कर रहे हैं) केडी-पेड़ दृष्टिकोण एक जीत होना चाहिए।

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

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

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