use*_*329 4 c# c++ java perl duplicates
我真的很难过这个问题,因此我已经停止工作了一段时间.我使用非常大的数据.我每周得到大约200GB的.txt数据.数据范围可达5亿行.其中很多都是重复的.我猜只有20gb是独一无二的.我有几个自定义程序,包括哈希删除重复项,外部删除重复项,但似乎没有工作.最新的一个是使用临时数据库,但需要几天时间才能删除数据.
所有程序的问题在于它们在某一点之后崩溃,并且在这些程序上花了大量资金后,我以为我会上网看看是否有人可以提供帮助.我知道这已经在这里得到了回答,我花了最近3个小时在这里读了大约50个线程,但似乎没有像我这样的大数据集.
谁能为我推荐任何东西？它需要超级准确和快速.最好不要基于内存,因为我只有32GB的内存工作.
删除重复项的标准方法是对文件进行排序,然后执行顺序传递以删除重复项.排序5亿行不是微不足道的,但它肯定是可行的.几年前,我有一个日常的过程,在16 GB的机器上排序50到100 GB.
顺便说一句,您可以使用现成的程序来完成此操作.当然,GNU排序实用程序可以对大于内存的文件进行排序.我从来没有尝试过500 GB的文件,但你可能会试一试.您可以将其与其他GNU Core Utilities一起下载.该实用程序有一个--unique选项,所以你应该能够sort --unique input-file > output-file.它使用类似于我在下面描述的技术.我建议先在100兆字节的文件上尝试,然后慢慢处理更大的文件.
使用GNU排序和我在下面描述的技术,如果输入和临时目录位于不同的物理磁盘上,它将执行得更好.将输出放在第三个物理磁盘上,或放在与输入相同的物理磁盘上.您希望尽可能减少I/O争用.
可能还有一个商业(即付费)程序将进行排序.开发一个能够有效地对大型文本文件进行排序的程序是一项非常重要的任务.如果你可以买几百美元的东西,如果你的时间有价值的话,你可能会提前赚钱.
如果你不能使用现成的程序,那么...
如果您的文本包含多个较小的文件,则问题更容易解决.首先,对每个文件进行排序,从这些文件中删除重复项,然后编写已删除重复项的已排序临时文件.然后运行一个简单的n路合并,将文件合并到一个删除了重复项的输出文件中.
如果您有一个文件,首先要读取尽可能多的行到内存,排序,删除重复文件和编写临时文件.你会继续为整个大文件做这件事.完成后,您可以合并一些已排序的临时文件.
在伪代码中,它看起来像这样:
fileNumber = 0
while not end-of-input
load as many lines as you can into a list
sort the list
filename = "file"+fileNumber
write sorted list to filename, optionally removing duplicates
fileNumber = fileNumber + 1
您实际上不必从临时文件中删除重复项,但如果您的唯一数据实际上只占总数的10%,则通过不向临时文件输出重复数据可以节省大量时间.
写入所有临时文件后,需要合并它们.根据您的描述,我认为您从文件中读取的每个块将包含大约2000万行.所以你可能有25个临时文件可供使用.
您现在需要进行k-way合并.这是通过创建优先级队列来完成的.打开每个文件,从每个文件中读取第一行并将其放入队列以及对其来自的文件的引用.然后,从队列中取出最小的项目并将其写入输出文件.要删除重复项,您可以跟踪输出的上一行,如果新行与前一行相同,则不输出新行.
输出行后,您将从文件中读取刚刚输出的行的下一行,并将该行添加到优先级队列中.你继续这样,直到你清空了所有的文件.
我在一段时间后发表了一系列关于排序非常大的文本文件的文章.它使用我上面描述的技术.它唯一没有做的是删除重复项,但这是对输出临时文件和最终输出方法的方法的简单修改.即使没有优化,该程序也表现良好.它不会设置任何速度记录,但它应该能够在不到12小时内从5亿行中排序和删除重复数据.考虑到第二遍仅使用总数据的一小部分(因为您从临时文件中删除了重复项),可能要少得多.
加速程序可以做的一件事是在较小的块上运行,并在将下一个块加载到内存中时在后台线程中对一个块进行排序.您最终不得不处理更多临时文件,但这确实不是问题.堆操作稍微慢一点,但是通过将输入和输出与排序重叠来重新获得额外的时间.您最终获得的I/O基本上是免费的.在典型的硬盘驱动器速度下,加载500千兆字节将需要在两个半小时到三个小时左右的某个地方.
看一下文章系列.它是许多不同的,大多数是小的文章,它们将引导您完成我描述的整个过程,并提供有效的代码.我很乐意回答您可能遇到的任何问题.