昨天在一次编码面试中，我被问到如何从 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 个值？
Dav*_*oko 40
如果数据进行排序，你可以收集进入前100 O(n)，其中n是数据的大小。由于数据已排序，不同的值是连续的。在遍历数据一次时对它们进行计数为您提供全局频率，当数据未排序时，您无法使用该频率。
请参阅下面的示例代码，了解如何做到这一点。在GitHub 上也有整个方法的实现（在 Kotlin 中）
注意：排序不是必需的。什么是需要的是不同的值是连续的，所以没有必要顺序进行定义-我们得到这个从分拣但也许还有更有效地这样做的方式。
您可以粗略地使用（外部）合并排序对数据文件进行排序，方法O(n log n)是将输入数据文件拆分为适合您内存的较小文件，将它们排序并写入已排序的文件中，然后合并它们。
关于此代码示例：
排序后的数据由 a 表示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]
}
}
Sjo*_*erd 24
整数是有符号的 32 位，所以如果只出现正整数，我们会查看最多 2^31 个不同的条目。2^31 字节的数组应保持在最大数组大小以下。
但这不能保持高于 255 的频率，你会说？你是对的。
因此，我们为超出数组中可能的最大值的所有条目添加一个哈希映射（255 - 如果它已签名，则从 -128 开始计数）。这个哈希图中最多有 1600 万个条目（40 亿除以 255），这应该是可能的。
我们有两种数据结构：
算法：
在阅读下一个数字“x”时
{
如果 (hashmap.contains(x))
{
哈希图[x]++；
}
别的
{
bigarray[x]++;
如果（大数组 [x] > 250）
{
hashmap[x] = bigarray[x];
}
}
}
// 完成后：
// 在 hashmap 中查找前 100 个
// 如果还不是 100，从 bigarray 添加更多，跳过那些已经从 hashmap 中取出的
我对 Java 不流利，所以无法给出更好的代码示例。
请注意，此算法是单次通过的，适用于未排序的输入，并且不使用外部预处理步骤。
它所做的只是假设读取的数字有最大值。如果输入是最大为 2^31 的非负整数，它应该可以工作。样本输入满足该约束。
上面的算法应该可以满足大多数问这个问题的面试官。你是否可以用 Java 编码应该由一个不同的问题来确定。这个问题是关于设计数据结构和高效算法的。
Boh*_*ian 18
在伪代码中：
假设：有明显的赢家 - 没有平局（前 100 名之外）。
时间复杂度：O(n log n)（大约）由于排序。空间复杂度：可用内存，同样是由于排序。
第 2 步和第 3 步都是 O(n) 时间和 O(1) 空间。
如果没有平局（在前 100 名之外），可以将步骤 2 和步骤 3 合并为一个 pass，这不会提高时间复杂度，但会稍微提高运行时间。
如果有平局会使获胜者的数量很大，则您无法发现并采取特殊行动（例如，抛出错误或放弃所有平局）而无需两次通过。但是，您可以通过一次从关系中找到最小的 100 个值。
gus*_*to2 10
但它可能会为 4000000000 个数字的数据集抛出 OutOfMemory 异常。此外，由于 4000000000 超过了 Java 数组的最大长度，假设数字在文本文件中并且没有排序。
这取决于价值分布。如果您有 4E9 数字，但数字是 1-1000 的整数，那么您最终将得到一个包含 1000 个条目的映射。如果数字是双精度数或值空间不受限制，那么您可能会遇到问题。
正如在以前的答案-有一个bug
unsorted.put(number, unsorted.getOrDefault(number, 0) + 1);
我个人会使用“AtomicLong”作为值，它允许在不更新 HashMap 条目的情况下增加值。
我认为多线程或 Map Reduce 更适合大数据集？这个问题最有效的解决方案是什么？
这是一个典型的 map-reduce 练习示例，因此理论上您可以使用多线程或 MR 方法。也许这是你练习的目标，你想实现多线程的 map-reduce 任务，不管它是否是最有效的方法。
实际上，您应该计算一下是否值得付出努力。如果您正在连续读取输入（因为它在您的代码中使用Scanner），那么绝对不是。如果可以拆分输入文件并并行读取多个部分，考虑到 I/O 吞吐量，则可能是这种情况。
或者，如果值空间太大而无法放入内存并且您需要缩小数据集的规模，您可以考虑不同的方法。
一种选择是一种二分搜索。考虑一棵二叉树，其中每个分裂对应于 32 位整数中的一个位。所以从概念上讲，我们有一个深度为 32 的二叉树。在每个节点，我们可以计算集合中以该节点的位序列开头的数字的计数。这个计数是一个 O(n) 操作，所以找到我们最常见的序列的总成本将是 O(n * f(n))，其中函数取决于我们需要枚举的节点数量。
让我们从考虑深度优先搜索开始。这为枚举期间的堆栈大小提供了合理的上限。对所有节点进行蛮力搜索显然很糟糕（在这种情况下，您可以完全忽略树的概念而仅枚举所有整数），但是我们有两件事可以阻止我们需要搜索所有节点：
如果我们曾经到达一个分支，在该分支中以该位序列开始的集合中有 0 个数字，我们可以修剪该分支并停止枚举。
一旦我们到达终端节点，我们就知道该特定数字出现了多少次。我们将此添加到我们的“前 100 名”列表中，必要时删除最低的。一旦此列表填满，我们就可以开始修剪总计数低于“前 100”计数中最低值的任何分支。
我不确定这的平均和最坏情况的性能是什么。对于具有较少不同数字的集合，它往往会表现得更好，而对于接近均匀分布的集合，它的表现可能最差，因为这意味着需要搜索更多的节点。
一些观察：
最多有 N 个非零计数的终端节点，但由于在这种特定情况下 N > 2^32，这无关紧要。
M 个叶节点（M = 2^32）的节点总数为 2M-1。这在 M 中仍然是线性的，因此最坏情况的运行时间限制在 O(N*M) 以上。
在某些情况下，这将比仅通过线性标量因子搜索所有整数表现更差。这是否平均表现更好取决于预期数据。对于均匀随机数据集，我的直觉猜测是，一旦前 100 个列表填满，您将能够修剪足够多的分支，而您往往需要少于 M 个计数，但这需要根据经验进行评估或证明。
实际上，该算法只需要对数据集进行只读访问（它只执行以特定位模式开始的数字计数）这一事实意味着它可以通过跨多个数组存储数据来进行并行化，并行计算子集，然后将计数加在一起。在实际实现中，这可能是一个相当大的加速，而需要排序的方法更难做到。
这是如何执行的一个具体示例，对于一组更简单的 3 位数字，并且只找到最频繁的一个。假设集合是 '000, 001, 100, 001, 100, 010'。
计算所有以“0”开头的数字。这个数是 4。
更深入地计算所有以“00”开头的数字。这个数是3。
计算所有为“000”的数字。这个计数是 1。这是我们新的最频繁的。
计算所有为“001”的数字。这个计数是 2。这是我们新的最频繁的。
进行下一个深分支并计算以“01”开头的所有数字。这个计数是 1，比我们最频繁的要少，所以我们可以停止枚举这个分支。
计算所有以“1”开头的数字。这个计数是 1，比我们最频繁的要少，所以我们可以停止枚举这个分支。
我们没有分支，所以我们完成了，“001”是最常见的。
小智 5
这只是在 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 个……数字具有相同的频率，会发生什么。整数只有正数吗？
他们需要什么样的输出，只是数字还是频率？只需像工作中的一项真正任务一样仔细考虑它，并询问您需要知道的一切来解决它。更多的是关于你如何思考和分析问题。