Рекурсивные методы для создания потоков в Scala - PullRequest
Новая
       17

Рекурсивные методы для создания потоков в Scala

5 голосов
/ 03 января 2012

Это продолжение моего предыдущего вопроса .

Как я понимаю , следующий метод вычисления чисел Фибоначчи неэффективен, поскольку метод fib вызывается для каждого числа Фибоначчи и каждый раз, когда он вызывается, создает новый поток. 

def fib:Stream[Int] =
  Stream.cons(1, Stream.cons(1, (fib zip fib.tail) map {case (x, y) => x + y}))

С другой стороны, метод хвостовой рекурсии (как в здесь ) выглядит довольно эффективным и вычисляет каждое число Фибоначчи в O(1)

def fib(a:Int, b:Int):Stream[Int] = Stream.cons(a, fib(b, a+b));

Теперь я заключаю, что рекурсивные методы, которые создают потоки, эффективны тогда и только тогда, когда они являются хвостовыми рекурсивными. Это правильно?

Ответы [ 2 ]

7 голосов
/ 03 января 2012

Нет, хвостовая рекурсия предназначена для того, чтобы помочь циклу компиляции вместо стеков (глобально), это оптимизация времени компиляции.

Проблема возникла в первой реализации, когда несколько вызовов fib приводят к нескольким конструкциям Stream, поэтому одно и то же исчисление выполняется снова и снова. 

fib zip fib.tail
//if we are at the 1000, it will compute million Streams

Если вы хотите увидеть это, попробуйте следующее 

var i = 0
def fib:Stream[Int] = {
  i = i + 1
  println("new Stream : " + i)
  Stream.cons(1, Stream.cons(1, (fib zip fib.tail) map {case (x, y) => x + y}))
}
4 голосов
/ 04 января 2012

Я пытался улучшить Энди ответ , но он в значительной степени прибил его.Первое решение - это создание пирамиды потоков - каждый вызов fib создает еще один поток Фибоначчи, и каждый из этих новых потоков сам создаст новый поток и т. Д.

Чтобы быть понятным, есть три потока в результате вызова к fib:

  • Один создан fib в fib zip fib.tail
  • Один созданfib.tail в fib zip fib.tail
  • Созданный map (помните, map создает новую коллекцию)

Поскольку первые два вызова fibони будут создавать по три потока каждый и т. д.

Вот примерная «картина» этого: 

                          1
                          1
          1               2               1
          1               3       1       2       1
    1     2       1       5       1       3   1   2   1
    1     3   1   2   1   8   1   2   1   5   1   3 1 2 1

И это продолжается и продолжается.Средний поток вычисляется с использованием самых высоких потоков слева и справа (fib и fib.tail).Каждый из них вычисляется с использованием нижних потоков на их влево и вправо.Каждый из этих более низких потоков вычисляется с использованием потоков, показанных в последней строке.

Мы могли бы продолжать это снова и снова, но вы можете видеть, что к тому времени, как мы вычислили 8, у нас уже есть 14 других потоков Фибоначчи

Если вы измените его с def на val, все эти новые потоки исчезнут, потому что fib и fib.tail будут ссылаться на существующий поток вместо созданияновые потоки.И поскольку новый поток не будет создан, больше не будет звонков на fib и fib.tail.

Теперь, если вы посмотрите на второй ответ, вы заметите, что есть один fib вызов, а не map или подобный метод, поэтому эффект умножения отсутствует.

...