निकटतम बिंदु

Question

मैं एक बहुत ही सरल Point वर्ग के लिए संकेत के वेक्टर है अंक का एक वेक्टर से बाहर का पता लगाएं?
क्या मुझे पहले वेक्टर को पहले क्रमबद्ध करने की आवश्यकता है या क्या कोई और अधिक प्रभावी तरीका है?

Answer 1

छंटाई O(n*log(N)) लेता है, तो यह बहुत ही कुशल नहीं है। आप इसे O(n) में केवल तत्वों के माध्यम से पुनरावृत्ति करके और सर्वोत्तम मिलान को याद करके कर सकते हैं।

<algorithm> से for_each का उपयोग करना, आप एक समारोह है कि निकटतम तत्वों का ट्रैक रखता है और O(n) में पूर्ण होती परिभाषित कर सकते हैं।

या, आप शायद min_element का भी उपयोग कर सकते हैं, <algorithm> से भी।

Answer 2

आप तेजी से एक रेखीय तुलना तो अगर आप केवल पता है कि एक सदिश में अंक हैं कि नहीं जा सकते। हालांकि यदि आपके पास अतिरिक्त ज्ञान है तो बहुत कुछ सुधार किया जा सकता है। उदाहरण के लिए यदि आप जानते हैं कि सभी बिंदुओं का आदेश दिया गया है और उसी पंक्ति पर झूठ बोलना है तो एक लॉगरिदमिक समाधान है।

इसके अलावा वहाँ उदाहरण एक k-d tree के लिए अपनी समस्या को हल करने के लिए बेहतर डेटा संरचनाओं हैं। यह एसटीएल का हिस्सा नहीं है - आपको इसे स्वयं लागू करना होगा, लेकिन यह आपके पास समस्या को हल करने के लिए उपयोग करने के लिए डेटा संरचना है।

Answer 3

यहाँ बुनियादी सवाल यह है कि अक्सर आप अंक का एक सेट के खिलाफ प्रश्नों करने जा रहे हैं है।

यदि आप एक बार सेट में एक नजदीकी बिंदु ढूंढने जा रहे हैं, तो @ लुइसियन सही है: आप अंक को बिना छेड़छाड़ कर सकते हैं, और सही बिंदु खोजने के लिए एक रैखिक खोज कर सकते हैं।

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

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

Answer 4

आप Quadtree http://en.wikipedia.org/wiki/Quadtree

या कुछ इसी तरह इस्तेमाल करने की कोशिश कर सकते हैं। ओ (_n_) के लिए