如何有效地从数十亿个数字中找到 10 个最大的数字

Question

>问题陈述：从包含数十亿个数字的文件中查找最多 10 个数字

输入： 97911 98855 12345 78982 ..... .....

我实际上想出了以下解决方案，它有

• 最佳情况复杂性 O(n) - 当文件具有按降序排列的数字时
• 最坏情况复杂性 O(n*10) ~ O(n) 当文件具有按升序排列的数字时
• 平均复杂性 ~ O(n)

在所有情况下，空间复杂性都O(1)

我正在使用文件阅读器和存储最多 10 个数字的排序数组读取文件。我将检查 currentLine 是否大于数组中的最小元素 - 如果是这样，将通过交换将其插入正确的位置。

Scanner sc = new Scanner(new FileReader(new File("demo.txt")));
int[] maxNum = new int[10];
    while(sc.hasNext()){
    int phoneNumber = Integer.parseInt(sc.nextLine());
    if(phoneNumber>maxNum[9]){
        maxNum[9] = phoneNumber;
        for(int i =9;i>0;i--){
            if(maxNum[i]>maxNum[i-1]){
                int temp = maxNum[i];
                maxNum[i] = maxNum[i-1];
                maxNum[i-1] = temp;
            }
        }
    }
    }

如果有更好的方法来实施此内容，我正在寻找反馈

Answer 1

如果文件未排序，则必须至少查看一次文件中的每个数字，因为它可能是 10 个最大的数字之一。因此，O（n） 是您可以达到的最佳效果。

通过用最小堆替换maxNum数组，可以进行一些优化（但是在不改变渐近复杂性的情况下）。如果要找到的数字计数足够大（假设您正在寻找 100 个最大的数字），这将运行得更快。它可能还没有在 10 点得到回报。

Answer 2

您可以通过多线程和并行化来改进算法。这意味着运行例如 20 个线程，并将文件分成 20 个文件，并在每个部分找到最大的 10 个数字。最后，找到您维护的 20 个数组（每个数组长度为 10）中最大的 10 个数字。

关键是操作正在从文件或数据库中读取而不是写入。因此，应该可以通过不同的线程并行访问文件的不同部分。即使您的输入在内存中，这也比天真的搜索更快。这仍然是 O（n），但根据它们并行运行的线程数量（例如 t），它使用大约 n/t 比较。这意味着它比朴素算法快大约 t 倍。

最后我应该说，对小数组的位优化作为主要时间是没有用的，重点是如何维护一个大文件而不是维护一个小数组。

Answer 3

通常，要从 N 个数字中找到 K 个最大数：

1. 以 O（N lg N） 时间对数字进行排序，然后取 K 最大。如果磁盘上有数十亿个数字，则必须执行外部（磁盘上）排序，例如外部 MergeSort。

2. 使用容量 K 的最小堆并扫描 N 个值。将 K 个最大值保留在堆中，其中最小的值位于顶部。运行时间： O（N lg K）.您可以在从磁盘扫描数字时将最小堆保留在内存中。

3. 使用选择算法查找预期时间 O（N） 中的第 （N-K） 个最大值。使用快速排序分区算法的快速选择算法还将对值进行分区，以便 K 最大值位于第 （N-K） 个最大值的一侧。预期运行时间：O（N）。但是，该选择算法位于内存中。