एल्गोरिथ्म मूल

Question

पहले 100 निकटतम सितारों उचित सवाल को खोजने के लिए जाने के लिए मुझे वाक्यांश:

प्रश्न: एक लाख से अधिक अंक (एक्स, वाई), जिनमें से प्रत्येक एक स्टार का प्रतिनिधित्व करता वाली फ़ाइल नहीं है। एक ग्रह पृथ्वी है (ए, बी)। अब, कार्य एक एल्गोरिदम बनाने के लिए है जो 100 निकटतम सितारों को पृथ्वी पर वापस कर देगा। आपके एल्गोरिदम का समय और स्थान जटिलता क्या होगी।

इस सवाल को विभिन्न साक्षात्कारों में कई बार पूछा गया है। मैंने जवाब देखने की कोशिश की लेकिन एक संतोषजनक नहीं मिला।

ऐसा करने का एक तरीका जो मैंने सोचा था कि आकार 100 का अधिकतम ढेर उपयोग कर सकता है। प्रत्येक स्टार के लिए दूरी की गणना करें और जांच करें कि अधिकतम ढेर की जड़ से दूरी कम है या नहीं। यदि हां, तो इसे रूट के साथ बदलें और हेपफी को कॉल करें।

कोई अन्य बेहतर/तेज उत्तर?

पीएस: यह होमवर्क प्रश्न नहीं है।

Answer 1

आप वास्तव में समय ओ (एन) और स्पेस ओ (के) में ऐसा कर सकते हैं, जहां के बहुत ही चालाक चाल का उपयोग करके आप निकटतम बिंदुओं की संख्या है।

selection problem इस प्रकार है: तत्वों की एक सरणी और कुछ सूचकांक मैं, सरणी के तत्वों को पुनर्व्यवस्थित को देखते हुए ऐसी है कि ith तत्व सही जगह में है, सभी तत्वों के ith तत्व की तुलना में छोटे बाईं ओर हैं , और ith तत्व से अधिक सभी तत्व दाईं ओर हैं। उदाहरण के लिए, अगर मैं सूचकांक 2 (शून्य अनुक्रमित) के आधार पर चयन करने की कोशिश की सरणी

40 10 00 30 20 

को देखते हुए एक परिणाम हो सकता है

10 00 20 40 30 

सूचकांक 2 (20) पर तत्व के बाद से में है सही जगह, बाईं ओर के तत्व 20 से छोटे होते हैं, और दाएं तत्व 20 से अधिक होते हैं।

यह पता चला है कि चूंकि यह वास्तव में सरणी को सॉर्ट करने की तुलना में कम सख्त आवश्यकता है, इसलिए ऐसा करना संभव है यह समय में ओ (एन), जहां एन सरणी के तत्वों की संख्या है। ऐसा करने के लिए median-of-medians एल्गोरिदम जैसे कुछ जटिल एल्गोरिदम की आवश्यकता होती है, लेकिन वास्तव में ओ (एन) समय है।

तो आप इसका उपयोग कैसे करते हैं? एक विकल्प फ़ाइल से सभी एन तत्वों को एक सरणी में लोड करना है, फिर ओ (एन) समय और ओ (एन) स्पेस (यहां, के = 100) में शीर्ष के चयन के लिए चयन एल्गोरिदम का उपयोग करें।

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

नए दृष्टिकोण की जटिलता क्या है? खैर, आप बफर और चयन एल्गोरिदम के लिए ओ (के) मेमोरी का उपयोग कर रहे हैं। आप आकार ओ (के) के कुल बफर (ओ) के बफर पर कॉलिंग का चयन करते हैं, क्योंकि आप नए तत्वों को पढ़ने के बाद चयन करते हैं।चूंकि आकार ओ (के) के बफर पर चयन करने के समय ओ (के) लगता है, यहां कुल रनटाइम ओ (एन + के) है। यदि के = ओ (एन) (एक उचित धारणा), इसमें समय ओ (एन), स्पेस ओ (के) लगता है।

आशा है कि इससे मदद मिलती है!

Answer 2

यह एक प्रसिद्ध सवाल है और वहाँ बहुत कुछ के समाधान की है कि के लिए कर दिया गया है: http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm

अगर आप इसे उपयोगी नहीं मिला, इस तरह के Rurk के कम्प्यूटेशनल ज्यामिति पुस्तक के रूप में कुछ संसाधन हैं।

Answer 3

आपका एल्गोरिदम सही है। बस याद रखें कि आपके प्रोग्राम की समय जटिलता ओ (एन। लॉग 100) = ओ (एन) है, जब तक कि निकटतम बिंदुओं की संख्या अलग-अलग हो सकती है।

Answer 4

import sys,os,csv 

iFile=open('./file_copd.out','rU') 
earth = [0,0] 



##getDistance return distance given two stars 
def getDistance(star1,star2): 
    return sqrt((star1[0]-star2[0])**2 +(star1[1]-star2[1])**2) 


##diction dict_galaxy looks like this {key,distance} key is the seq assign to each star, value is a list [distance,its cordinance] 
##{1,[distance1,[x,y]];2,[distance2,[x,y]]} 
dict_galaxy={} 
#list_galaxy=[] 
count = 0 
sour=iFile.readlines() 
for line in sour: 
    star=line.split(',') ##Star is a list [x,y] 
    dict_galaxy[count]=[getDistance(earth,star),star] 
    count++ 

###Now sort this dictionary based on their distance, and return you a list of keys. 
list_sorted_key = sorted(dict_galaxy,key=lambda x:dict_galaxy[x][0]) 

print 'is this what you want %s'%(list_sorted_key[:100].to_s) 
iFile.close() 

Answer 5

मैक्सहेप समाधान पर विस्तृत करने के लिए आप फ़ाइल के पहले के तत्वों (इस मामले में के = 100) के साथ अधिकतम-ढेर का निर्माण करेंगे।

अधिकतम-ढेर के लिए कुंजी पृथ्वी (ए, बी) से इसकी दूरी होगी। एक 2d हवाई जहाज पर 2 अंक के बीच की दूरी का उपयोग कर गणना की जा सकती:

dist = (x1,y1) to (x2,y2) = square_root((x2 - x1)^2 + (y2 - y1)^2); 

यह निर्माण करने के लिए हे (के) समय लगेगा। के बाद से प्रत्येक से प्रत्येक तत्व के लिए। यानी (एन - के) तत्व जिन्हें आपको पृथ्वी से अपनी दूरी लाने की आवश्यकता है और अधिकतम-ढेर के शीर्ष से इसकी तुलना करें। यदि नया तत्व डाला जा सकता है तो अधिकतम-ढेर के शीर्ष की तुलना में पृथ्वी के करीब है, अधिकतम-ढेर के शीर्ष को प्रतिस्थापित करें और ढेर की नई जड़ पर हेपफीइफ़ करें।

यह ओ ((एन-के) लॉगक) पूरा करने के लिए समय लेगा। अंत में हम अधिकतम-ढेर में केवल के तत्वों के साथ छोड़े जाएंगे। आप इन सभी के तत्वों को वापस करने के लिए heapify k times को कॉल कर सकते हैं। यह एक और ओ (klogk) है।

कुल मिलाकर समय जटिलता ओ (के + (एन-के) logk + klogk होगा)।