为什么Scala写的线路重复数据删除应用程序很慢？

我有一些大的（比方说200 MiB - 2 GiB）文本文件充满了大量的重复记录。每行可以有大约100个甚至更多精确的重复文件分布在文件中。任务是删除所有重复，留下每个记录的唯一实例。为什么Scala写的线路重复数据删除应用程序很慢？

我如下实现它：


object CleanFile { 
    def apply(s: String, t: String) { 
    import java.io.{PrintWriter, FileWriter, BufferedReader, FileReader} 

    println("Reading " + s + "...") 

    var linesRead = 0 

    val lines = new scala.collection.mutable.ArrayBuffer[String]() 

    val fr = new FileReader(s) 
    val br = new BufferedReader(fr) 

    var rl = "" 

    while (rl != null) { 
     rl = br.readLine() 

     if (!lines.contains(rl)) 
     lines += rl 

     linesRead += 1 

     if (linesRead > 0 && linesRead % 100000 == 0) 
     println(linesRead + " lines read, " + lines.length + " unique found.") 
    } 

    br.close() 
    fr.close() 

    println(linesRead + " lines read, " + lines.length + " unique found.") 
    println("Writing " + t + "...") 

    val fw = new FileWriter(t); 
    val pw = new PrintWriter(fw); 

    lines.foreach(line => pw.println(line)) 

    pw.close() 
    fw.close() 
    } 
}

它需要15分钟（在我的Core 2 Duo处理器，4 GB RAM）来处理92 MIB文件。虽然下面的命令：

awk '!seen[$0]++' filename

需要大约一分钟来处理1.1吉布文件（这将需要许多小时以矿的上面的代码）。

我的代码有什么问题？

来源

2012-01-28 Ivan

尝试使用散列而不是该ArrayBuffer。 – Mat 2012-01-28 11:56:15

什么是错误的是，你正在使用数组来存储行。查找（lines.contains）将O（n）放在一个数组中，所以整个事件在O（n²）时间内运行。相比之下，Awk解决方案使用哈希表，即O（1）查找和总运行时间O（n）。

尝试使用mutable.HashSet代替。

来源

2012-01-28 12:00:58

确实，HashSet的速度更快，接近awk的结果。但它破坏了序列顺序（在我的情况下这是可以忍受的但不受欢迎的）。 Awk设法维持秩序并且仍然有点快。 – Ivan 2012-01-28 15:20:57

@Ivan：您可以通过更紧密地模拟Awk程序来保持订单;如果在哈希表中没有看到该行，立即发出并添加它，否则就忽略它。 – 2012-01-28 15:27:21

LinkedHashSets保留插入顺序http://www.scala-lang.org/api/current/scala/collection/mutable/LinkedHashSet.html – 2012-01-28 22:12:56

您也可以阅读所有行，并致电.distinct。我不知道distinct是如何实现的，但我打赌它使用HashSet来做到这一点。

来源

2012-01-28 14:27:33

为什么Scala写的线路重复数据删除应用程序很慢？

回答

相关问题