एल्गोरिदम?

Question

एक्स, वाई निर्देशांक के साथ कई मिलियन अंकों के सेट को देखते हुए, किसी स्थान से शीर्ष 1000 निकटतम बिंदुओं को तुरंत ढूंढने के लिए पसंद का एल्गोरिदम क्या है? "जल्दी" यहां घर कंप्यूटर पर लगभग 100ms का मतलब है।

ब्रूट फोर्स का मतलब लाखों गुणा करने और फिर उन्हें सॉर्ट करना होगा। यहां तक ​​कि एक साधारण पायथन ऐप भी एक मिनट से भी कम समय में ऐसा कर सकता है, फिर भी यह एक इंटरैक्टिव एप्लिकेशन के लिए बहुत लंबा है।

अंक के लिए सीमांकन बॉक्स में जाना जाएगा, तो एक सरल ग्रिड में अंतरिक्ष विभाजन संभव हो जाएगा। हालांकि अंक कुछ हद तक असमान रूप से वितरित किए जाते हैं, इसलिए मुझे संदेह है कि अधिकांश ग्रिड वर्ग खाली होंगे और फिर उनमें से कुछ में अंक का एक बड़ा हिस्सा होगा।

संपादित करें: सटीक नहीं होना चाहिए, वास्तव में काफी गलत हो सकता है। यदि शीर्ष 1000 वास्तव में उदाहरण के लिए शीर्ष 2000 से कुछ यादृच्छिक बिंदु हैं तो यह एक बड़ा सौदा नहीं होगा।

संपादित करें: बिंदुओं का सेट शायद ही कभी बदलता है।

Answer 1

कैसे quadtree का उपयोग कर के बारे में?

यदि क्षेत्र में कम घनत्व है, आयताकार बड़े हैं, और यदि क्षेत्र में अंक की उच्च घनत्व है, तो आयताकार छोटे होंगे। आप आयताकार रूप से प्रत्येक आयताकार को चार उप आयताकारों तक उप-विभाजित करते हैं जब तक कि आयत पर्याप्त न हों या कुछ पर्याप्त बिंदु न हों।

फिर आप स्थान के पास आयतों के किसी बिंदु पर तलाश शुरू, और बाहर ले जाने के जब तक आप अपने 1000 अंक पाया है सकते हैं। इस के लिए

कोड कुछ जटिल हो सकता है, तो हो सकता है आप पहले सरल ग्रिड के साथ कोशिश करते हैं और अगर यह काफी तेज है देखना चाहिए।

Answer 2

Quadtrees अच्छे हैं, लेकिन BSP trees (लॉग एन) समय हे में चलाने के लिए गारंटी है। मुझे लगता है कि क्वाड्रिस को एक सीमित बाउंडिंग वॉल्यूम की आवश्यकता होती है, और कुछ अपमानजनक मामले होते हैं जहां क्वाड्रिस बुरी तरह विफल हो जाते हैं, जैसे कि बड़ी संख्या में अंक समान अपेक्षाकृत छोटी जगह पर कब्जा करते हैं।

कहा जा रहा है, Quadtrees यकीनन लागू करने के लिए आसान है और सबसे आम स्थितियों में काफी प्रभावी हैं। यूपीएस उनके रूटिंग एल्गोरिदम में उपयोग करता है, क्योंकि इसमें कमीएं अभ्यास में महत्वपूर्ण समस्याएं उत्पन्न नहीं करती हैं, संभवतः क्योंकि शहरों में रुचि के क्षेत्र में फैलता है।

Answer 3

मुझे लगता है कि अंक डेटाबेस में हैं या कुछ खोजे जाने योग्य अनुक्रमित स्थान हैं? यदि ऐसा है तो यह बहुत तेज़ होना चाहिए। दिए गए बिंदु से आप एक्स और वाई अक्ष पर एक सीमा प्राप्त कर सकते हैं और उस सीमा के भीतर सभी स्थानों को प्राप्त कर सकते हैं (यानी शीर्ष बाएं कोने एक्स (ए) और वाई (बी) और नीचे सबसे दाएं कोने एक्स (सी) और वाई निर्दिष्ट करें (घ))।

