Scalaで書かれた私の重複排除アプリケーションが遅いのはなぜですか？

Question

私はいくつかの重複したレコードがたくさんあるテキストファイル（200 MiB〜2 GiBと言う）を持っています。各行には、約100以上の重複がファイル上に広がっています。タスクはすべての繰り返しを削除し、各レコードの一意のインスタンスを残します。

次のように私はそれを実装しました：

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() 
    } 
} 

をそして、92 MIBファイルを処理するために〜15分（4 GBのRAMと私のコアに2デュオ）かかります。次のコマンド中：

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

は（私の上記のコードで多くの時間を取る）1.1ジブファイルを処理する分程度かかり。

私のコードで何が問題になっていますか？

Answer 1

何が問題なのは、配列を使用して線を保存していることです。ルックアップ（lines.contains）はO（n）を配列内に持つため、すべてがO（n2）時間で実行されます。対照的に、Awkソリューションは、O（1）ルックアップとO（n）の合計実行時間を意味するハッシュテーブルを使用します。

代わりにmutable.HashSetをお試しください。

Answer 2

また、すべての行を読み、.distinctを呼び出すこともできます。 distinctがどのように実装されているのかわかりませんが、HashSetを使って賭けています。