最终
初赛排名42名,得分 240.69s,Java代码实现,总结文章
复赛排名49名,得分 606.47s,Java代码实现,总结如下。
本来其实是还想写个总结的,但复赛成绩实在不太理想,一方面是在实习,只能夜里打打比赛,一方面是因为开的线程导致timeout问题卡了太久。
这里我贴上两位Java大佬的分享,自己就不再写完整的总结文章了,因为其实到了后面大家的思路就都非常近似,没有什么非常独特地方了。
neoReMinD大佬的分享
kirito大佬的分享
我最后的实现:
- 64个key文件,用mmap写入和做open时的读取,写入时利用hashmap去重,key根据前6位分文件,文件内无序,文件本身有序。
- 512个value文件,每个520M,fileChannel写入和随机读取,写入时根据key的前9位划分文件,让value文件之间有序。
- 索引为一个6400w的大long型数组,对应的offset记录在大int型数组中相同index处(read时利用二分查找取索引)。
- open时 64个线程读取key文件,因为文件之间相对有序,故直接在读取完成后进行快排对这一文件中的key进行排序
- 2块520M的DirectByteBuffer作为range的共享缓存,一块读,一块做预读操作。利用CycleBarrier和阻塞队列(或者自旋锁,或者等待通知均可)保证同步。
最后大概 open 1.5s fillRandom 118s readRandom 113s range 380~400s。
因为我是那种写出来一版,再接下来思考下一版的那种写法。还没有达到直接找到最优解的境界。
但是时间最后不够了,得分的版本就止步在这了。还是比较难受的。
提一下我想了要做但没来及实现的:
- range处把2块buffer替换为4个buffer,移除CycleBarrier,利用自旋或者其他等待通知的方式实现类似于滑动窗口式的文件读取过程。
- 调整我的代码结构。。因为一开始初赛没考虑太多,导致代码非常混乱,后来复赛来不及拆分了。
后来看大佬们分享又收获到的一些其他点:
- 随机读写阶段可以利用dio来实现,性能更高,同时减少了清空pageCache的时间。
- 利用将IO线程进行的绑核来减少IO线程的时间片争用。
因为还没来得及对几位大佬的代码和文章细细研究,所以说的很少,后面有新发现还会补充上来。
太菜了,菜鸡不配写博客。