讨论一道面试题啊(take home task)

[wangpugod2003]

题目很简单，就是一个文件，里面的数据就是 ID->value：

<unique ID> <space> <value>

例如： 123131321   100

135235423   101

132523121    80

...

给定一个值 n ，返回最大的 n 个值的 ID: 比如上面 n=2 ，就应该返回:

135235423   

123131321   

就是个 top k 的问题，也不要求返回的 id 的顺序。唯一的要求是这个文件极端的大。

我理解单个文件，哪怕几百 G 吧，我直接 java 中按照 BufferedReader 一行行的读，再用 size 为 n 的 PriorityQueue 梳理一遍整个<id->value>即可，时间复杂度就是 O(lines * logn)。

也写了单元测试+集成测试，各种不合法的 corn case 都处理了，生成了个 10G 的文件(几十亿条)测试了就一分多钟就出来结果。不知道怎么提交上去还是挂了。。

大家觉得应该用啥高级些的算法么？

[zhy0216]

size 为 k 就够吧 每一个和最小的比较 大才进这个堆

[wangpugod2003]

@zhy0216 哦，我题目没写清楚，就是这里的 n 就是 k ，我改下。

[Sawyerhou]

可能用大顶堆更好，queue 底层是二叉堆吧，另外，算法题代码最好手搓，别用库，体现不出水平

[coyove]

工作碰到过类似场景，从 mq 读一组数据，取 topk 打入下游 mq ，问题是 k 很大。
第一版是把 k 拆成比如 k=10m ，然后串行跑 10 遍，取 top 0-m, top m-2m, ... top 8m-9m
第二版直接存 redis zset 了，更符合工程师思维
第三版直接交给 data 那边做，上 flink

[wxf666]

极端情况下，每个 ID 只出现一次，

你是要在内存里，保留整个 几百 GB 的 ID 吗？

[wxf666]

@wxf666 #5 等会儿，我以为是，求出现最多次数的 ID 了。。

那你这个算法，应该没问题的呀？

[geelaw]

@Sawyerhou #3 堆是否是大顶和是否是二项是两个正交的概念。

回到楼主的问题，描述实在是 underspecified ，数据范围是什么？是否大到需要使用非托管代码？ ID 和 value 是 int 可返程表示的吗？挂了是指代码机器评测不通过，还是指面试之后拒绝录用？后者的情况下可能和代码是否机器评测通过无关。

[GeekGao]

外部排序：

1.将文件分割成多个小块，每个小块可以在内存中排序。
2. 对每个小块进行排序，并将排序后的小块写入临时文件。
3. 合并所有排序后的小块，得到一个大的排序数组。
4.从排序后的数组中选择最大的 n 个值的 ID 。

[aboutyang]

PriorityQueue 中的排序没必要，可以用个数组不断替换其中的最小值。

[GeekGao]

意思是说这思路不行？？？

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

