मैं 1 मिलियन नंबर कैसे क्रमबद्ध कर सकता हूं, और केवल पायथन में शीर्ष 10 प्रिंट कर सकता हूं?

Question

मेरे पास एक फ़ाइल है जिसमें 1 मिलियन नंबर हैं। मुझे पता है कि मैं इसे कैसे कुशलतापूर्वक सॉर्ट कर सकते हैं, इतना है कि यह कंप्यूटर रोकने नहीं करता है की जरूरत है, और यह केवल शीर्ष 10.

#!/usr/bin/python3 

#Find the 10 largest integers 
#Don't store the whole list 

import sys 

def fOpen(fname): 
     try: 
       fd = open(fname,"r") 
     except: 
       print("Couldn't open file.") 
       sys.exit(0) 
     all = fd.read().splitlines() 
     fd.close() 
     return all 

words = fOpen(sys.argv[1]) 

big = 0 
g = len(words) 
count = 10 

for i in range(0,g-1): 
     pos = i 
     for j in range(i+1,g): 
       if words[j] > words[pos]: 
         pos = j 
       if pos != i: 
         words[i],words[pos] = words[pos],words[i] 
       count -= 1 
       if count == 0: 
         print(words[0:10]) 

मुझे पता है कि इस चयन तरह है, मुझे यकीन है कि नहीं कर रहा हूँ प्रिंट क्या करने के लिए सबसे अच्छा तरीका होगा।

Answer 1

यदि आपको केवल शीर्ष 10 मानों की आवश्यकता है, तो आप प्रत्येक नंबर को सॉर्ट करने में बहुत समय बर्बाद कर देंगे।

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

इसका मतलब यह होगा कि आप केवल एक सरल समस्या (थीटा की यानी समय जटिलता (एन))

फ़ाइल के माध्यम से एक भी पास बनाने की जरूरत है

आप एक सामान्यीकरण के रूप में आपकी समस्या को देख सकते हैं संख्याओं की सूची में अधिकतम मूल्य खोजने के लिए। अगर आपको {2,32,33,55,13, ...} दिया गया है और सबसे बड़ा मूल्य खोजने के लिए कहा जाता है, तो आप क्या करेंगे? ठेठ समाधान सूची के माध्यम से जाना है, जबकि अब तक की सबसे बड़ी संख्या याद है और इसे अगले नंबर से तुलना करना है।

सादगी के लिए, मान लीजिए कि हम सकारात्मक संख्याओं से निपट रहे हैं।

Initialize max to 0 
0 < 2, so max = 2 
2 < 32, so max = 32 
32 < 33, so max = 33 
33 < 55, so max = 55 
55 > 13, so max = 55 
... 
return max 

तो आप देखते हैं, हम के रूप में तुलना तरह के किसी भी प्रकार का विरोध करने, सूची की एक एकल ट्रेवर्सल में अधिकतम पा सकते हैं।

सामान्यीकरण एक सूची में शीर्ष 10 मान ढूँढना बहुत समान है। केवल अंतर यह है कि हमें केवल अधिकतम (शीर्ष 1) के बजाय शीर्ष 10 का ट्रैक रखने की आवश्यकता है।

नीचे की रेखा यह है कि आपको कुछ कंटेनर की आवश्यकता है जिसमें 10 मान हैं। चूंकि आप संख्याओं की अपनी विशाल सूची के माध्यम से पुनरावृत्ति कर रहे हैं, आपके आकार -10-कंटेनर में केवल एक ही मूल्य की देखभाल न्यूनतम है। ऐसा इसलिए है क्योंकि यह वह नंबर है जिसे प्रतिस्थापित किया जाएगा यदि आपने एक नया नंबर खोज लिया है जो शीर्ष 10-दूर तक होने का हकदार है।

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

कोई भी कंटेनर जिसमें 10 तत्व होते हैं और उचित मात्रा में मिनट प्राप्त कर सकते हैं, एक अच्छी शुरुआत होगी।

Answer 2

सर्वोत्तम प्रकार एक आंशिक प्रकार है, जो पाइथन लाइब्रेरी में heapq.nlargest के रूप में उपलब्ध है।

Answer 3

import heapq 

with open('nums.txt') as f: 
    numbers=map(int,f.readlines()) 
    print heapq.nlargest(10,numbers) 
    print heapq.nsmallest(10,numbers) 
""" 
[1132513251, 13252365, 23512, 2000, 1251, 1235, 324, 100, 82, 82] 
[1, 1, 7, 13, 15, 21, 22, 22, 33, 82] 
""" 

Answer 4

क्या आप चाहते हैं एक अच्छा selection algorithm

निम्नलिखित अजगर कोड समारोह partition() विभाजन के आसपास आधारित है है दो भागों में सूची बांट देता है। "पिवोटवेल्यू" से कम मान सूची की शुरुआत में स्थानांतरित हो जाते हैं। PivotValue से अधिक मान सूची के अंत में ले जाया जाता है। यह ओ (एन) संचालन में प्रारंभ से अंत तक सूची के माध्यम से किया जाता है, प्रत्येक बार जब यह एक मूल्य को देखता है तो यह सूची की शुरुआत के करीब ले जाता है, केवल तभी जब यह पिवट मूल्य से छोटा होता है।

(अपने मामले में नोट करें कि हम वास्तव में बड़े मूल्यों को सूची की शुरुआत में ले जाते हैं क्योंकि आप सबसे छोटे मूल्यों को सबसे छोटे नहीं चाहते हैं)।

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

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

def partition(_list,left,right,pivotIndex): 
    pivotValue=_list[pivotIndex] 
    _list[right],_list[pivotIndex]=pivotValue,_list[right] 
    storeIndex=left 
    for i in range(left,right): 
     if _list[i] > pivotValue: 
      _list[storeIndex],_list[i]=_list[i],_list[storeIndex] 
      storeIndex+=1 
    _list[right],_list[storeIndex]=_list[storeIndex],_list[right] 
    return storeIndex 

from random import randint 
def select(_list,left,right,k): 
    if left==right: 
     return _list[:left+1] 
    pivotIndex=randint(left,right) 
    pivotNewIndex=partition(_list,left,right,pivotIndex) 
    pivotDist=pivotNewIndex-left+1 
    if pivotDist==k: 
     return _list[:pivotNewIndex+1] 
    elif k<pivotDist: 
     return select(_list,left,pivotNewIndex-1,k) 
    else: 
     return select(_list,pivotNewIndex+1,right,k-pivotDist) 

_list=[1,2,109,2234,23,6,1,234,11,4,12451,1] 

left=0 
right=len(_list)-1 
pivotIndex=4 

print _list 
"[1, 2, 109, 2234, 23, 6, 1, 234, 11, 4, 12451, 1]" 
print partition(_list,left,right,pivotIndex) #partition is order(N). 
"7" #index 7, so the lowest number are in the first 7 numbers of the list [1, 2, 1, 6, 1, 11, 4, 23] 
print _list 
"[1, 2, 1, 6, 1, 11, 4, 23, 2234, 109, 12451, 234]" 
print select(_list,left,right,10) 
"[1, 2, 1, 1, 4, 11, 6, 23, 109, 234]" 

with open('nums.txt') as f: 
    numbers=map(int,f.readlines()) 
    print select(numbers,0,len(numbers)-1,10) 
    "[1132513251, 2000, 23512, 13252365, 1235, 1251, 324, 100, 82, 82]"