100万の数値を並べ替えるにはどうすればいいですか？

Question

私は100万の数字を持つファイルを持っています。私はこれが選択ソートであることを知って、私はそれがコンピュータをストールしないように、私は、効率的にそれを並べ替えることができます方法を知っておく必要があり、それが唯一のトップ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値だけが必要な場合は、1つの数値をソートするのに多くの時間を費やすことになります。

数字のリストを調べて、これまでに見た上位10個の最大値を把握するだけです。あなたがリストを通過するときにトップ10を更新し、最後に到達したときにそれらを印刷します。

これは、あなたが一般化として、あなたの問題を見ることができる単純な問題

あなただけのファイルを介して単一のパスを作成する必要があります意味（シータのすなわち、時間の複雑さ（N））

ます数字のリストの中で最大値を見つけること。 {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 

このように比較の並べ替えとは対照的に、リストの1つのトラバーサルでmaxを見つけることができます。リストにトップ10値を見つける

を一般

は非常に似ています。唯一の違いは、max（top 1）ではなくtop 10を追跡する必要があることです。

結論として、10個の値を保持するコンテナが必要です。巨大な数字のリストを繰り返しているので、サイズ10のコンテナで気になる唯一の価値は最小です。これは、トップ10に入るにふさわしい新しい番号を発見した場合にこれが置き換えられる番号なのでです。

とにかく、分をすばやく見つけるのに最適なデータ構造は最小ヒープです。しかし、ヒープについてまだ学習しているかどうかは分かりません.10個の要素にヒープを使用するオーバーヘッドが、その利点を上回る可能性があります。

10個の要素を保持し、妥当な時間内に分を得ることができる任意のコンテナが良いスタートになります。何をしたい

Answer 2

ベストソートは、部分ソートで、heapq.nlargestというPythonライブラリで利用できます。

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

は、次のPythonコードがpartition() パーティションを2つにリストを分割機能に基づいています良いselection algorithm

です。 "pivotValue"より小さい値はリストの先頭に移動されます。 pivotValueより大きい値はリストの最後に移動されます。 これは、開始点から終了点までのリストをたどることでO（N）操作で実行され、ピボット値よりも小さい場合にのみ、リストの開始付近で値を移動するたびに移動します。

（実際には、大きな値を最小にしないため、大きな値をリストの先頭に移動することに注意してください）。

O（N）時間にリストを分割すると、リストの先頭にm個の大きな数字が残されます。もしm = 10であれば、それはあなたの10の大きな数字です。 mが10より大きい場合は、最大のm個の数字から10個の最大の数字を得るためにm個の最大の数字を再び分割する必要があります。 mが10より小さい場合、10 m以上の数字が必要なので、10 mの数字を見つけてm個の数字に追加して、必要な10個の数字を取得します。

したがって、私たちは最大の数字が10になるまでパーティショニングを続けます。これはselect()メソッドによって行われます。全体の方法は通常非常に速いです。なぜなら、パーティションを作成するたびに、扱う数値の半分を残すからです。 （あなたが2で見なければならない数字の数を絶えず分けるなら、それは良いことです）。私たちが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]"