Kotlin 中的递归“装饰器”

Question

假设我有一个像

fibonacci

这样的递归函数：

fun fibonacci(n: Int): BigInteger = 
    if (n < 2) 
        n.toBigInteger() 
    else 
        fibonacci(n-1) + fibonacci(n-2)

这很慢，因为我要多次重新计算已知值。我可以通过添加“备忘录”来解决这个问题：

val memo = ConcurrentSkipListMap<Int, BigInteger>()

fun mFibonacci(n: Int): BigInteger = 
    memo.computeIfAbsent(n) { 
        if (n < 2) 
            it.toBigInteger() 
        else 
            mFibonacci(n-1) + mFibonacci(n-2) 
    }

工作起来就像一个魅力，但我可以在不接触该功能的情况下做到这一点吗？我的第一个想法是使用包装类：

class Cached<in T, out R>(private val f: (T) -> R) : (T) -> R {
    private val cache = ConcurrentSkipListMap<T, R>()
    override fun invoke(x: T): R = cache.computeIfAbsent(x, f)
}

cFibonacci = Cached(::fibonacci)

...但问题是，这只能记住最外层的调用。如果我用像

cFibonacci

这样的“大”数字来调用

42

，则需要很长时间才能将正确的值放入备忘录中；后续使用

42

的调用会很快，但

41

会再次变慢。将此与

mFibonacci

进行比较，后者第一次运行速度很快，并使用从

0

到

42

的值填充备忘录。

在 Python 中，我可以编写一个“装饰器”来执行此操作。

def memoized(f):
    def helper(t):
        if x in helper.memo:
          return helper.memo[t]
        else:
          r = f(t)
          helper.memo[t] = r
          return r
    helper.memo = {}
    return helper

@memoized
def fib(n):
  if n < 2:
    return n
  else:
    return fib(n-1) + fib(n-2)

这就像上面的

mFibonacci

一样工作。如果我从其他地方导入

fib = memoized(fib)

并且无法访问定义，我也可以将其称为

fib

。有趣的是，

c_fib = memoized(fib)

的工作方式类似于上面的

Cached

/

cFibonacci

，暗示函数引用的可变性可能是必要的。

问题是：（如何）我可以像在 Python 中一样，以影响 Kotlin 中内部调用的方式包装/“装饰”递归函数吗？

Answer 1

在没有解决方案的情况下，我会建议一个解决方法。此模式需要访问函数的定义（即它不能是导入）：

object fibonacci: (Int) -> BigInteger {
    private val memo = ConcurrentSkipListMap<Int, BigInteger>()
    override fun invoke(n: Int): BigInteger = fibonacci(n)
    private fun fibonacci(n: Int): BigInteger = memo.computeIfAbsent(n) {
        if (n < 2)
            n.toBigInteger()
        else
            fibonacci(n-1) + fibonacci(n-2)
    }
}

这里几乎没有什么决定可能需要论证：

1. 我使用驼峰命名法而不是帕斯卡命名法。尽管

   object

   是一个类，但它被作为一个函数调用，所以我觉得函数的命名约定更好。这样，您就可以像平常一样调用

   fibonacci

   函数。

2. 我已将

   invoke

   重命名为

   fibonacci

   。如果没有这个，递归调用将使用

   invoke

   ，这对我来说似乎不太可读。这样，您就可以像平常一样读取和写入

   fibonacci

   函数（几乎*）。

总的来说，我们的想法是尽可能减少干扰，同时仍然添加所需的功能。我愿意接受有关如何改进它的建议！

*需要注意的是，该函数是使用lambda语法定义的，所以没有

return

。如果函数末尾只有一个 return，则只需删除

return

关键字即可。如果您有多个回程，则必须使用不太漂亮的

return@computeIfAbsent

来进行短路。

Answer 2

根据要求，这是 @AlexJones 解决方法的变体，它不会使用非常规命名将函数包装在

object

中。我没有对此进行测试——它是基于其他解决方案有效的假设。以下代码位于 .kt 文件的顶层。

private val memo = ConcurrentSkipListMap<Int, BigInteger>()

fun fibonacci(n: Int): BigInteger = fibonacciImpl(n)

private fun fibonacciImpl(n: Int): BigInteger = memo.computeIfAbsent(n) {
    if (n < 2)
        n.toBigInteger()
    else
        fibonacci(n-1) + fibonacci(n-2)
}

Answer 3

Arrow的MemoizedDeepRecursiveFunction提供了一个很好的无堆栈缓存递归解决方案：

import arrow.core.MemoizedDeepRecursiveFunction

val fibonacciWorker = MemoizedDeepRecursiveFunction<Int, Int> { n ->
  when (n) {
    0 -> 0
    1 -> 1
    else -> callRecursive(n - 1) + callRecursive(n - 2)
  }
}