Вопросы относительно синтаксиса scala в следующем программном решении Dynami c взяты из leetcode - PullRequest
Новая
       91

Вопросы относительно синтаксиса scala в следующем программном решении Dynami c взяты из leetcode

0 голосов
/ 27 мая 2020

Фрагмент кода взят из здесь : 

object Solution {
    def numSquares(n: Int): Int = {
    def memoize[I, O](f: I => O): I => O = new scala.collection.mutable.HashMap[I, O]() {
      override def apply(key: I): O = getOrElseUpdate(key, f(key))
    }

    lazy val numSq: Int => Int = memoize {
      case 0 => 0
      case x => Range(math.sqrt(x).toInt, 1, -1).foldLeft(x)((a , b) => math.min(numSq(x - b * b) + 1, a))    
    }
    numSq(n)
  }
}

Поскольку numSq использует изменяемую HashMap, правильно ли говорить, что numSq является изменяемой функцией?

Обычно при использовании нисходящего подхода в dp это обычно вызывает переполнение стека для больших входных данных, но здесь кажется, что он работает нормально даже для некоторых больших входных данных. Это из-за использования lazy val в определении numSq?

1 Ответ

1 голос
/ 28 мая 2020

... правильно ли говорить, что numSq является изменяемой функцией?

Как отметил @gregghz в комментариях, «изменяемая функция» не является общепринятой терминологией . Это правда, что HashMap находится в разном состоянии при каждом рекурсивном вызове, но это фактически невидимо для вызывающего.

... кажется, он отлично работает даже для некоторых больших входов. Это из-за использования lazy val в определении numSq?

No.

Переменная numSq объявлена ​​lazy, чтобы разрешить полученную функцию рекурсивный. Без части lazy компилятор жалуется на недопустимую прямую ссылку. 

Error: forward reference extends over definition of value numSq

numSq может обрабатывать большие входные числа, потому что мемоизация (память того, что уже было вычислено) уменьшает количество рекурсий требуется для вычисления следующего результата.

Обратите внимание, что вы можете получить StackOverflow, просто изменив направление Range: 

Range(2, math.sqrt(x).toInt + 1)...

Начав с малых чисел и увеличивая, HashMap не будет содержать достаточно элементов, чтобы в достаточной степени уменьшить рекурсию, требуемую по мере роста чисел.

...