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