बड़ी संख्या में संख्याओं से बड़ी संख्या कैसे प्राप्त करें?

Question

मैं कम से कम 100000000 संख्याओं की सूची से सबसे बड़ा 100 तत्व प्राप्त करना चाहता हूं।

मैं पूरी सूची को सॉर्ट कर सकता हूं और क्रमबद्ध सूची से पिछले 100 तत्वों को ले सकता हूं, लेकिन यह स्मृति और समय दोनों के मामले में बहुत महंगा होगा।

क्या ऐसा करने का कोई मौजूदा आसान, पाइथोनिक तरीका है?

मैं जो चाहता हूं वह शुद्ध प्रकार की बजाय फ़ंक्शन का पालन करना है। असल में मैं ऐसे तत्वों को हल करने के लिए बर्बाद समय नहीं चाहता हूं जिनकी मुझे परवाह नहीं है।

getSortedElements(100, lambda x,y:cmp(x,y)) 

नोट इस आवश्यकता को केवल प्रदर्शन परिप्रेक्ष्य के लिए है:

उदाहरण के लिए, इस समारोह मैं करना चाहते हैं है।

Answer 1

मानक पुस्तकालय में heapq मॉड्यूल nlargest() फ़ंक्शन यह करने के लिए प्रदान करता है:

top100 = heapq.nlargest(100, iterable [,key]) 

यह पूरी सूची को सॉर्ट नहीं होगा तो आप तत्वों आप डॉन 'पर समय बर्बाद नहीं होगा टी जरूरत है

Answer 2

Selection algorithms यहां सहायता करनी चाहिए।

100 वां सबसे बड़ा तत्व खोजने के लिए एक बहुत ही आसान समाधान है, फिर इस तत्व से बड़े तत्वों को चुनने वाली सूची को चलाने के माध्यम से चलाएं। इससे आपको 100 सबसे बड़े तत्व मिलेंगे। यह सूची की लंबाई में रैखिक है; यह सबसे अच्छा संभव है।

अधिक परिष्कृत एल्गोरिदम हैं। उदाहरण के लिए, heap, इस समस्या के लिए बहुत ही उपयुक्त है। ढेर आधारित एल्गोरिदम n log k है जहां n सूची की लंबाई है और k उन सबसे बड़े तत्वों की संख्या है जिन्हें आप चुनना चाहते हैं।

चयन एल्गोरिदम के लिए विकिपीडिया पृष्ठ पर इस problem पर चर्चा की गई है।

संपादित करें: एक और पोस्टर ने इंगित किया है कि पाइथन इस समस्या के समाधान में बनाया गया है। जाहिर है कि खुद को रोल करने से कहीं ज्यादा आसान है, लेकिन अगर आप इस तरह के एल्गोरिदम काम करते हैं, तो मैं इस पोस्ट को तब तक रखूंगा जब आप सीखना चाहें।

Answer 3

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

एक ढेर में दो बुनियादी संचालन हैं जो आपकी मदद करेंगे: जोड़ें और बदलें।

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

जब भी आप पहले आइटम को किसी चीज़ के साथ बदलते हैं, तो ढेर में आंतरिक कोड ढेर सामग्री को समायोजित करेगा ताकि यदि नया आइटम सबसे छोटा न हो, तो यह ढेर में उछाल जाएगा, और सबसे छोटी वस्तु " बुलबुला नीचे "पहले तत्व के लिए, रास्ते में बदलने के लिए तैयार।

Answer 4

ऐसा करने का सबसे अच्छा तरीका एक ढेर क्रमबद्ध प्राथमिकता कतार को बनाए रखना है जिसे आप इसमें से 100 प्रविष्टियों के बाद बंद कर देते हैं।

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

जैसा कि पाइथन में उल्लेख किया गया है, आप हेपैक का उपयोग करेंगे। जावा PriorityQueue में: http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html

Answer 5

यहाँ एक समाधान मैं का इस्तेमाल किया है पुस्तकालयों से स्वतंत्र है और कहा कि किसी भी प्रोग्रामिंग भाषा सरणियों है कि में काम करेंगे:

initialisation:

Make an array of 100 elements and initialise all elements 
with a low value (less than any value in your input list). 

Initialise an integer variable to 0 (or any value in 
[0;99]), say index_minvalue, that will point to the 
current lowest value in the array. 

Initialise a variable, say minvalue, to hold the current 
lowest value in the array. 

प्रत्येक के लिए मान, वर्तमान_value कहें, इनपुट सूची में:

if current_value > minvalue 

    Replace value in array pointed to by index_minvalue 
    with current_value 

    Find new lowest value in the array and set index_minvalue to 
    its array index. (linear search for this will be OK as the array 
    is quickly filled up with large values) 

    Set minvalue to current_value 

else 
    <don't do anything!> 

minvalue wil मैं जल्दी से एक उच्च मूल्य प्राप्त करता हूं और इस प्रकार इनपुट सूची में के अधिकांश मूल्यों की तुलना केवल न्यूनतम से तुलना की जानी चाहिए (तुलना का परिणाम अधिकतर झूठा होगा)।

Answer 6

दर्शकों में एल्गोरिदम weenies लिए: यदि आप टोनी होरे एल्गोरिथ्म Find पर एक साधारण परिवर्तन के साथ ऐसा कर सकते हैं:

find(topn, a, i, j) 
    pick a random element x from a[i..j] 
    partition the subarray a[i..j] (just as in Quicksort) 
    into subarrays of elements <x, ==x, >x 
    let k be the position of element x 
    if k == 0 you're finished 
    if k > topn, call find(topn, a, i, k) 
    if k < topn, call find(topn-k, k, j) 

इस एल्गोरिथ्म सरणी a, के पहले topn तत्वों में सबसे बड़ा topn तत्वों डालता है बिना उन्हें छंटाई के बिना। बेशक, यदि आप उन्हें सॉर्ट करना चाहते हैं, या बेहद सादगी के लिए, एक ढेर बेहतर है, और लाइब्रेरी फ़ंक्शन को कॉल करना अभी भी बेहतर है। लेकिन यह एक अच्छा एल्गोरिदम है।