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

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，它是为对无法放入内存的大量数据进行排序而发明的，并且比上述方法更快。它对整个数据集的小块（可以放入内存）进行排序，将它们存储到临时文件中，然后将它们合并在一起。有趣的是，如果您的 OS 有一个虚拟内存选项，那么 OS 将通过将不适合内存的数据交换到硬盘驱动器来为您做类似的事情。

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

Answer 2

您可以使用布隆过滤器(https://en.m.wikipedia.org/wiki/Bloom_filter)从文件中删除重复项

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

removing duplicates from list without storing list in memory

java

performance

scala

out-of-memory