题目很简单,就是一个文件,里面的数据就是 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 的文件(几十亿条)测试了就一分多钟就出来结果。不知道怎么提交上去还是挂了。。
大家觉得应该用啥高级些的算法么?
1
zhy0216 224 天前 via Android
size 为 k 就够吧 每一个和最小的比较 大才进这个堆
|
2
wangpugod2003 OP @zhy0216 哦,我题目没写清楚,就是这里的 n 就是 k ,我改下。
|
3
Sawyerhou 224 天前 via Android
可能用大顶堆更好,queue 底层是二叉堆吧,另外,算法题代码最好手搓,别用库,体现不出水平
|
4
coyove 224 天前
工作碰到过类似场景,从 mq 读一组数据,取 topk 打入下游 mq ,问题是 k 很大。
第一版是把 k 拆成比如 k=10m ,然后串行跑 10 遍,取 top 0-m, top m-2m, ... top 8m-9m 第二版直接存 redis zset 了,更符合工程师思维 第三版直接交给 data 那边做,上 flink |
5
wxf666 224 天前
|
7
geelaw 224 天前 via iPhone
@Sawyerhou #3 堆是否是大顶和是否是二项是两个正交的概念。
回到楼主的问题,描述实在是 underspecified ,数据范围是什么?是否大到需要使用非托管代码? ID 和 value 是 int 可返程表示的吗?挂了是指代码机器评测不通过,还是指面试之后拒绝录用?后者的情况下可能和代码是否机器评测通过无关。 |
8
GeekGao 224 天前
外部排序:
1.将文件分割成多个小块,每个小块可以在内存中排序。 2. 对每个小块进行排序,并将排序后的小块写入临时文件。 3. 合并所有排序后的小块,得到一个大的排序数组。 4.从排序后的数组中选择最大的 n 个值的 ID 。 |
9
aboutyang 224 天前
PriorityQueue 中的排序没必要,可以用个数组不断替换其中的最小值。
|
10
GeekGao 224 天前
意思是说这思路不行???
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(); } } } |
11
lyminghao 224 天前
value 的范围有条件吗
|
12
fkdtz 224 天前
这题如果是纯算法题,那么除了外部排序加最小堆真没别的思路了。
如果是个实际工程题那就可以并发处理,每组并发线程都做 topK ,最后汇总 topK ,类似 MapReduce 。 蹲个后续看看纯算法的话有其他什么方案。 |
13
wxf666 224 天前
@wangpugod2003 #2 楼主,我突然对你的 10GB 文件感兴趣。。
假设你 10GB 二十亿条,那平均每条 (10 << 30) / 2e9 = 5 字节, 去除空格、换行 2 字节,还剩 3 字节,你是怎么存得下 10 位数的 ID ,和几位数的 value 呢? |
14
Sawyerhou 224 天前 via Android
@geelaw 我默认 priority queue 就是二叉堆,二叉堆就大顶堆和小顶堆,确实有三叉四叉,或者二叉无序堆,咬文嚼字没啥意思
op 的算法没问题,我理解有误,不过我还是觉得手搓算法题比较好,也可能如楼上说的,这是生产问题,不是在考算法,或者单纯就是人招到了 |
15
geelaw 224 天前 via iPhone
@Sawyerhou #14 我很难理解 #3 想表达的意思,因为前两个分句的意思听起来风马牛不相及,我尝试的理解是“应该用大顶堆,pq 自带的二叉堆(不是大顶堆所以)不够好”,这当然是 nonsense 。堆不考虑无序,也通常不考虑二叉和多叉的区别,在“二叉”这个属性上的另外选项是指“二项”和 Fibonacci 等。
另外我需要更正一下#7 ,应该在例子里面用“二叉”而不是“二项”。 最后,比较自然的想法是使用小顶堆,因为需要反复查询、替换堆中的最小值,这表示堆顶应该是最小值。 |
16
lvlongxiang199 224 天前
感觉可以并行来跑, 充分利用 CPU 多核. 启动多个线程, 每个线程同时做 topK, 最后 merge 成一个
|
17
Sawyerhou 224 天前 via Android
|
18
kenberkeley 224 天前 via iPhone
|
20
fkdtz 224 天前
@Sawyerhou topK 用小顶堆恰恰就是为了不把所有数据放进堆里吧,这样复杂度 logk ,要是用大顶堆 logn 了。
还是说我没理解你的意思,用大顶堆是有什么特殊考虑吗? |
21
BanGanExpert 224 天前 via iPhone
既然做了基准测试,那么是不是该测试下自己读取所花的时间和内部排序的时间比例,在确认下优化方案。
|
23
chesha1 224 天前
先确定挂了是不是时间复杂度的问题,堆排序的复杂度是 O ( n log k ),按理说已经很不错了
如果是因为 k 很大的话不通过的话,试下随机选择,这个应该能有 O ( n ) 再不行用 BFPRT ,最坏也有 O ( n ),这个还不行应该试试用工程方法了,比如看看怎么并行或者引入第三方方案 |
24
BanGanExpert 224 天前
而且我觉得我以前看到的这个项目也可能是解决你这个问题的一个思路,虽然没有直接解决你这里的 topk ,https://github.com/gunnarmorling/1brc
|
25
pennai 224 天前
@aboutyang 并不,用 PriorityQueue 不是为了保存最小值,是为了保存某个分块中( map-reduce 做法),最小的 k 个,因为有一种情况下是最小的 k 个都在同一块,这时你只保留一个最小值是不够的
|
26
wangpugod2003 OP @geelaw 数据范围、ID 或者 value 的大小格式等等条件都未知,只告诉了你:
1 。数据文件极端的大; 2 。最好有 test ,当成最终要 deploy 到生产的版本去做。 最后就是这个题提上去说没过,interview not process 了。 我还是用的工程化的 java project ,搞了一堆 unit test ,integration test ,docker 镜像,然后 READEME 写的很清楚。。 |
28
wangpugod2003 OP |
29
JackCh3ng 223 天前
你这题面上的 value 有做限制吗?如果你的例子里三个 id 的值都是 100 ,然后 n=2 ,请问要返回几个 id 呢?
|
30
wangpugod2003 OP @JackCh3ng 我做了限制,value 限制为 long ,ID 我是 string 类型的,value 如果超过 long 的范围就打印出 warning 。
|
31
wangpugod2003 OP 外排我为什么后来觉得没必要呢,是因为 TOP k 问题不需要对原文件进行排序,如果排序的话内存的消耗太大,时间复杂度最少 O(nlogN)吧,算上至少读取一次文件,明显时间复杂度远大于小根堆的方式。
|
32
wangpugod2003 OP @JackCh3ng 哦,如果 n=2 ,那么在三个相等的值中任意返回两个 ID 即可。
|
35
uliah 223 天前
@kenberkeley #18 无论如何,文件都需要全部处理完才能得到 TOP K 吧?
通常第三第四步从每个临时文件里面取前 k 个值 然后再次排序,这样好处时临时文件可以重复使用. 不过第二步既然排序了, 不如额外记录一些值, 比如 max.value max.count 如果 max.count >= k , 后续每个分片处理只需要比较 max.value 不过感觉分片效率依旧很低,学习一下流处理 |