java - 从列表中删除重复项而不将列表存储在内存中

Question

我正在尝试找到一种有效的方法来删除文件中的重复行，而无需将文件的全部内容读入内存。该文件是随机排序的。我试图不将它读入内存，因为文件太大(20GB+)。谁能建议一种方法来修复我的代码，使其不会将整个文件读入内存？

val oldFile="steam_out_scala.txt"
val noDupFile="nodup_steam_out.txt"

import scala.io.Source
import java.io.{FileReader, FileNotFoundException, IOException}
import java.io.FileWriter;
import scala.collection.mutable.ListBuffer

var numbers = new ListBuffer[String]()
val fw = new FileWriter(noDupFile, true) 

for (line <- Source.fromFile(oldFile).getLines()) {
    numbers+=line

}

numbers.distinct.foreach((x)=>{
    //println(x)
    fw.write(x)
})
fw.close()    

我对数据的了解:

每一行都是一个Long ex: 76561193756669631

不是有序的，最终的结果不需要任何排序

该列表是使用另一个程序生成的。一个数字可以重复 (0,400 万]

Answer 1

有几种方法可以解决这个问题:

1) 逐行读取原始文件，在将其添加到仅包含唯一行的新文件之前检查该文件是否存在这样的行。这将非常慢，因为 O(n^2)。

代码看起来像这样:

val oldFile="steam_out_scala.txt"
val noDupFile="nodup_steam_out.txt"

import scala.io.Source
import java.io.{FileReader, FileNotFoundException, IOException}
import java.io.FileWriter;
import scala.collection.mutable.ListBuffer

var numbers = new ListBuffer[String]()
val fw = new FileWriter(noDupFile, true) 

for (line <- Source.fromFile(oldFile).getLines()) {
    if(Source.fromFile(noDupFile).getLines().forall(!_.equals(line))) {
        fw.write(line)
    }
}

fw.close()

2) 您可以执行所谓的 external sort它的发明正是为了对无法放入内存的大量数据进行排序，并且比上述方法更快。它对整个数据集的小块(可以放入内存)进行排序，将它们存储到临时文件中，然后将它们合并在一起。有趣的是，如果您的操作系统有虚拟内存选项，那么操作系统无论如何都会为您做类似的事情，将不适合内存的数据交换到硬盘驱动器。

这些是适用于任何类型数据的通用解决方案。如果您可以提供有关文件内容的更多信息，我们或许可以想出一些更聪明的办法。