讨论一道面试题啊(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 的文件(几十亿条)测试了就一分多钟就出来结果。不知道怎么提交上去还是挂了。。

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

[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

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