我怎样才能从4,000,000,000个号码中得到最频繁的100个号码？

昨天，在一次编程访谈中，我被问到如何从400万个整数(可能包含重复)中找出最常用的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个值？

5677 次浏览
小开

我注意到这条线上有一个错误。

unsorted.put(number, unsorted.getOrDefault(number, 1) + 1);

您应该将默认值设置为0，然后向其中添加1。如果不是，当您只有一个出现的值，它被记录为2的频率。

unsorted.put(number, unsorted.getOrDefault(number, 0) + 1);

我看到的一个缺点是，在分类时没有必要保留所有40亿个频率。

可以使用 PriorityQueue仅保存100个值。

    Map<String, Integer> unsorted = new HashMap<>();


PriorityQueue<Map.Entry<String, Integer>> highestFrequentValues = new PriorityQueue<>(100,
(o1, o2) -> o2.getValue().compareTo(o1.getValue()));


// O(n)
try (Scanner scanner = new Scanner(new File("numbers.txt"))) {
while (scanner.hasNextLine()) {
String number = scanner.nextLine();
unsorted.put(number, unsorted.getOrDefault(number, 0) + 1);
}
}


// O(n)
for (Map.Entry<String, Integer> stringIntegerEntry : unsorted.entrySet()) {
if (highestFrequentValues.size() < 100) {
highestFrequentValues.add(stringIntegerEntry);
} else {
Map.Entry<String, Integer> minFrequencyWithinHundredEntries = highestFrequentValues.poll();
if (minFrequencyWithinHundredEntries.getValue() < stringIntegerEntry.getValue()) {
highestFrequentValues.add(stringIntegerEntry);
}
}
}


// O(n)
for (Map.Entry<String, Integer> frequentValue : highestFrequentValues) {
System.out.println(frequentValue.getKey());
}
小开

但是它可能会对4000000000个数字的数据集抛出 OutOfMemory 异常。而且，由于4000000000超过了 Java 数组的最大长度，我们假设数字在一个文本文件中，并且它们没有排序。

这取决于价值分布。如果您有4E9数字，但是这些数字是整数1-1000，那么您将得到一个包含1000个条目的映射。如果数字是双精度的，或者值空间不受限制，那么您可能会遇到问题。

前一个答案里面有个窃听器

unsorted.put(number, unsorted.getOrDefault(number, 0) + 1);

我个人会使用“ AtomicLong”作为值，它允许在不更新 HashMap 条目的情况下增加值。

我认为多线程或者 Map Reduce 更适合大数据集？ 解决这个问题最有效的方法是什么？

这是一个典型的 map-reduce 练习示例，因此理论上可以使用多线程或 M-R 方法。也许这就是你练习的目标，你应该实现多线程 map-reduce 任务，不管它是否是最有效的方法。

在现实中，您应该计算它是否值得付出努力。如果您是按顺序读取输入(因为它在使用 Scanner的代码中) ，那么肯定不是。如果考虑到 I/O 吞吐量，可以分割输入文件并并行读取多个部分，那么情况可能就是这样。

或者，如果值空间太大，无法放入内存，需要缩小数据集的大小，则可以考虑采用不同的方法。

小开
最佳答案

如果数据是 解决了，您可以收集 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]
}
}
小开

由于数据集对于内存来说可能太大了，我将使用十六进制的 基数排序基数排序。因此，数据集将在每次传递中被分割为16个文件，并按需要传递多少个文件来获得最大的整数。

第二部分是将这些文件组合成一个大型数据集。

第三部分是按数字读取文件编号，并计算每个编号的出现次数。将出现的次数和次数保存到按大小排序的二维数组(列表)中。如果文件中的下一个数字比列表中出现次数最少的数字出现次数更多，则替换该数字。

小开

一种选择是二进制搜索类型。考虑一个二叉树，其中每个分割对应于32位整数中的一个位。所以概念上我们有一个深度为32的二叉树。在每个节点上，我们可以计算集合中以该节点的位序列开始的数字的计数。这个计数是一个 O (n)操作，因此查找最常见序列的总成本将是 O (n * f (n)) ，其中函数取决于我们需要枚举多少个节点。

