Всем привет. Сегодня я расскажу о своих приключениях с сортировкой массивов 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++, тут нет плюсовых компайл-тайм шаблонов и спасающих инлайнов.