python - 我如何对 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 个元素并且可以在合理的时间内获得最小值的容器都是一个好的开始。