एक बार फिर एक बिंदु बादल में सबसे बड़ी एकाग्रता खोजने के बारे में

एक बार फिर, मुझे एक काम मिला - बिंदुओं के बादल में खोजने के लिए उनकी सबसे बड़ी संवेदना का स्थान। इस बार स्थिति इस प्रकार थी:

• एक निश्चित राशि है (हम मान सकते हैं कि 16 मिलियन से अधिक नहीं) पैरामीटर सेट के माप के। सेट में मापदंडों की संख्या 2 से 5 तक है।
• मापदंडों का माप अपेक्षाकृत सफल हो सकता है - फिर उनका परिणाम सही के करीब होगा (पैरामीटर और वितरण के प्रकार अज्ञात हैं), या सफल नहीं हैं - फिर परिणाम यादृच्छिक होगा (फिर से अज्ञात वितरण मापदंडों के साथ)। यह एक माप से निर्धारित नहीं किया जा सकता है कि क्या यह सफल था।
• हम मान सकते हैं कि संक्षेपण बिंदु मौजूद है। यदि उनमें से कई समान गुणवत्ता वाले हैं (जो औपचारिक रूप से परिभाषित नहीं हैं), तो आप कोई भी जारी कर सकते हैं।
• उत्तर स्रोत डेटा पर एक पास में दिया जाना चाहिए: उन्हें फिर से गणना करें या पूरे - महंगे को बचाएं।
• और, हमेशा की तरह, मैं चाहता हूं कि एल्गोरिथ्म सरल दिखे और तेजी से काम करे।

सादगी के लिए, हम मान सकते हैं कि मापा पैरामीटर मान 0 से 1 तक की वास्तविक संख्याएं हैं। परिणाम 5 मापदंडों के मामले के लिए 3 दशमलव स्थानों का एक रिज़ॉल्यूशन प्राप्त करने के लिए वांछनीय होगा, और 4 या उससे कम मापदंडों के लिए 4 या अधिक।

यह स्पष्ट है कि बड़ी संख्या में शुरुआती बिंदु प्रसंस्करण बिंदुओं के आधार पर तरीकों को संदिग्ध बनाते हैं। यहां तक ​​कि निकटतम बिंदु तक की दूरी के लिए एक प्रभावी खोज को ध्यान देने योग्य कार्यान्वयन प्रयास की आवश्यकता होगी।

हिस्टोग्राम का निर्माण भी आसान नहीं है: यहां तक ​​कि वांछित सेल आकार पहले से ज्ञात नहीं है। यह संभव है, उदाहरण के लिए, सभी माप 0.1 के व्यास के साथ एक गेंद में परिणाम देंगे, और सफल लोगों को आकार 0.003 के क्षेत्र में स्थानीयकृत किया जाएगा। और इस क्षेत्र की स्थिति (एन-आयामी अंतरिक्ष में!) देना आवश्यक होगा।

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

जो विकल्प मुझे सबसे अधिक आशाजनक लगा, वह है केडी ट्री का उपयोग। यदि हम एक बाइनरी ट्री का निर्माण करते हैं, जिसमें से प्रत्येक नोड एक निर्देशांक के अनुसार अंतरिक्ष क्षेत्र को दो भागों में विभाजित करने से मेल खाती है (निर्देशांक चक्र द्वारा क्रमबद्ध हैं - x ₁ , x ₂ , ..., x _k , x ₁ , x ₂ , ...), और बिंदुओं की संख्या ज्ञात करें। जो प्रत्येक क्षेत्र में आते हैं, आप ऐसा कर सकते हैं।

अंक N को N से कम K का मान चुनें, उदाहरण के लिए, K = [sqrt (N)] या K = [N ^2/3 ]। हम कम से कम K अंक वाले सबसे छोटे आयतन (यानी, पेड़ की सबसे बड़ी गहराई पर स्थित) का क्षेत्र पाते हैं। यदि ऐसे कई क्षेत्र हैं, तो उस बिंदु को लें जिसमें अधिकांश बिंदु हैं। उसके बाद, हम इसे आधे हिस्से में विभाजित करना शुरू कर देंगे (आगे पेड़ नीचे जाना), हर बार एक आधा चुनना जिसमें अधिक अंक हैं। जब हम शीट पर पहुंचे (उदाहरण के लिए, एक बिंदु पर), हम इसे एक उत्तर के रूप में जारी करते हैं।

आप ऐसे उदाहरण पा सकते हैं जिसमें यह एल्गोरिदम संक्षेपण के मुख्य क्षेत्र को याद करेगा और इसके बजाय कुछ स्थानीय विसंगति का चयन करेगा, या प्रतिक्रिया के रूप में संक्षेपण के केंद्र से एक बिंदु दूर होगा, लेकिन आप उम्मीद कर सकते हैं कि ज्यादातर मामलों में इसके उत्तर कम या ज्यादा होंगे पर्याप्त। दुर्भाग्य से, केडी के पेड़ का निर्माण महंगा है, और इसमें बहुत सारी मेमोरी लगती है। मैं प्रति प्वाइंट 8 बाइट आवंटित करने के लिए तैयार हूं, लेकिन अधिक खर्च करना वांछनीय नहीं होगा।