我们先从深度优先搜索开始。这为枚举期间的堆栈大小提供了一个合理的上限。对所有节点进行蛮力搜索显然是很糟糕的(在这种情况下，你可以完全忽略树的概念，只是枚举所有的整数) ，但是我们有两件事情可以防止我们需要搜索所有节点:

  1. 如果我们曾经到达一个分支，其中有0个数字在集合中从该位序列开始，我们可以删除该分支并停止枚举。

  2. 一旦我们到达一个终端节点，我们就知道这个特定数字出现了多少次。我们将其添加到我们的“前100名”列表中，如果有必要，删除最低的。一旦这个列表填满，我们就可以开始删除总计数低于“ top 100”计数中最低的分支。

我不确定这种情况下的平均和最坏的表现是什么。对于数目较少的集合，它的性能往往更好，对于接近均匀分布的集合，它的性能可能最差，因为这意味着需要搜索更多的节点。

以下是一些观察结果:

  1. 最多有 N 个具有非零计数的终端节点，但是由于在这个特定的情况下 N > 2 ^ 32，所以这并不重要。

  2. M 个叶节点(M = 2 ^ 32)的总节点数为2M-1。这在 M 中仍然是线性的，所以最坏的情况下运行时间在 O (N * M)上限。

  3. 这比仅仅搜索某些情况下的所有整数要糟糕，但是仅仅是通过线性标量因子。平均而言，这是否执行得更好取决于预期的数据。对于统一的随机数据集，我的直观猜测是，一旦前100名列表填满，您可以修剪足够多的分支，这样您需要的数量往往少于 M，但这需要经验评估或证明。

  4. 实际上，这个算法只需要对数据集进行只读访问(它只执行从某个位模式开始的数字计数) ，这意味着它可以通过跨多个数组存储数据，并行计数子集，然后将计数相加来实现并行化。对于实际的实现来说，这可能是一个相当大的加速，而对于需要排序的方法来说，这是很难做到的。

一个具体的例子说明如何执行这个操作，对于一个更简单的3位数集合，只找到最常见的一个。假设场景是’000,001,100,001,100,010’。

  1. 数数所有以’0’开头的数字，这个数字是4。

  2. 再深入一点，数数所有以“00”开头的数字，这个数字是3。

  3. 统计所有“000”的数字。这个数字是1。这是我们新的最频繁的数字。

  4. 统计所有“001”的数字。这个数字是2。这是我们新的最频繁的数字。

  5. 采取下一个深分行，并计算所有数字以’01’开始。这个计数是1，比我们最常见的计数少，所以我们可以停止枚举这个分支。

  6. 数数所有以“1”开头的数字。这个计数是1，比我们最常见的计数少，所以我们可以停止枚举这个分支。

  7. 我们没有分行了，所以我们完成了，“001”是最频繁的。

小开

我认为选择4万亿是为了确保这个问题太大，以至于当前的桌面计算机无法容纳内存。那么从亚马逊或微软租用一个大的虚拟机就是为了这个目的？这是一个大多数人还没有想到的答案，但对于现实世界的解决方案是有效的。

我的方法是从 垃圾箱开始。数字的范围大概是所有32位无符号整数(或者不管他们说什么)。内存中的数组有多大？将范围划分为这么多相等的容器，然后将数据传递一次。看一下分布: 它是相当均匀的，还是尖锐的，或者是某种曲线？如果第一个/最后一个垃圾桶的范围是零，那么它会给你输入值的真实范围，你可以调整程序只是在这个范围内的垃圾桶和重复，以获得更好的准确性。

然后根据分布情况，决定如何进行。一般来说，只有前100个容器可能包含前100个值，因此可以重新配置这些范围以及在该摘录范围内可以处理的最大容器。如果分布过于均匀，你可能会得到许多同样数量的垃圾桶，所以即使你还有许多超过100个垃圾桶，也要扔掉较小的垃圾桶——你仍然要减少 一些。

最糟糕的情况是，所有的垃圾桶出来都是一样的，你不能这样切下来！有人用这种方法准备了一些病理数据。所以，重新安排你的方式，做装箱。而不是简单地切割成相同大小的连续范围，我们1:1映射洗牌他们。但是，对于大容器，这可能会保留相当统一的属性，因此您不需要传统的“良好”散列函数。

另一种方法

如果分类工作，并迅速减少问题，这是很容易的。但是这些数据可能非常困难。那么，什么是不管数据如何都能正常工作的方法呢？我可以假设结果是存在的: 大约100个值会有更多的出现。

不要选择容器，而是选择 n 个特定的值(不管内存中能容纳多少个)。要么选择随机数，要么使用输入中的前 N 个不同值。数一数，然后把其他的复制到另一个文件中。也就是说，没有空间可以计数的值将被复制到一个(较小的原始)文件中。

