Почему Clojure намного быстрее, чем Scala на рекурсивном добавляет функцию?
После быстрого взгляда на вашу модель (спасибо, что поделились этим), выясняется, что виновным является поведение по умолчанию параметра , нарушающего симметрию . В качестве обходного пути к вашей проблеме, если вы установите для параметра значение < = 2, тогда следует соблюдать ограничение по времени. Пожалуйста, дайте это попробовать. Более того, более новая версия CPLEX (в настоящее время находится в разработке), по-видимому, уже решает эту проблему, поэтому эта проблема должна быть решена в будущей версии CPLEX.
4 ответа
Во-первых, Scala оптимизирует хвостовые вызовы, только если вы вызываете его с помощью -optimise . Изменить : кажется, Scala всегда будет оптимизировать рекурсию хвостовых вызовов, если это возможно, даже без -оптимизации .
Во-вторых, Stream и Диапазон - это две очень разные вещи. Диапазон имеет начало и конец, а его проекция имеет только счетчик и конец. Поток - это список, который будет вычисляться по запросу. Поскольку вы добавляете целые целые , вы вычисляете и, следовательно, выделяете весь поток .
Более точный код будет:
import scala.annotation.tailrec
def add(r: Range) = {
@tailrec
def f(i: Iterator[Int], acc: Long): Long =
if (i.hasNext) f(i, acc + i.next) else acc
f(r iterator, 0)
}
def time(f: => Unit) {
val t1 = System.currentTimeMillis()
f
val t2 = System.currentTimeMillis()
println((t2 - t1).asInstanceOf[Float]+" msecs")
}
Нормальный запуск:
scala> time(println(add(1 to 9999999)))
49999995000000
563.0 msecs
В Scala 2.7 вам нужен « elements » вместо « итератор », и нет » аннотация - эта аннотация используется только для того, чтобы пожаловаться, если определение не может быть оптимизировано с помощью хвостовой рекурсии - поэтому вам нужно удалить « @tailrec », а также « import scala .annotation.tailrec "из кода.
Также несколько соображений по альтернативным реализациям. Самый простой:
scala> time(println(1 to 9999999 reduceLeft (_+_)))
-2014260032
640.0 msecs
В среднем при нескольких запусках здесь он медленнее. Это тоже неверно, потому что работает только с Int. Правильный:
scala> time(println((1 to 9999999 foldLeft 0L)(_+_)))
49999995000000
797.0 msecs
Здесь работает еще медленнее. Честно говоря, я не ожидал, что он будет работать медленнее, но каждое взаимодействие вызывает передаваемую функцию. Если учесть это, то это довольно хорошее время по сравнению с рекурсивной версией.
аннотация - эта аннотация используется только для того, чтобы пожаловаться, если определение не может быть оптимизировано с помощью хвостовой рекурсии - поэтому вам нужно удалить « @tailrec », а также « import scala .annotation.tailrec "из кода.
Также несколько соображений по альтернативным реализациям. Самый простой:
scala> time(println(1 to 9999999 reduceLeft (_+_)))
-2014260032
640.0 msecs
В среднем при нескольких запусках здесь он медленнее. Это тоже неверно, потому что работает только с Int. Правильный:
scala> time(println((1 to 9999999 foldLeft 0L)(_+_)))
49999995000000
797.0 msecs
Здесь работает еще медленнее. Честно говоря, я не ожидал, что он будет работать медленнее, но каждое взаимодействие вызывает передаваемую функцию. Если учесть это, то это довольно хорошее время по сравнению с рекурсивной версией.
а также " import scala.annotation.tailrec " из кода.
Кроме того, некоторые соображения по альтернативным реализациям. Самый простой:
scala> time(println(1 to 9999999 reduceLeft (_+_)))
-2014260032
640.0 msecs
В среднем при нескольких запусках здесь он медленнее. Это тоже неверно, потому что работает только с Int. Правильный:
scala> time(println((1 to 9999999 foldLeft 0L)(_+_)))
49999995000000
797.0 msecs
Здесь работает еще медленнее. Честно говоря, я не ожидал, что он будет работать медленнее, но каждое взаимодействие вызывает передаваемую функцию. Если учесть это, то это довольно хорошее время по сравнению с рекурсивной версией.
а также " import scala.annotation.tailrec " из кода.
Кроме того, некоторые соображения по альтернативным реализациям. Самый простой:
scala> time(println(1 to 9999999 reduceLeft (_+_)))
-2014260032
640.0 msecs
В среднем при нескольких запусках здесь он медленнее. Это тоже неверно, потому что работает только с Int. Правильный:
scala> time(println((1 to 9999999 foldLeft 0L)(_+_)))
49999995000000
797.0 msecs
Здесь работает еще медленнее. Честно говоря, я не ожидал, что он будет работать медленнее, но каждое взаимодействие вызывает передаваемую функцию. Если учесть это, то это довольно хорошее время по сравнению с рекурсивной версией.
еще медленнее, бегу сюда. Честно говоря, я не ожидал, что он будет работать медленнее, но каждое взаимодействие вызывает передаваемую функцию. Если учесть это, то это довольно хорошее время по сравнению с рекурсивной версией. еще медленнее, бегу сюда. Честно говоря, я не ожидал, что он будет работать медленнее, но каждое взаимодействие вызывает передаваемую функцию. Если учесть это, то это довольно хорошее время по сравнению с рекурсивной версией.Диапазон Clojure не запоминает, а Scala's Stream. Абсолютно разные структуры данных с совершенно разными результатами. Scala имеет не запоминающуюся структуру Range, но в настоящее время неудобно работать с этим простым рекурсивным способом. Вот мой взгляд на все это.
Используя Clojure 1.0 на старом ящике, который работает медленно, я получаю 3,6 секунды.
user=> (defn sum [coll acc] (if (empty? coll) acc (recur (rest coll) (+ (first coll) acc))))
#'user/sum
user=> (time (sum (range 1 9999999) 0))
"Elapsed time: 3651.751139 msecs"
49999985000001
Для буквального перевода в Scala требуется написать код
def time[T](x : => T) = {
val start = System.nanoTime : Double
val result = x
val duration = (System.nanoTime : Double) - start
println("Elapsed time " + duration / 1000000.0 + " msecs")
result
}
Это хорошо чтобы убедиться, что это правильно
scala> time (Thread sleep 1000)
Elapsed time 1000.277967 msecs
Теперь нам нужен немемозированный Range с семантикой, аналогичной Clojure
case class MyRange(start : Int, end : Int) {
def isEmpty = start >= end
def first = if (!isEmpty) start else error("empty range")
def rest = new MyRange(start + 1, end)
}
Из этого «add» следует непосредственно
def add(a: MyRange, b: Long): Long = {
if (a.isEmpty) b else add(a.rest, b + a.first)
}
И это в разы быстрее, чем у Clojure на одном и том же боксе.
scala> time(add(MyRange(1, 9999999), 0))
Elapsed time 252.526784 msecs
res1: Long = 49999985000001
Используя стандартную библиотеку Scala Range, вы можете сделать фолд. Это не так быстро, как простая примитивная рекурсия, но она меньше кода и все же быстрее, чем рекурсивная версия Clojure (по крайней мере, на моем компьютере).
scala> time((1 until 9999999 foldLeft 0L)(_ + _))
Elapsed time 1995.566127 msecs
res2: Long = 49999985000001
Контраст со складкой над запоминающимся потоком
time((Stream from 1 take 9999998 foldLeft 0L)(_ + _))
Elapsed time 3879.991318 msecs
res3: Long = 49999985000001
Профилировали этот ваш пример, и кажется, что класс Stream (ну ... какая-то анонимная функция, связанная с ним - забыл свое имя, так как visualvm обрушился на меня) занимает большую часть кучи. Это связано с тем, что у Stream в Scala есть утечка памяти - см. Scala Trac # 692 . Исправления в Scala 2.8. . РЕДАКТИРОВАТЬ: Комментарий Даниэля справедливо указал, что он не связан с этой ошибкой. Это потому, что «val ints указывает на заголовок потока, сборщик мусора не может ничего собирать» [ Даниэль ]. Тем не менее, я нашел, что комментарии в этом сообщении об ошибке приятно читать в связи с этим вопросом.
В вашей функции добавления вы держите ссылку на a.head, поэтому сборщик мусора не может собрать заголовок, что приводит к потоку, который содержит 9999998 элементов в конце, который не может быть GC-ed.
[Небольшая интерлюдия]
Вы можете также хранить копии хвостов, которые вы продолжаете проходить, я не уверен, как с этим справляются Stream. Если бы вы использовали список, хвосты не были бы скопированы . Например:
val xs = List(1,2,3)
val ys = 1 :: xs
val zs = 2 :: xs
Здесь и ys, и zs «разделяют» один и тот же хвост, по крайней мере, в куче (ys.tail eq zs.tail, то есть эталонное равенство приводит к true).
[Эта небольшая интерлюдия состояла в том, чтобы показать, что прохождение большого количества хвостов в принципе не является плохой вещью :), они не копируются, по крайней мере, для списков]
Альтернатива реализация (которая работает довольно быстро, и я думаю, что она более понятна, чем чисто функциональная) заключается в использовании императивного подхода:
def addTo(n: Int, init: Int): Long = {
var sum = init.toLong
for(i <- 1 to n) sum += i
sum
}
scala> addTo(9999998, 0)
В Scala вполне нормально использовать императивный подход для повышения производительности. и ясность (по крайней мере для меня, эта версия add более ясна для ее намерения). Для еще большей краткости вы можете написать
(1 to 9999998).reduceLeft(_ + _)
(работает немного медленнее, но все же разумно и не взрывает память)
Я считаю, что Clojure может быть быстрее он полностью функционален, поэтому возможна большая оптимизация, чем в Scala (которая сочетает в себе функциональность, OO и императив). Я не очень знаком с Clojure, хотя.
Надеюсь, это поможет:)
Я подозреваю, что это связано с тем, как Clojure обрабатывает хвостовые оптимизации. Поскольку JVM изначально не выполняет эту оптимизацию (и на ней работают и Clojure, и Scala), Clojure оптимизирует хвостовую рекурсию с помощью ключевого слова recur . С сайта Clojure :
В функциональных языках циклы и итерация заменяется / реализуется через рекурсивные вызовы функций. Многие такие языки гарантируют эту функцию звонки, сделанные в хвостовой позиции, не потребляют пространство стека и, таким образом, рекурсивные циклы используют константу пространство. Поскольку Clojure использует Java соглашения о вызовах, это не может, и нет, сделать тот же хвостовой зов гарантии оптимизации. Вместо этого предоставляет специальный оператор recur, который делает рекурсивный в постоянном пространстве цикл путем повторного связывания и перехода к ближайший охватывающий цикл или функция Рамка. Хотя не такой общий, как оптимизация хвостового вызова, это позволяет большинству тех же элегантных конструкций, и предлагает преимущество проверки того, что повторные вызовы могут происходить только в положение хвоста.
РЕДАКТИРОВАТЬ: Scala также оптимизирует хвостовые вызовы , если они имеют определенную форму. Однако, как показывает предыдущая ссылка, Scala может делать это только для очень простых случаев:
Фактически, это особенность компилятора Scala, называемая оптимизацией хвостового вызова. Это оптимизирует рекурсивный вызов. Эта функция работает только в простых случаях, как указано выше, хотя. Если рекурсия косвенная, например, Scala не может оптимизировать хвостовые вызовы, из-за ограниченного набора инструкций JVM.
Без фактической компиляции и декомпиляции вашего кода, чтобы увидеть, какие инструкции JVM создаются, я подозреваю, что это не один из тех простых случаев (как выразился Майкл, из-за необходимости извлечения a.tail на каждом рекурсивном шаге), и поэтому Scala просто не может его оптимизировать.