如何排序100万个数字,并且只打印Python中的前10个？

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个值,那么您将浪费大量时间对每个数字进行排序.

只需查看数字列表并跟踪到目前为止看到的前10大值.在浏览列表时更新前十名,并在结束时打印出来.

这意味着你只需要在文件中进行一次传递(即theta(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

所以你看,我们可以在列表的单个遍历中找到最大值,而不是任何类型的比较排序.

泛化

查找列表中的前10个值非常相似.唯一的区别是我们需要跟踪前10名而不是最大值(前1名).

底线是你需要一个容纳10个值的容器.当你迭代你庞大的数字列表时,你在10号容器中唯一关心的值就是最小值.那是因为如果你发现了一个值得进入前10名的新号码,这就是要替换的号码.

无论如何,事实证明,最适合快速查找分钟的数据结构是最小堆.但是我不确定你是否已经了解了堆,并且使用10个元素的堆的开销可能超过它的好处.

任何容纳10个元素并且可以在合理的时间内获得最小值的容器将是一个良好的开端.

Answer 2

最好的排序是部分排序,在Python库中可用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]
"""