如何在Python中排序100万个数字并仅打印前10个？

Question

我有一个文件，里面有一百万个数字。我想知道怎么高效地对这些数字进行排序，这样就不会让电脑卡住，而且只打印出前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

在编程中，有时候我们会遇到一些问题，特别是在使用某些工具或库的时候。这些问题可能会让我们感到困惑，不知道该怎么解决。比如，有人可能在使用某个特定的功能时，发现它的表现和预期不一样。这种情况很常见，尤其是当我们刚开始学习编程的时候。

解决这些问题的第一步是要仔细阅读错误信息。错误信息通常会告诉我们出错的地方，虽然有时候它们可能看起来很复杂，但其实它们是有用的线索。

另外，查阅相关的文档也是一个好主意。文档里通常会有详细的说明和示例，帮助我们更好地理解如何使用某个功能。

如果自己解决不了，可以去一些编程社区，比如StackOverflow，看看别人是怎么解决类似问题的。很多时候，别人遇到过的问题和我们是一样的，找到答案的几率就会大大增加。

总之，遇到问题时不要慌张，慢慢分析，查找资料，通常都能找到解决办法。

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 2

最好的排序方式是部分排序，这个功能在Python的库里叫做 heapq.nlargest。

Answer 3

如果你只需要找出前10个最大的值，那就没必要把所有的数字都排序，这样会浪费很多时间。

你可以直接浏览这个数字列表，记录下目前为止看到的前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

所以你看，我们可以在一次遍历中找到最大值，而不是进行任何排序比较。

扩展一下

在一个列表中找出前10个值其实很相似。唯一的区别是我们需要记录前10个，而不仅仅是最大的一个（前1）。

总的来说，你需要一个容器来存放这10个值。当你在浏览这个庞大的数字列表时，容器中最小的值是你最关心的。因为如果你发现了一个新的数字，它应该替换掉这个最小值，成为前10名之一。

其实，最适合快速找到最小值的数据结构是最小堆。但我不确定你是否已经学习过堆，而且对于10个元素来说，使用堆的开销可能会超过它的好处。

任何能够存放10个元素并且能在合理时间内找到最小值的容器都是一个不错的开始。