Alc*_*ott 4 c++ algorithm data-structures
我有一个文件,可能是30 + GB或更多.并且此文件中的每一行称为记录,由2个列组成,如下所示
id1 id2
所有这2个ID都是整数(32位).我的工作是编写一个程序来删除所有重复记录,使记录唯一,最后将唯一的id2输出到一个文件中.
存在一些约束,最多允许30G内存,并且通过非多线程/进程程序更好地完成工作.
最初我提出了一个想法:由于内存的限制,我决定读取文件n次,每次只保留在那些记录中id1 % n = i (i = 0,1,2,..,n-1).我使用的数据结构是a std::map<int, std::set<int> >,它将id1作为键,并将id2放入id1中std::set.
这样,内存约束不会被违反,但速度很慢.我认为这是因为随着std::map并且std::set变大,插入速度会下降.此外,我需要读取文件n次,每轮完成后,我必须清除std::map下一轮,这也需要花费一些时间.
我也试过哈希,但它也不满足我,我认为即使300W桶也可能有太多的碰撞.
所以,我在这里发布我的问题,帮助你们给我任何更好的数据结构或算法.
非常感谢.
PS
如果脚本(shell,python)可以有效地执行它,那么它们是理想的.
除非我忽略了一个要求,否则应该可以在Linux shell上执行此操作
sort -u inputfile > outputfile
许多实现也允许您以sort并行方式使用:
sort --parallel=4 -u inputfile > outputfile
最多可以执行四次并行执行.
请注意,暂时sort可能会占用大量空间/tmp.如果磁盘空间不足,可以使用该-T选项将其指向磁盘上的备用位置以用作临时目录.
(编辑:)关于效率的一些评论:
sort是一个高度优化的东西.sort).同样,优化这意味着需要做很多工作,而sort所有这些工作都已完成.sort是它在输入线的字符串表示上操作.如果你要编写自己的代码,你可以做的一件事(类似于你已经建议的那样)就是将输入行转换为64位整数并对它们进行散列.如果你有足够的RAM,这可能是sort速度方面的一种方法,如果你得到IO和整数转换真的很快.我怀疑它可能不值得努力,因为sort它易于使用 - 我认为 - 足够快.