时间戳

首页 > 解决方案 > 斐波那契与记忆长生不老药

functional-programming - 斐波那契与记忆长生不老药

问题描述

我正在研究函数式编程，并在长生不老药中做了一个简单的斐波那契。

我知道在函数式编程中不可能改变值，我编写了一个代码来制作带有记忆的斐波那契，但代码很糟糕。如何改进此代码？

defmodule Fib do
  def fib_memoized(0, memo) do
    {0, memo}
  end

  def fib_memoized(1, memo) do
    {1, memo}
  end

  def fib_memoized(n, memo \\ %{}) do
    if Map.has_key?(memo, n) do
      { memo[n], memo }
    else
      {n1, memo1} = fib_memoized(n-1, memo)
      {n2, memo2} = fib_memoized(n-2, memo1)

      value = n1+n2

      {value, Map.merge(memo2, %{n => value})}
    end
  end

  def fib(n) do
    { value, _ } = fib_memoized(n)
    value 
  end
end

IO.puts Fib.fib(1000)

在javascript中可以创建一个高阶函数并保存“地图”并更新这个。

前任：

function memoization(fn) {
    let memo = {}
    return function (n) {
      if(!memo[n]) {
        memo[n] = fn(n)
      }
      return memo[n]
    }
  }

有可能做出类似的东西吗？

标签： functional-programmingelixirfibonaccimemoization

解决方案

通常，当我必须在 elixir 中存储状态时，我会启动一个流程来执行此操作。在斐波那契案例中，an 非常Agent适合。

可以这样写：

defmodule Fib do
  use Agent

  def start do
    Agent.start_link(fn -> %{0 => 0, 1 => 1} end, name: __MODULE__)
  end

  def fib(n) do
    cached_value = Agent.get(__MODULE__, &(Map.get(&1, n)))

    if cached_value do
      cached_value
    else
      v = fib(n - 1) + fib(n - 2)
      Agent.update(__MODULE__, &(Map.put(&1, n, v)))
      v
    end
  end
end

{:ok, _} = Fib.start
IO.puts Fib.fib(1000)

推荐阅读