现在您至少有了一个有用的轴心值: 您确实精确计算过的100个不同顶部值的精确基数。好吧，你选的那些可能最后还是一样的！所以最坏的情况只有一个不同的基数。你知道这不是一个“顶”值，因为它们远不止100个。

再次运行新的(较小的)文件，丢弃小于已知的前100个的计数。重复。

这让我想起了我可能在 Knuth 的 TAOCP中读到过的一些东西，但是为了适应现代机器的尺寸而进行了扩展。

小开

在伪代码中:

  1. 执行 外部排序
  2. 做一个传递来收集前100个频率(不是哪个值有它们)
  3. 再次传递以收集具有这些频率的值

假设: 有明确的赢家——没有平局(在前100名之外)。

时间复杂度: 由于排序，O (n logn)(大约)。 空间复杂性: 可用内存，同样由于排序。

步骤2和步骤3都是 O (n)时间和 O (1)空间。

如果没有关联(在前100之外) ，步骤2和步骤3可以合并为一个步骤，这不会改善时间复杂性，但会略微改善运行时间。

如果有一些平局会使得胜利者的数量很大，你不可能发现并采取特殊的行动(例如，抛出错误或丢弃所有的平局)没有两个通行证。但是，您可以通过一次传递就可以从平局中找到最小的100个值。

小开

整数是有符号的32位，所以如果只有正整数出现，我们查看2 ^ 31个最大不同的条目。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 编写代码应该由另一个问题来确定。这个问题是关于设计数据结构和高效算法的。

小开

好的，我知道这个问题是关于 Java 和算法的，解决这个问题并不是重点，但是我仍然认为这个解决方案必须公布以保证完整性。

sh中的解决方案:

 sort FILE | uniq -c | sort -nr | head -n 100

说明: sort | uniq -c只列出唯一的条目，并计算它们在输入中出现的次数; sort -nr按相反的顺序对输出进行数字排序(顶部出现更多的行) ; head -n 100只保留100个顶部行。一个400,000,000,000个数字直到9999999的文件(根据 OP)大约需要40GB，因此可以很好地放在一台机器的磁盘上，所以从技术上来说可以使用这种解决方案。

优点: 简单，有恒定和有限的内存使用。缺点: 次优(因为 sort) ，为操作消耗了大量的临时磁盘空间，总的来说，毫无疑问，专门为这个问题设计的解决方案将具有更好的性能。问题仍然存在(非常严肃地) : 在一般情况下，编写(然后调试和执行)一个优化的解决方案是否会比使用次优解决方案(如上所述)花费更多或更少的时间，但可以立即使用？我在一个有400,000,000行(小10倍)的示例文件上运行了这个解决方案，在我的计算机上花了大约7分钟。

另外，OP 提到这个问题是在一次编程面试中提出的。这很有趣，因为我认为在开始从头编写另一个程序之前，这是一种值得在本文中提及的解决方案。当人们说“经验丰富的工程师比其他人快10倍... ...”，我个人并不认为这是因为经验丰富的工程师编码更快，或者是因为他们不假思索地产生了优化的算法，而是因为他们探索了可以节省时间的替代方案。在面试的情况下，这是一个重要的技能之一，以证明其他。

小开
  1. 把你的号码分成两份
  2. 在每个桶里找出前100名
  3. 合并那些排名前100的名单。

要除法，执行 中位数中位数(也可以修改为顶部/底部的中位数)。

每个桶里都有不同范围的数字。最初的中间分割使得2个桶，每个桶中的元素数量大约是整个列表的一半。

要找到前100名，首先要知道桶是狭窄的(类似的最小值和最大值) O (1)还是很小的(里面只有很少的数字)(O (n)次 O (n * 桶计数)内存)。如果其中一个为真，那么一个简单的计数传递(可能同时执行多于1个桶)就可以解决这个问题(由于内存限制，您可能不得不执行多次计数)。

如果两者都不是真的，递归并将桶分成两部分。

如何在不浪费太多时间的情况下递归，将会有一些棘手的问题。

但是这个想法是，每个桶都会以指数方式变得越来越窄或越来越小。狭窄的桶有一个最小值和最大值，它们很接近，而小桶只有很少的元素。

您合并存储桶，以便拥有足够的存储空间来计算存储桶中的元素(基于宽度或基于卷)。然后你传球，数那个桶，找到前100名，然后重复。每次你合并前100名从扫描到前100名。