public class ExternalSorter {
public static void main(String[] args) throws IOException {
String inputFile = "bigfile.txt"; // 输入文件路径
String tempDirectory = "temp"; // 临时文件目录
int maxMemory = 1024*1024*1024; // 假设最大内存使用量限制为 1GB

try (BufferedReader reader = new BufferedReader(new FileReader(inputFile))) {
String line;
int fileCounter = 0;
while ((line = reader.readLine()) != null) {
// 使用 PriorityQueue 在内存中对行进行排序
PriorityQueue<String> sortedLines = new PriorityQueue<>();
sortedLines.add(line);

// 继续读取行，直到内存使用达到限制
int memoryUsage = line.length();
while (memoryUsage <= maxMemory && (line = reader.readLine()) != null) {
sortedLines.add(line);
memoryUsage += line.length();
}

// 将排序后的行写入临时文件
File tempFile = new File(tempDirectory, "tempfile" + fileCounter + ".txt");
try (BufferedWriter writer = new BufferedWriter(new FileWriter(tempFile))) {
while (!sortedLines.isEmpty()) {
writer.write(sortedLines.poll());
writer.newLine();
}
}

fileCounter++;
}
}

// 合并临时文件
mergeTemporaryFiles(tempDirectory);

// 清理临时文件
cleanUpTemporaryFiles(tempDirectory);
}

private static void mergeTemporaryFiles(String tempDirectory) throws IOException {
File[] tempFiles = new File(tempDirectory).listFiles();
PriorityQueue<BufferedReader> readers = new PriorityQueue<>((br1, br2) -> {
try {
String line1 = br1.readLine();
String line2 = br2.readLine();
return line1.compareTo(line2);
} catch (IOException e) {
throw new RuntimeException(e);
}
});

for (File tempFile : tempFiles) {
BufferedReader reader = new BufferedReader(new FileReader(tempFile));
readers.add(reader);
}

String outputFile = "output.txt"; // 输出文件路径
try (BufferedWriter writer = new BufferedWriter(new FileWriter(outputFile))) {
while (!readers.isEmpty()) {
BufferedReader reader = readers.poll();
String line = reader.readLine();
if (line != null) {
writer.write(line);
writer.newLine();
readers.add(reader);
} else {
reader.close();
}
}
}
}

private static void cleanUpTemporaryFiles(String tempDirectory) {
File[] tempFiles = new File(tempDirectory).listFiles();
for (File tempFile : tempFiles) {
tempFile.delete();
}
}
}

[lyminghao]

value 的范围有条件吗

[fkdtz]

这题如果是纯算法题，那么除了外部排序加最小堆真没别的思路了。
如果是个实际工程题那就可以并发处理，每组并发线程都做 topK ，最后汇总 topK ，类似 MapReduce 。

蹲个后续看看纯算法的话有其他什么方案。

[wxf666]

@wangpugod2003 #2 楼主，我突然对你的 10GB 文件感兴趣。。


假设你 10GB 二十亿条，那平均每条 (10 << 30) / 2e9 = 5 字节，

去除空格、换行 2 字节，还剩 3 字节，你是怎么存得下 10 位数的 ID ，和几位数的 value 呢？

[Sawyerhou]

@geelaw 我默认 priority queue 就是二叉堆，二叉堆就大顶堆和小顶堆，确实有三叉四叉，或者二叉无序堆，咬文嚼字没啥意思

op 的算法没问题，我理解有误，不过我还是觉得手搓算法题比较好，也可能如楼上说的，这是生产问题，不是在考算法，或者单纯就是人招到了

[geelaw]

@Sawyerhou #14 我很难理解 #3 想表达的意思，因为前两个分句的意思听起来风马牛不相及，我尝试的理解是“应该用大顶堆，pq 自带的二叉堆（不是大顶堆所以）不够好”，这当然是 nonsense 。堆不考虑无序，也通常不考虑二叉和多叉的区别，在“二叉”这个属性上的另外选项是指“二项”和 Fibonacci 等。

另外我需要更正一下#7 ，应该在例子里面用“二叉”而不是“二项”。

最后，比较自然的想法是使用小顶堆，因为需要反复查询、替换堆中的最小值，这表示堆顶应该是最小值。

[lvlongxiang199]

感觉可以并行来跑, 充分利用 CPU 多核. 启动多个线程, 每个线程同时做 topK, 最后 merge 成一个

[Sawyerhou]

@geelaw 我一开始记错了，把 pq 底层当成有序二叉树了，所以才说大顶堆更好，op 写的没问题，这里我理解的不对

至于用小顶堆，我不太理解为什么，为了方便把所有数据都放进堆里？

[kenberkeley]

@GeekGao 我觉得你的这个思路很好。

其中第 3 步「合并所有排序的小块」其实还能优化一下，只要凑够前 n 个元素就够了，不用真的把所有小块都处理完毕。由此第 4 步也省了。

[Sawyerhou]

@geelaw 哦，是的是的，你说的对，op 的帖子我看的太不仔细了，下次要检查检查再回复了:P

