Почему мое приложение для дедупликации строк, написанное на 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()
  }
}

И это занимает ~ 15 минут (на моем ядре2 Duo с 4 ГБ ОЗУ) для обработки файла объемом 92 МБ.В то время как следующая команда:

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

Занимает около минуты, чтобы обработать файл 1.1 ГиБ (что заняло бы много часов с моим вышеупомянутым кодом).1011 *

Answer 1

Что плохого в том, что вы используете массив для хранения строк.Lookup (lines.contains) принимает O ( n ) в массиве, поэтому все это выполняется за O ( n ²) времени.В отличие от этого, решение Awk использует хеш-таблицу, что означает поиск O (1) и общее время выполнения O ( n ).

Попробуйте использовать mutable.HashSet вместо.

Answer 2

Вы также можете просто прочитать все строки и вызвать .distinct на них.Я не знаю, как реализовано distinct, но держу пари, что для этого используется HashSet.