Фибоначчи с эликсиром воспоминания - PullRequest
Новая
       42

Фибоначчи с эликсиром воспоминания

0 голосов
/ 01 мая 2018

Я изучаю функциональное программирование, и я сделал простой фибоначчи в эликсире.

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

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 можно сделать функцию высокого порядка, сохранить «карту» и обновить эту.

Ex: 

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

Можно ли сделать что-то подобное?

Ответы [ 2 ]

0 голосов
/ 01 мая 2018

Дословный перевод фрагмента, который вы опубликовали в JS, на Elixir будет выглядеть примерно так: 

memoization = fn fun ->
  fn n, acc ->
    acc =
      if(!acc[n]) do
        Process.sleep(1_000)
        IO.inspect acc, label: "Just put... Need a rest... Sleeping... Zzzz..."
        Map.put(acc, n, fun.(n))
      else
        acc
      end
    {acc, Map.get(acc, n)}
  end
end

fun = memoization.(& &1 * 2)
{acc, _} = IO.inspect fun.(42, %{}), label: "Result for 42"
{acc, _} = IO.inspect fun.(42, acc), label: "Result for 42"
{acc, _} = IO.inspect fun.(3.14, acc), label: "Result for 3.14"
{_, _} = IO.inspect fun.(3.14, acc), label: "Result for 3.14"

В результате: 

# Just put... Need a rest... Sleeping... Zzzz...: %{}
# Result for 42: {%{42 => 84}, 84}
# Result for 42: {%{42 => 84}, 84}
# Just put... Need a rest... Sleeping... Zzzz...: %{42 => 84}
# Result for 3.14: {%{42 => 84, 3.14 => 6.28}, 6.28}
# Result for 3.14: {%{42 => 84, 3.14 => 6.28}, 6.28}

Необходимо пропустить аккумулятор, так как в Elixir нет глобального состояния. Ой, подождите, на самом деле есть!

Я написал подробный пост в блоге о том, как запоминать функции в Elixir с примером и готовым к использованию кодом.

0 голосов
/ 01 мая 2018

Обычно, когда мне нужно сохранить состояние в эликсире, я запускаю процесс, чтобы сделать это. В случае Фибоначчи 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)
...