如何从 4，000，000，000 个号码中获取最常用的 100 个号码？

algorithm java

2022-08-31 12:37:31

昨天在一次编码面试中，我被问及如何从4，000，000，000个整数（可能包含重复项）中获取最常见的100个数字，例如：

我想到的第一种方法是使用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 个值？

答案 1

如果对数据进行排序，则可以收集数据大小的前 100 个。由于数据已排序，因此不同值是连续的。在遍历数据一次时对它们进行计数会为您提供全局频率，当数据未排序时，您将无法获得全局频率。O(n)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]
    }
}

答案 2

整数是有符号的32位，所以如果只发生正整数，我们看2 ^ 31 max不同的条目。2^31 字节的数组应保持在最大数组大小以下。

但是这不能保持高于255的频率，你会说吗？是的，你是对的。

因此，我们为数组中超过最大值的所有条目添加一个哈希映射（255 - 如果它是有符号的，则从 -128 开始计数）。此哈希图中最多有 1600 万个条目（40 亿除以 255），这应该是可能的。

我们有两种数据结构：

一个大数组，由读取的字节数（0..2^31）索引。
的哈希图（数字读取，频率）

算法：

 while reading next number 'x'
 {
   if (hashmap.contains(x))
   {
     hashmap[x]++;
   }
   else
   {
     bigarray[x]++;
     if (bigarray[x] > 250)
     {
       hashmap[x] = bigarray[x];
     }
   }
 }

 // when done:
 // Look up top-100 in hashmap
 // if not 100 yet, add more from bigarray, skipping those already taken from the hashmap

我不精通Java，所以不能给出更好的代码示例。

请注意，此算法是单通道的，适用于未排序的输入，并且不使用外部预处理步骤。

它所做的只是假设读取数的最大值。如果输入是非负整数，则它应该有效，其最大值为2 ^ 31。示例输入满足该约束。

上面的算法应该满足大多数提出这个问题的面试官。你是否可以用Java编写代码应该由一个不同的问题来决定。这个问题是关于设计数据结构和有效的算法。