फिर एक प्रश्न करना जहां अंक के लिए जहां y> = ख और वाई < = डी और एक्स> = एक और एक्स < = c। यह जल्दी से माना जाएगा कि आपके पास एक्स और वाई निर्देशांक पर अलग-अलग इंडेक्स हैं। (माना जाता है कि मूल बाईं ओर 0,0 है)।

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

एक बार जब आपके पास कोई मोटा डेटा प्रत्येक बिंदु और स्रोत बिंदु के बीच की दूरी को काम करने के लिए अपने सुंदर सरल गणित सेट करता है।

Answer 4

आप एक क्वाड पेड़, या एक आरटीआई जैसे संरचना का उपयोग करना चाहते हैं। ये बहुआयामी सूचकांक संरचनाएं हैं।

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

http://en.wikipedia.org/wiki/Space_filling_curve

मैं इस सामान में से किसी पूर्व-पैकेज कार्यान्वयन की पता नहीं है। मैंने हाल ही में 2 आयामों में अपनी खुद की आरटीआई लागू की है जो केवल थोक लोडिंग और खोजों (प्रदान किए गए बाउंडिंग बॉक्स के माध्यम से) का समर्थन करती है।

यहां एक दोष यह है कि आपके अंक को एक सीमित क्षेत्र में निहित होना है। वहां पता है कि अंतरिक्ष भरने वाले वक्र हैं जो रिक्त स्थान के लिए काम नहीं करते हैं, लेकिन मुझे उनके बारे में कुछ भी पता नहीं है।

Answer 5

यदि अंक का सेट शायद ही कभी बदलता है, तो आप एक वोरोनोई आरेख का उपयोग करने पर भी विचार कर सकते हैं। मुझे यकीन नहीं है कि अगर पहले पॉइंट तेजी से खोजने में मदद करता है, लेकिन इसे अगले 999 अंक ढूंढना बहुत आसान बनाना चाहिए।

Answer 6

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

Answer 7

मुझे पता है कि यह वास्तव में सबसे तेज़ नहीं है क्योंकि आप वास्तव में तेजी से परिणाम चाहते हैं कि मुझे यह पोस्ट Google से मिला है, मैंने सोचा था कि मैं अपना एसक्यूएल समाधान जोड़ूंगा जिसे मैंने थोड़ी देर पहले संग्रहीत किया था प्रोक। यह एक समन्वयक के नजदीक स्थानों की तलाश करता है और उन्हें दूरी से वापस कर देता है।

मुझे आशा है कि यह मदद करता है किसी को :)

CREATE PROCEDURE [dbo].[getstores] @lat float, @lng float AS 
DECLARE @radius float, @DegToRad float 
SET @DegToRad = 57.29577951 
SET @radius = 25000 
SELECT TOP 10 
    name 
    ,sto_lat 
    ,sto_lng 
    ,postcode 
    ,ROUND((ACOS((SIN(@lat/57.2958) * SIN(sto_lat/@DegToRad)) +(COS(@lat/@DegToRad) * COS(sto_lat/@DegToRad) *COS(sto_lng/@DegToRad - @lng/@DegToRad))))* 6387.7, 2) AS distance 
FROM store 
WHERE (sto_lat >= @lat - (@radius/111)) 
And (sto_lat <= @lat + (@radius/111)) 
AND (sto_lng >= @lng - (@radius/111)) 
AND (sto_lng <= @lng + (@radius/111)) 
AND (
    ISNUMERIC(sto_lat) = 1 
    AND 
    ISNUMERIC(sto_lat) = 1 
) 
ORDER BY distance 

नोट: मैं पहले से ही कहा है कि इस लिए सबसे अच्छा समाधान नहीं है इस सवाल का बस किसी के लिए हो सकता है, जो मेरे जैसे