Память Фибоначчи в Scala с Memo.mutableHashMapMemo - PullRequest
Новая
       55

Память Фибоначчи в Scala с Memo.mutableHashMapMemo

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

Я пытаюсь реализовать функцию Фибоначчи в Scala с мемоизацией

В одном из приведенных здесь примеров используется выражение case: Существует ли универсальный способ мемоизации в Scala? 

import scalaz.Memo
lazy val fib: Int => BigInt = Memo.mutableHashMapMemo {
  case 0 => 0
  case 1 => 1
  case n => fib(n-2) + fib(n-1)
}

Кажется, переменная n неявно определена как первый аргумент, но я получаю ошибку компиляции, если я заменяю n на _

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

Однако я хотел обобщить это определение для более общего определения функции с соответствующей типизацией 

import scalaz.Memo
def fibonachi(n: Int) : Int = Memo.mutableHashMapMemo[Int, Int] {
    var value : Int = 0
    if( n <= 1 ) { value = n; }
    else         { value = fibonachi(n-1) + fibonachi(n-2) }
    return value
}

, но я получаюследующая ошибка компиляции 

cmd10.sc:4: type mismatch;
 found   : Int => Int
 required: Int
def fibonachi(n: Int) : Int = Memo.mutableHashMapMemo[Int, Int] {
                                                                         ^Compilation Failed
Compilation Failed

Итак, я пытаюсь понять общий способ добавления добавления заметки-памятки в функцию scala def

Ответы [ 2 ]

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

Более общий вопрос, который я пытаюсь задать, заключается в том, как взять ранее существующую функцию def и добавить изменяемую / неизменяемую аннотацию / обертку памятки в строку.

К сожалению, в Scala нет способа сделать это, если вы не захотите использовать для этого макросовую аннотацию 1007 *, которая кажется мне излишней, или использовать очень уродливый дизайн.,

Противоречивые требования: "def" и "inline".Фундаментальная причина этого заключается в том, что все, что вы делаете в строке с def, не может создать никакого нового места для хранения запомненных значений (если вы не используете макрос, который может переписать код, вводящий новые val / var s).Вы можете попытаться обойти это, используя некоторый глобальный кеш, но это IMHO попадает под ветвь "некрасивый дизайн".

Конструкция ScalaZ Memo используется для создания val типа Function[K,V], который часто пишется в Scala как K => V вместо def.Таким образом, созданный val может также содержать хранилище для кэшированных значений.С другой стороны, синтаксически разница между использованием метода def и функции K => V минимальна, поэтому это работает довольно хорошо.Поскольку компилятор Scala знает, как преобразовать метод def в функцию, вы можете заключить def в Memo, но вы не можете получить def из него.Если по какой-то причине вам все равно понадобится def, вам понадобится еще одна оболочка def. 

import scalaz.Memo

object Fib {

  def fib(n: Int): BigInt = n match {
    case 0 => BigInt(0)
    case 1 => BigInt(1)
    case _ => fib(n - 2) + fib(n - 1)
  }

  // "fib _" converts a method into a function. Sometimes "_" might be omitted 
  // and compiler can imply it but sometimes the compiler needs this explicit hint 
  lazy val fib_mem_val: Int => BigInt = Memo.mutableHashMapMemo(fib _) 

  def fib_mem_def(n: Int): BigInt = fib_mem_val(n)

}

println(Fib.fib(5))
println(Fib.fib_mem_val(5))
println(Fib.fib_mem_def(5))

Обратите внимание, что нет разницы в синтаксисе вызовов fib, fib_mem_val и fib_mem_def хотя fib_mem_val является значением.Вы также можете попробовать этот пример онлайн

Примечание : помните, что некоторые реализации ScalaZ Memo не являются поточно-ориентированными.

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

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

Одним из способов получения последовательности Фибоначчи является рекурсивный Stream. 

val fib: Stream[BigInt] = 0 #:: fib.scan(1:BigInt)(_+_)

Интересный аспект потоков состоит в том, что, если что-то держится за начало потока, результаты вычисленийавто-memoized.Таким образом, в этом случае, поскольку идентификатор fib представляет собой val, а не def, значение fib(n) вычисляется только один раз и затем просто получается.

Однако индексирование a Stream по-прежнему линейная операция.Если вы хотите запомнить это, вы можете создать простую оболочку для заметок. 

def memo[A,R](f: A=>R): A=>R =
  new collection.mutable.WeakHashMap[A,R] {
    override def apply(a: A) = getOrElseUpdate(a,f(a))
  }

val fib: Stream[BigInt] = 0 #:: fib.scan(1:BigInt)(_+_)
val mfib = memo(fib)
mfib(99)  //res0: BigInt = 218922995834555169026
...