删除重复项的标准方法是对文件进行排序,然后执行顺序传递来删除重复项。对 5 亿行进行排序并不是一件小事,但它确实是可行的。几年前,我每天都有一个进程在 16 GB 的机器上对 50 到 100 GB 的数据进行排序。
顺便说一句,您也许可以使用现成的程序来完成此操作。当然,GNU 排序实用程序可以对大于内存的文件进行排序。我从未在 500 GB 文件上尝试过,但您可以尝试一下。您可以将其与其余部分一起下载GNU 核心实用程序 http://gnuwin32.sourceforge.net/packages/coreutils.htm。该实用程序有一个--unique
选项,所以你应该能够sort --unique input-file > output-file
。它使用了一种类似于我下面描述的技术。我建议首先在 100 MB 的文件上尝试,然后慢慢处理更大的文件。
使用 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 路合并。这是通过创建优先级队列来完成的。您打开每个文件,读取每个文件的第一行,并将其连同对它来自的文件的引用一起放入队列中。然后,从队列中取出最小的项目并将其写入输出文件。要删除重复项,您需要跟踪输出的前一行,如果新行与前一行相同,则不会输出新行。
输出该行后,您可以从刚刚输出的文件中读取下一行,并将该行添加到优先级队列中。继续这种方式,直到清空所有文件。
我不久前发表了一系列文章。它使用了我上面描述的技术。它唯一不做的就是删除重复项,但这是对输出临时文件的方法和最终输出方法的简单修改。即使没有优化,程序的性能也相当好。它不会创造任何速度记录,但它应该能够在不到 12 小时的时间内对 5 亿行进行排序并删除重复项。考虑到第二遍仅处理总数据的一小部分(因为您从临时文件中删除了重复项),可能要少得多。
为了加快程序速度,您可以做的一件事是对较小的块进行操作,并在将下一个块加载到内存中时在后台线程中对一个块进行排序。您最终不得不处理更多的临时文件,但这确实不是问题。堆操作稍微慢一些,但是通过将输入和输出与排序重叠来重新获得额外的时间是不够的。您最终基本上免费获得 I/O。在典型的硬盘速度下,加载 500 GB 需要大约两个半到三个小时。
看看该系列文章。这是许多不同的文章,大部分是小文章,可以引导您完成我描述的整个过程,并且它提供了工作代码。我很乐意回答您对此可能提出的任何问题。