乐趣区

关于java:海量数据处理-大量数据中找出最大的前10个数-Top-K-问题

jiezi

在工作中咱们常遇到此类问题，从一个大量甚至海量的数据中取出前几个大的数。必须在海量的文章中取出点击量最大的 10 篇文章。
此类问题其实就是 Top K 问题。
给定一个数据（数据量海量 N），想找到前 K 个最大的或最小的元素。

eg：有 10 亿个 Long 型整数，存储在文件中，如果找出其中最大的 10 个？
最容易想到的办法是将数据全副排序，而后在排序后的汇合中进行查找，最快的排序算法的工夫复杂度个别为 O（nlogn），如疾速排序。每个 Long 类型占 8 个字节，10 亿个数就要占用 7GB+ 的存储空间，对于一些可用内存小于 7GB 的计算机而言，很显然是不能一次将全副数据读入内存进行排序的。其实即便内存可能满足要求（我机器内存都是 8GB），该办法也并不高效，因为题目的目标是寻找出最大的 10 个数即可，而排序却是将所有的元素都排序了，做了很多的无用功。

第二种办法采纳最小堆。首先读入前 10 个数来创立大小为 10 的最小堆，而后遍历后续的数字，并于堆顶（最小）数字进行比拟。如果比最小的数小，则持续读取后续数字；如果比堆顶数字大，则替换堆顶元素并从新调整堆为最小堆。整个过程直至 10 亿个数全副遍历完为止。而后依照中序遍历的形式输入以后堆中的所有 10 个数字。这个办法应用的内存是可控的，只有 10 个数字所需的内存即可。
这种办法 Java 中有现成的数据结构优先级队列能够应用：java.util.PriorityQueue
代码如下：

import org.junit.Test;

import java.io.*;
import java.util.PriorityQueue;
import java.util.Random;

/**
 * @author liming
 * @date 2020/9/3
 * @description
 */
public class TopKDemo {

    // 模仿海量数据的文件
    private final File file = new File("file" + File.separator + "topkdata.txt");
    private final Random random = new Random();
    private final PriorityQueue<Long> priorityQueue = new PriorityQueue<>(10);

    @Test
    public void computeTopK() {
        FileReader fileReader = null;
        BufferedReader bufferedReader = null;
        try {fileReader = new FileReader(file);
            bufferedReader = new BufferedReader(fileReader);
            String line;
            while ((line = bufferedReader.readLine()) != null) {addToTopKQueue(Long.valueOf(line));
            }
        } catch (Exception e) {e.printStackTrace();
        } finally {if (bufferedReader != null) {
                try {bufferedReader.close();
                } catch (IOException e) {e.printStackTrace();
                }
            }
            if (fileReader != null) {
                try {fileReader.close();
                } catch (IOException e) {e.printStackTrace();
                }
            }
            System.out.println("Long.MAX_VALUE =" + Long.MAX_VALUE);
            Long target;
            while ((target = priorityQueue.poll()) != null) {System.out.println("target =" + target);
            }
        }
    }

    /**
     * init 办法仅运行一次即可，是为筹备模仿数据
     */
    @Test
    public void init() {long start = System.currentTimeMillis();
        System.out.println("init");
        FileWriter fileWriter = null;
        try {fileWriter = new FileWriter(file, true);
            // 先用 100 万数据，多了电脑可能受不了
            for (int i = 0; i < 1000000; i++) {fileWriter.write(String.valueOf(random.nextLong()) + System.lineSeparator());
            }
            // 写入 10 个靠近 long 的最大值的数，便于取出是验证正确后果
            for (int i = 0; i < 10; i++) {fileWriter.write(String.valueOf(Long.MAX_VALUE - i) + System.lineSeparator());
            }
            fileWriter.flush();} catch (IOException e) {e.printStackTrace();
        } finally {if (fileWriter != null) {
                try {fileWriter.close();
                } catch (IOException e) {e.printStackTrace();
                }
            }
            System.out.println("用时：" + (System.currentTimeMillis() - start));
        }
    }

    public void addToTopKQueue(Long target) {if (priorityQueue.size() < 10) {priorityQueue.add(target);
        } else {Long head = priorityQueue.peek();
            if (target > head) {priorityQueue.poll();
                priorityQueue.add(target);
            }
        }
    }

}

理论运行：实际上，最优的解决方案应该是最符合实际设计需要的计划，在理论利用中，可能有足够大的内存，那么间接将数据扔到内存中一次性解决即可。也可能机器有多个核，这样能够采纳多线程解决整个数据集。多线程解决时，上述办法须要做线程平安保障。

退出移动版