समय और स्मृति को बचाने के लिए, मैंने स्पष्ट रूप से एक kd पेड़ बनाने का फैसला किया।

मान लीजिए कि हमारे पास एक बिंदु (x ₁ , x ₂ , ..., x _k ) है। हम बाइनरी सिस्टम में इसके निर्देशांक लिखते हैं
x ₁ = 0.x ₁₁ x ₁₂ x ₁₃ ...
x ₂ = 0.x ₂₁ x ₂₂ x ₂₃ ...
x ₃ = 0.x ₃₁ x ₃₂ x ₃₃ ...
...

और हम 64-बिट पूर्णांक बनाएंगे
P = x ₁₁ x ₂₁ ... x _k1 x ₁₂ ... x _k2 ...

यह संख्या पेड़ के माध्यम से 64 की गहराई तक पथ का प्रतिनिधित्व करती है। इसके अलावा, यह आपको आवश्यक सटीकता के साथ एक बिंदु के निर्देशांक को पुनर्स्थापित करने की अनुमति देता है।

यदि हम आरोही क्रम में सभी बिंदुओं के लिए P कोड को सॉर्ट करते हैं, तो हमें पेड़ के ट्रैवर्सल के क्रम में अंक मिलते हैं। किसी भी दो बिंदु P _a और P _{b के लिए,} सबसे गहरे नोड को खोजना आसान है, जिसके सामान्य वंशज वे हैं: यह संख्या P P _a ^ _b में सबसे महत्वपूर्ण नॉनजरो बिट खोजने के लिए पर्याप्त है। और इस प्रतिनिधित्व पर समस्या के सभी आवश्यक टुकड़े कई लाइनों में हल किए गए हैं:

उस स्तर की खोज करें जिस पर कम से कम K अंक वाले सबसे छोटे बिंदु स्थित हैं:

ulong mask=ulong.MaxValue; K--; for(int i=K;i<m_np;i++) mask=Math.Min(mask,m_Arr[i]^m_Arr[iK]); 

यहाँ m_Arr कोड की एक सरणी है, m_np इसमें भरे हुए तत्वों की संख्या है, मास्क एक संख्या है जिसका उच्च बिट वांछित स्तर निर्धारित करता है।

पाया स्तर पर एक क्षेत्र के लिए खोजें जिसमें अधिकतम अंक हों (हम जानते हैं कि कम से कम K हैं):

  mask=InvMask(mask); int ms=0,me=0; for(int i=0;i<m_np-K;i++){ ulong a=m_Arr[i]; int h=i+K; if(((a^m_Arr[h])&mask)==0){ while(h<m_np-1 && ((a^m_Arr[h+1])&mask)==0) h++; K=hi; ms=i; me=i=h; } } 

यहाँ InvMask (मास्क) सभी बिट्स में 1 से युक्त मास्क की गणना है जो मास्क मास्क के सबसे पुराने गैर-शून्य बिट से अधिक वरिष्ठ हैं। यह एमएस की गणना करता है - वांछित क्षेत्र की शुरुआत और मुझे - इसका अंत।

एक भारी वंशज के लिए खोजें:

  int h=(ms+me)/2; ulong samp=m_Arr[h]; ulong cb=samp^m_Arr[ms],ce=samp^m_Arr[me]; if(cb>ce) { ms=h; ce=InvMask(ce); while(ms>0 && ((m_Arr[ms-1]^samp)&ce)==0) ms--; } else { me=h; cb=InvMask(cb); while(me<m_np-1 && ((m_Arr[me+1]^samp)&cb)==0) me++; } 

यहां वंश जरूरी नहीं कि एक स्तर का हो।
इस प्रकार, संक्षेपण की खोज का कार्य हल हो गया है।

पूरा कार्यक्रम 100 लाइनों में फिट होता है, स्रोत (सी # में) यहां पाया जा सकता है ।

वास्तविक कार्य में थोड़ा अधिक जटिल सूत्रीकरण है। पैरामीटर में परिवर्तन की सीमा पहले से ज्ञात नहीं है, इसके अलावा, नमूने में माप योजनाबद्ध 16 मिलियन से बड़ा हो सकता है, और "अच्छा" माप अंत की ओर जा सकता है। लेकिन एल्गोरिथ्म के छोटे संशोधन इन समस्याओं का सामना कर सकते हैं। उदाहरण के लिए, यदि सरणी में जगह समाप्त हो जाती है, और अंक प्रवाहित होते रहते हैं, तो हम पहले से डायल किए गए कोड के सरणी को छांट और पतला कर सकते हैं - इससे मोटा होने की स्थिति और गुणवत्ता प्रभावित नहीं होगी।

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