Блог пользователя frp

Автор frp, 11 лет назад, По-русски

Всем привет. Опять пишу о Scala и ее быстродействии. На этот раз о производительности ввода-вывода, о быстродействии, или, точнее, медленнодействии println и java.util.Scanner.

История о выводе

Решал я задачу. Единственной интересной для нас особенностью ее является то, что в ней возникает необходимость вывести миллион чисел. Если кратко, то мое решение получает список чисел, который затем нужно вывести, каждое число в новой строке, и на обеих концах списка — барьерные элементы (-1), которые выводить не нужно. Этот список — это list типа scala.collection.mutable.LinkedList[Int]. Первая попытка, самая очевидная:

    var next = list.next
    while (next.elem != -1) {
      println(next.elem)
      next = next.next
    }

Конечно же, попытка эта успешно обламывается с TLE.

Оказывается, println медленный. Заместо этого создаю StringBuilder и запихиваю в него результаты, и лишь затем вывожу при помощи print:

    var next = list.next
    val sb = new StringBuilder()
    while (next.elem != -1) {
      sb.append(next.elem).append("\n")
      next = next.next
    }
    print(sb)

Результат: полное решение. Попался на подобном во второй раз. Когда было в первый раз, я попался одновременно и на этом, и на вводе.

История о вводе

Решал я задачу. На скале решать я начал совсем недавно, поэтому о подводных камнях Scala и JVM вообще в плане быстродействия знаю немного. Первая посылка дала TLE#23. Это было из-за вывода, та же проблема, что описана выше, но я-то тогда этого не знал и стал думать на ввод, который делался при помощи такой функции:

def readLineOfNums(): Array[Long] = readLine().split(" ").map(_.toLong)

Что, очевидно, далеко не идеально по быстродействию, зато очень легко пишется и сравнительно удобно в использовании. Решил я вместо этого использовать java.util.Scanner, знакомый мне с Java, но ни разу не использованный в серьезных боевых условиях. И тут меня ждал неожиданный фейл: TLE#11. Как оказалось, на самом деле java.util.Scanner очень и очень тормозный, гораздо тормознее, чем мой способ. Я сдал эту задачу после того, как вернул обратно свой разбор ввода и пофиксил вывод.

Выводы

  1. println медленный. Если запихнуть всё в StringBuilder и затем вывести, будет быстрее. Да вот только это создает серьезные неудобства, когда вывода слишком много, чтобы одновременно весь хранить в памяти. Проблема явно актуальна и для Java, т.к. Scala-вский println вызывает System.out.println.
  2. java.util.Scanner медленный, причем аж до такой степени, что readLine().split(" ").map(_.toLong) его обгоняет. Не стоит его использовать там, где присутствует большой ввод. Мне весьма неочевидно, что же делает его таким медленным.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

Автор frp, 11 лет назад, По-русски

Всем привет. Сегодня я расскажу о своих приключениях с сортировкой массивов Scala, а также о найденном подводном камне этих сортировок, а также о том, почему для сортировки массивов элементарных типов все еще стоит использовать старый добрый java.util.Arrays.sort вместо scala.util.Sorting.quickSort.

История

Все началось с этой задачи (ссылка на разбор там есть). Для ее решения необходима сортировка массива Long-ов. Первый способ, который приходит в голову — это использовать scala.util.Sorting.quickSort. Моя посылка. Вердикт — TLE. Из этой посылки нас будут интересовать в дальнейшем только две строки:

    Sorting.quickSort(array)
    Sorting.quickSort(b)

Я был немного удивлен таким результатом. Но что поделать, пишу свою собственную сортировку, merge (люблю ее за то, что под нее, в отличии от квиксорта, нельзя подобрать плохой тест). Посылка. Нас из нее интересует это:

  def merge(a: Array[Long], b: Array[Long], l: Int, r:Int, m:Int) {
    var al_next = l
    var am_next = m + 1
    for (i <- l to r)
      if (am_next > r || (al_next <= m && a(al_next) < a(am_next))) {
        b(i) = a(al_next)
        al_next += 1
      }
      else {
        b(i) = a(am_next)
        am_next += 1
      }
  }
  def mergeSortAct(a: Array[Long], b: Array[Long], l: Int, r: Int) {
    if (l >= r)
      return
    val m = (l + r) / 2
    mergeSortAct(a, b, l, m)
    mergeSortAct(a, b, m+1, r)
    merge(a, b, l, r, m)
    Array.copy(b, l, a, l, r - l + 1)
  }
  def mergeSort(a: Array[Long]) {
    mergeSortAct(a, Array.ofDim[Long](a.length), 0, a.length - 1)
  }

И

    mergeSort(array)
    mergeSort(b)