[fkdtz]

@Sawyerhou topK 用小顶堆恰恰就是为了不把所有数据放进堆里吧，这样复杂度 logk ，要是用大顶堆 logn 了。
还是说我没理解你的意思，用大顶堆是有什么特殊考虑吗？

[BanGanExpert]

既然做了基准测试，那么是不是该测试下自己读取所花的时间和内部排序的时间比例，在确认下优化方案。

[Sawyerhou]

@fkdtz 想当然以为从小到大，看了楼上回复后又回去看了一眼 op 的题目，是要大值，读题不仔细，见笑见笑，下次要仔细些了

[chesha1]

先确定挂了是不是时间复杂度的问题，堆排序的复杂度是 O （ n log k ），按理说已经很不错了

如果是因为 k 很大的话不通过的话，试下随机选择，这个应该能有 O （ n ）

再不行用 BFPRT ，最坏也有 O （ n ），这个还不行应该试试用工程方法了，比如看看怎么并行或者引入第三方方案

[BanGanExpert]

而且我觉得我以前看到的这个项目也可能是解决你这个问题的一个思路，虽然没有直接解决你这里的 topk ，https://github.com/gunnarmorling/1brc

[pennai]

@aboutyang 并不，用 PriorityQueue 不是为了保存最小值，是为了保存某个分块中（ map-reduce 做法），最小的 k 个，因为有一种情况下是最小的 k 个都在同一块，这时你只保留一个最小值是不够的

[wangpugod2003]

@geelaw 数据范围、ID 或者 value 的大小格式等等条件都未知，只告诉了你：
1 。数据文件极端的大；
2 。最好有 test ，当成最终要 deploy 到生产的版本去做。

最后就是这个题提上去说没过，interview not process 了。
我还是用的工程化的 java project ，搞了一堆 unit test ，integration test ，docker 镜像，然后 READEME 写的很清楚。。

[WoodsGao]

@wxf666 #13 这种情况就不需要换行了呀，序列化结构体就行，每 5 字节就是一组数据。5 字节分配好，上限非常大

[wangpugod2003]

@fkdtz 我怀疑是需要用多线程并发读取文件的，不然如果文件到 TB 的话，读取是个很耗时的动作。
另外，外排我也考虑过，但是后面又觉得没必要。。
最小堆的算法时间和空间复杂度都还可以。

[JackCh3ng]

你这题面上的 value 有做限制吗？如果你的例子里三个 id 的值都是 100 ，然后 n=2 ，请问要返回几个 id 呢？

[wangpugod2003]

@JackCh3ng 我做了限制，value 限制为 long ，ID 我是 string 类型的，value 如果超过 long 的范围就打印出 warning 。

[wangpugod2003]

外排我为什么后来觉得没必要呢，是因为 TOP k 问题不需要对原文件进行排序，如果排序的话内存的消耗太大，时间复杂度最少 O(nlogN)吧，算上至少读取一次文件，明显时间复杂度远大于小根堆的方式。

[wangpugod2003]

@JackCh3ng 哦，如果 n=2 ，那么在三个相等的值中任意返回两个 ID 即可。

[wxf666]

@WoodsGao #27 题目的原文件，应该是十进制字符串吧。。

就算是二进制数据，也应该是 8 字节，俩 int32 呀。。

[WoodsGao]

@wxf666 #33 这么大规模的数据真没人用字符串,而且也不需要 int32,很多这类文件都用了压缩的办法,比如先用一个字节存下后面一个数的字节数

[uliah]

@kenberkeley #18 无论如何,文件都需要全部处理完才能得到 TOP K 吧?

通常第三第四步从每个临时文件里面取前 k 个值 然后再次排序,这样好处时临时文件可以重复使用.

不过第二步既然排序了, 不如额外记录一些值, 比如 max.value max.count
如果 max.count >= k , 后续每个分片处理只需要比较 max.value

不过感觉分片效率依旧很低，学习一下流处理