java - 如何从 4,000,000,000 个号码中获取最频繁的 100 个号码？

Question

昨天在一次编码面试中，我被问到如何从 4,000,000,000 个整数(可能包含重复项)中获取最频繁的 100 个数字，例如:

813972066
908187460
365175040
120428932
908187460
504108776

我想到的第一种方法是使用 HashMap:

static void printMostFrequent100Numbers() throws FileNotFoundException {
    
    // Group unique numbers, key=number, value=frequency
    Map<String, Integer> unsorted = new HashMap<>();
    try (Scanner scanner = new Scanner(new File("numbers.txt"))) {
        while (scanner.hasNextLine()) {
            String number = scanner.nextLine();
            unsorted.put(number, unsorted.getOrDefault(number, 0) + 1);
        }
    }

    // Sort by frequency in descending order
    List<Map.Entry<String, Integer>> sorted = new LinkedList<>(unsorted.entrySet());
    sorted.sort((o1, o2) -> o2.getValue().compareTo(o1.getValue()));

    // Print first 100 numbers
    int count = 0;
    for (Map.Entry<String, Integer> entry : sorted) {
        System.out.println(entry.getKey());
        if (++count == 100) {
            return;
        }
    }
}

但它可能会为 4,000,000,000 个数字的数据集抛出 OutOfMemory 异常。此外，由于 4,000,000,000 超过了 Java 数组的最大长度，假设数字在文本文件中并且没有排序。我认为多线程或 Map Reduce 更适合大数据集？
当数据不适合可用内存时，如何计算前 100 个值？

Answer 1

如果数据是已排序 ，您可以在O(n)中收集前100名哪里n是数据的大小。由于数据已排序，不同的值是连续的。在遍历数据时计算它们一次为您提供 全局频率，当数据未排序时，您无法使用该频率。
请参阅下面的示例代码，了解如何做到这一点。在 GitHub 上还有整个方法的实现(在 Kotlin 中)
注:不需要排序。什么 是 需要的是不同的值是连续的，所以不需要定义排序——我们从排序中得到这个，但也许有一种更有效的方法。
您可以在大约 O(n log n) 中使用(外部)合并排序对数据文件进行排序。通过将输入数据文件拆分为适合您内存的较小文件，将它们排序并写入已排序的文件中，然后合并它们。

关于此代码示例:

排序后的数据由 long[] 表示.因为逻辑一个一个地读取值，所以它是从排序文件中读取数据的近似值。

OP 没有指定如何处理具有相同频率的多个值；因此，除了确保结果是没有特定顺序的前 N ​​个值并且不暗示没有其他值具有相同的频率之外，代码不会做任何事情。

import java.util.*;
import java.util.Map.Entry;

class TopN {
    private final int maxSize;
    private Map<Long, Long> countMap;

    public TopN(int maxSize) {
        this.maxSize = maxSize;
        this.countMap = new HashMap(maxSize);
    }

    private void addOrReplace(long value, long count) {
        if (countMap.size() < maxSize) {
            countMap.put(value, count);
        } else {
            Optional<Entry<Long, Long>> opt = countMap.entrySet().stream().min(Entry.comparingByValue());
            Entry<Long, Long> minEntry = opt.get();
            if (minEntry.getValue() < count) {
                countMap.remove(minEntry.getKey());
                countMap.put(value, count);
            }
        }
    }

    public Set<Long> get() {
        return countMap.keySet();
    }

    public void process(long[] data) {
        long value = data[0];
        long count = 0;

        for (long current : data) {
            if (current == value) {
                ++count;
            } else {
                addOrReplace(value, count);
                value = current;
                count = 1;
            }
        }
        addOrReplace(value, count);
    }

    public static void main(String[] args) {
        long[] data = {0, 2, 3, 3, 4, 5, 5, 5, 5, 6, 6, 6, 7};
        TopN topMap = new TopN(2);

        topMap.process(data);
        System.out.println(topMap.get()); // [5, 6]
    }
}