Результат — полное решение. Хорошо, но я все же удивлен тем, что встроенная сортировка так сильно сливает. Идем дальше: пробуем сортировку из java (Scala ведь позволяет использовать любые Java-классы). Используем java.util.Arrays.sort. Посылка. Сортировка:

    Arrays.sort(array)
    Arrays.sort(b)

Результат — полное решение.

Гугление подсказало, что в Scala, помимо Sorting.quickSort, есть еще Sorting.stableSort, который реализован сортировкой слиянием. Пробую использовать. Попытка. ВНЕЗАПНО TLE#7, т.е., их сортировка слиянием работает хуже моей. Это меня очень заинтересовало, поэтому я отыскал соответствующий код (специально взял код из версии 2.9.0, как на codeforces, хотя в последующих версиях конкретно этот участок кода почти не менялся, единственное изменение — ClassManifest на ClassTag). Вот, собственно, функция, которая делает работу (все перегруженные версии stableSort в конечном итоге вызывают ее):

  private def stableSort[K : ClassTag](a: Array[K], lo: Int, hi: Int, scratch: Array[K], f: (K,K) => Boolean) {
    if (lo < hi) {
      val mid = (lo+hi) / 2
      stableSort(a, lo, mid, scratch, f)
      stableSort(a, mid+1, hi, scratch, f)
      var k, t_lo = lo
      var t_hi = mid + 1
      while (k <= hi) {
        if ((t_lo <= mid) && ((t_hi > hi) || (!f(a(t_hi), a(t_lo))))) {
          scratch(k) = a(t_lo)
          t_lo += 1
        } else {
          scratch(k) = a(t_hi)
          t_hi += 1
        }
        k += 1
      }
      k = lo
      while (k <= hi) {
        a(k) = scratch(k)
        k += 1
      }
    }
  }

Практически 1-в-1 с моей. Я было даже подумал "а вдруг у КФ какая-то неправильная Scala с другой реализацией сортировки" и перекопипастил это в мой код и отправил (естественно, TLE, ибо никакого заговора на самом деле нет). Тогда я стал анализировать отличия кода от моего. Вот:

  • имена переменных
  • слияние — в той же функции, что и сама сортировка
  • они везде используют циклы while, а я — for
  • я использую Array.copy, а они копируют циклом
  • моя сортировка заточена под Long, а их — универсальна и работает для всего
  • моя сортировка сравнивает элементы оператором <, а их — используя функцию, передаваемую в качестве аргумента

Естественно, первые три — это по большей мере косметическая разница, никакой реальной роли они не играют. Четвертое в теории могло бы играть какую-либо роль, но я попробовал сделать в своей реализации простое копирование циклом, и она все равно нормально проходила, заметного увеличения времени не было. А вот 5 и 6 — это и есть то самое место, где собака зарыта. Если взять функцию stableSort, заточить ее под Long и использовать обычные сравнения вместо функции, передаваемой аргументом, то она проходит все тесты. Вот так вот выглядит мой вариант этой функции:

  private def scalaMergeSort(a: Array[Long], lo: Int, hi: Int, scratch: Array[Long]) {
    if (lo < hi) {
      val mid = (lo+hi) / 2
      scalaMergeSort(a, lo, mid, scratch)
      scalaMergeSort(a, mid+1, hi, scratch)
      var k, t_lo = lo
      var t_hi = mid + 1
      while (k <= hi) {
        if ((t_lo <= mid) && ((t_hi > hi) || (a(t_lo) >= a(t_hi)))) {
          scratch(k) = a(t_lo)
          t_lo += 1
        } else {
          scratch(k) = a(t_hi)
          t_hi += 1
        }
        k += 1
      }
      k = lo
      while (k <= hi) {
        a(k) = scratch(k)
        k += 1
      }
    }
  }

Вот так вот. В java.util.Arrays мы имеем функции для сортировки массивов всех примитивных типов (разработчики вынуждены это делать, т.к. в Java нет способа написать универсальную функцию для сортировки всего). В Scala же такая возможность есть, и разработчики ею воспользовались. quickSort имеет отдельные реализации для Float, Double, Int, но не для Long. stableSort же один для всех типов. Такая универсальность требует жертв: в моем случае накладные расходы на вызов функции сравнения оказались слишком велики.

Выводы

  1. Если у вас Array[Long], и критерий сортирования — за неубыванием или невозрастанием, то сортируйте его при помощи java.util.Arrays.sort, либо своей собственной процедурой. Для Array[Int], Array[Float], Array[Double] специальные реализации scala.util.Sorting.quickSort есть, но после этого случая я бы побоялся на них полагаться.
  2. (капитан очевидность) Не стоит пренебрегать расходами на вызов функций. Это не C++, тут нет плюсовых компайл-тайм шаблонов и спасающих инлайнов.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +45
  • Проголосовать: не нравится