在适当的位置，不需要对整个列表进行排序，当初始“桶”很窄或很小时，就会转变为更简单和更优化的策略。

小开

我只需删除数据库中的所有数字(SQLite将是我的第一选择)

CREATE TABLE tbl (
number INTEGER PRIMARY KEY,
counter INTEGER
)

然后对每个接收到的数字执行

INSERT INTO tbl (number,counter) VALUES (:number,1) ON DUPLICATE KEY UPDATE counter=counter+1;

或使用 SQLite 语法

INSERT INTO tbl (number,counter) VALUES (:number,1) ON CONFLICT(number) DO UPDATE SET counter=counter+1;

当所有的数字都被计算在内时,

SELECT number, counter FROM tbl ORDER BY counter DESC LIMIT 100

然后我会得到100个最常见的数字，以及它们出现的频率。只有当磁盘空间用完时(或者当磁盘空间达到 ~ 20000000000000(20万亿)个唯一数字大约281TB 时...) ，该方案才会中断

小开

Linux 工具

这只是在 Linux/Mac 上的一个 shell 脚本中完成的:

sort inputfile | uniq -c | sort -nr | head -n 100

如果数据已经排序，只需使用

uniq -c inputfile | sort -nr | head -n 100

文件系统

另一个想法是使用数字作为文件名，并增加每次命中的文件大小

while read number;
do
echo -n "." >> number
done <<< inputfile

文件系统约束可能会给这么多文件带来麻烦，因此您可以创建一个包含第一个数字的目录树并将文件存储在那里。

完成后，遍历树并记住文件大小的100个最高可见值。

数据库

可以对数据库使用相同的方法，因此不需要实际存储 GB 数据(也可以) ，只需要计数器(需要更少的空间)。

采访

一个有趣的问题是你如何处理边缘情况，所以应该发生什么，如果100,101，... 数字有相同的频率。整数只是正数吗？

他们需要什么样的输出，是数字还是频率？把它当作一项真正的工作任务来思考，然后问问你需要知道的一切来解决它。更多的是你如何思考和分析一个问题。

小开

我假设挑战的关键是在不消耗太多内存的情况下处理这么大量的数据，并避免过多地解析输入。

这个算法需要两个不太大的数组。我不了解 java，但是我相信它可以在 C 语言中快速运行 非常:

创建一个大小为2 ^ n 的 数数数组，以便根据输入数字的 n 个最高有效位计数。这将需要对输入数据进行首次扫描，但这真的很容易做到。我首先尝试使用 n = 20(大约100万个桶)。

显然，我们不会一次处理一个桶的数据，因为这需要读取输入100万次，相反，我们选择我们的最佳批量大小 B，并分配一个大小 B 的 批次数组 B 可能是40M，所以我们的目标是读取输入大约100次。(这完全取决于可用内存)。

然后，我们在 count 数组上迭代，对桶的第一个范围进行分组，以便总和接近，但不超过 B。

对于每个这样的范围，我们解析输入数据，查找范围内的数字并将这些数字复制到批处理数组。因为我们已经知道每个 bucket 的大小，所以我们可以立即将它们分组复制到每个 bucket 中，这样我们就只需要逐个 bucket 对它们进行排序(您可以重新使用 count 数组来存储索引，以便在哪里写入下一个条目)。接下来，我们计算已排序的批处理数组中的相同项目，并跟踪到目前为止排名前100位的项目。

继续下一个桶的范围，其计数总数小于 B，等等。

优化措施:

  • 一旦我们开始有一个体面的前100名，你可以跳过整个桶的大小低于我们的第100项。为此，我们可以在 count 数组中使用一个特殊的值(比如 -1)来表示没有索引。根据数据的不同，这可以大大减少所需的传递次数。
  • 当在已排序的批处理中计算相同项时，我们可以跳过第100个条目的大小(然后向后退几步)。如果需要，我可以共享伪代码)

这种方法可能存在的问题: 输入数字可以集中在一个很小的范围内，然后你可能会得到一个或多个比 B 大的单个桶。可能的解决方案:

  1. 您可以尝试另外选择 n 个位(例如 n 个最低有效位)。请注意，如果同样的数字出现10亿次，这仍然没有帮助。
  2. 如果输入是32位整数，那么可能值的范围是有限的，每个桶中只能有几千个不同的数字。因此，如果一个 bucket 非常大，那么我们可以以不同的方式处理它: 只需为该范围内的每个唯一值保留一个计数器。我们可以为此重定义 Batch 数组。

提交答案