Почему решение constant () более эффективно, чем простое в «FP in Scala» 5.8? - PullRequest
Новая
       36

Почему решение constant () более эффективно, чем простое в «FP in Scala» 5.8?

0 голосов
/ 04 января 2019

Я смотрю на упражнение 5.8 в книге "FP in Scala" и задаю вопрос:

"Немного обобщить константу функции, которая возвращает бесконечный поток заданного значения." 

def constant[A](a: A): Stream[A]

Мое решение: 

def constant[A](a: A): Stream[A] =
  Stream.cons(a, constant(a))

пока я ссылаюсь на стандартное решение, оно было: 

// This is more efficient than `cons(a, constant(a))` since it's just
// one object referencing itself.
def constant[A](a: A): Stream[A] = {
  lazy val tail: Stream[A] = Cons(() => a, () => tail) 
  tail
}

, который говорит "более эффективный", см. здесь .

Могу ли я узнать, почему это более эффективно? AFAIK, конструктор cons в Streams уже помечает голову и хвост как ленивый: 

def cons[A](hd: => A, tl: => Stream[A]): Stream[A] = { 
  lazy val head = hd 
  lazy val tail = tl 
  Cons(() => head, () => tail) 
}

Почему мы все еще должны пометить хвост снова как ленивый? Я не совсем понимаю суть здесь.

Ответы [ 2 ]

0 голосов
/ 05 января 2019

Это скорее комментарий к ответу @ElBaulP, чем ответ в своем собственном праве, но он слишком велик для комментария.

Я думаю, что вы пропустили корень оптимизации, хотя это явно указано в комментарии выше. Тот факт, что val tail в constant равен lazy, является деталью реализации или, скорее, уловкой, делающей возможным основной источник оптимизации. И основным источником оптимизации является тот факт, что tail является самоссылочным.

На минутку давайте избавимся от всех вещей lazy. Предположим, что Cons определяется как 

case class Cons[+A](h: A, t: () => Stream[A]) extends Stream[A]

и давайте определим constant как 

def constant[A](a: A): Stream[A] = {
   val tailFunc: () => Stream[A] =  () => tail
   val tail: Stream[A] = Cons(a, tailFunc)
   tail
}

Да, это синтаксически неверная программа, потому что tailFunc использует tail, определенный только в следующей строке. Но представьте, что Scala может это скомпилировать. Теперь я думаю, что совершенно ясно, что такая реализация constant будет создавать только один экземпляр класса Cons на вызов, и этот экземпляр будет использоваться независимо от того, как долго вы пытаетесь перебрать возвращаемый поток.

Что определяет tail как lazy, так это просто сделать код логически эквивалентным вышеупомянутому, скомпилированному без ошибок. С точки зрения реализации это похоже на что-то подобное: 

class Lazy[A](var value:A)

def constant[A](a: A): Stream[A] = {
   val lazyTail: Lazy[Stream[A]] = new Lazy(null)
   // this tailFunc works because lazyTail is already fixed and can be safely 
   // captured although lazyTail.value will be changed
   val tailFunc: () => Stream[A] =  () => lazyTail.value 
   lazyTail.value = new Stream(a, tailFunc)
   lazyTail.value
}

Этот код не совсем совпадает с фактической реализацией lazy во многих деталях, потому что он на самом деле нетерпелив, но я думаю, что это показывает, что вам действительно не нужно lazy, чтобы заставить оптимизацию работать (но за счет использования var, что в любом случае делает компилятор Scala в своей реальной, более сложной lazy реализации).

В вашей наивной реализации 

def constant[A](a: A): Stream[A] =  Stream.cons(a, constant(a))

ленивая оценка tail позволяет вам сразу не завершиться с переполнением стека из-за рекурсивных вызовов constant из самого себя. Но все же, когда вы делаете constant(whatever).tail, tail оценивается, поэтому метод constant вызывается еще раз и создается новый объект Cons. И это будет происходить каждый раз, когда tail вызывается на новый head.

Чтобы переформулировать его еще раз, lazy val tail - это просто уловка, позволяющая tail ссылаться на себя при создании, и действительно важной частью является тот факт, что tail ссылается на себя, что позволяет использовать только один объект для итерация, а не один объект на каждый следующий .tail вызов.

0 голосов
/ 04 января 2019

Я думаю, это потому, что в ленивой реализации вы создаете объект только один раз и запоминаете его, поэтому, когда вы вызываете constant, вы обращаетесь к одному и тому же объекту снова и снова примерно так: 

tail -----
  ^------'

С вашей реализацией (то же самое я встречал, читая книгу), вы создаете новые объекты каждый раз, когда вызываете функцию. Поэтому, если вы несколько раз вызываете свою реализацию, вы получите: 

Stream.cons(a, Stream.cons(a, Stream.cons(a, constant(a))))

Давайте посмотрим на примере: 

def constant[A](a: A): Stream[A] = { println("CALLED"); cons(a, constant(a)) }

// This is more efficient than `cons(a, constant(a))` since it's just
// one object referencing itself.
def constant_1[A](a: A): Stream[A] = {
   lazy val tail: Stream[A] = Cons(() ⇒ a, () ⇒ tail)
   println("CALLED_1")
   tail
  }

println(s"Cons ${Stream.constant_1(0).take(10).toListFast}")
println(s"Cons ${Stream.constant(0).take(10).toListFast}")

Выше кода выдает следующий вывод: 

CALLED_1
Cons List(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
CALLED
CALLED
CALLED
CALLED
CALLED
CALLED
CALLED
CALLED
CALLED
CALLED
Cons List(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

Как видите, оператор println отложенной реализации вызывается только один раз.

Вы можете увидеть @SergGr для подробного объяснения.

...