Elixir の Agent で計算を高速化


# やりたいこと

Elixir の Agent を使ってメモ化再帰を実装してその効果を見たい。
フィボナッチ数列とたらい回し関数で試す。 
ちなみに Agent の使い方あってるかわからない。

# 環境

-   MacBook Pro (Retina, 13-inch, Early 2015)
    -   Processor: 2.7GHz Intel Core i5
    -   Memory: 16GB 1867 MHz DDR3
-   elixir 1.4.2

# フィボナッチで試す

フィボナッチ数列の計算を行う。 今回は第 40 項を計算する。

## コード

- 普通に書くとこんな感じ。

```elixir:fib_normal.exs
defmodule Fib do
  def fib(0), do: 0
  def fib(1), do: 1
  def fib(n), do: fib(n - 1) + fib(n - 2)
end

Fib.fib(40)
|> IO.inspect
```

- メモ化するとこんな感じ。

```elixir:fib_memorize.exs
defmodule Memorize do
  def fib(0), do: 0
  def fib(1), do: 1
  def fib x do
    case Agent.get(__MODULE__, &Map.get(&1, x)) do
      nil ->
        f = fib(x - 1) + fib(x - 2)
        Agent.update(__MODULE__, &Map.put(&1, x, f))
        f
      f -> f
    end
  end

  def start_agent do
    Agent.start_link &Map.new/0, name: __MODULE__
  end
end

Memorize.start_agent
Memorize.fib(40)
|> IO.inspect
```

## 結果

速さがぜんぜん違う。

- 普通に書いた方

```console
$ time elixir fib_normal.exs
102334155
elixir fib_normal.exs  5.28s user 0.31s system 100% cpu 5.560 total
```

5.28s かかってる。

- Agent でメモ化した方

```console
$ time elixir fib_memorize.exs
102334155
elixir fib_memorize.exs  0.35s user 0.16s system 104% cpu 0.487 total
```

0.35s。一瞬。

# たらい回し関数で試す

たらい回し関数(竹内関数)でも試してみる。
 今回は tarai(14, 7, 0)で試す。

## コード

- 普通に書くとこんな感じ。

```elixir:tarai_normal.exs
defmodule Tarai do
  def tarai(x, y, z) do
    cond do
      x <= y -> y
      true -> tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y))
    end
  end
end

Tarai.tarai(14, 7, 0)
|> IO.inspect
```

- メモ化でこうなる。

```elixir:tarai_memorize.exs
defmodule Tarai do
  def tarai(x, y, z) do
    cond do
      x <= y -> y
      true ->
        case Agent.get(:tarai, &Map.get(&1, [x, y, z])) do
          nil ->
            ret = tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y))
            Agent.update(:tarai, &Map.put(&1, [x, y, z], ret))
            ret
          ret -> ret
        end
    end
  end

  def start_agent do
    Agent.start_link &Map.new/0, name: :tarai
  end
end

Tarai.start_agent
Tarai.tarai(14, 7, 0)
|> IO.inspect

```

## 結果

- 普通の方、7.96s かかった。

```console
$ time elixir tarai_normal.exs
14
elixir tarai_normal.exs  7.96s user 0.54s system 98% cpu 8.597 total
```

- メモ化した方、0.35s だけで済んだ。

```console
$ time elixir tarai_memorize.exs
14
elixir tarai_memorize.exs  0.35s user 0.16s system 103% cpu 0.489 total
```

# ちなみに

フィボナッチの 20000 項目を計算してもこの速さ。

```console
$ time elixir fib_memorize.exs
2531162323732361242240155003520607291766356485802485278951929841991312781760541315230153423463758831637443488219211037689033673531462742885329724071555187618026931630449193158922771331642302030331971098689235780843478258502779200293635651897483309686042860996364443514558772156043691404155819572984971754278513112487985892718229593329483578531419148805380281624260900362993556916638613939977074685016188258584312329139526393558096840812970422952418558991855772306882442574855589237165219912238201311184749075137322987656049866305366913734924425822681338966507463855180236283582409861199212323835947891143765414913345008456022009455704210891637791911265475167769704477334859109822590053774932978465651023851447920601310106288957894301592502061560528131203072778677491443420921822590709910448617329156135355464620891788459566081572824889514296350670950824208245170667601726417091127999999941149913010424532046881958285409468463211897582215075436515584016297874572183907949257286261608612401379639484713101138120404671732190451327881433201025184027541696124114463488665359385870910331476156665889459832092710304159637019707297988417848767011085425271875588008671422491434005115288334343837778792282383576736341414410248994081564830202363820504190074504566612515965134665683289356188727549463732830075811851574961558669278847363279870595320099844676879457196432535973357128305390290471349480258751812890314779723508104229525161740643984423978659638233074463100366500571977234508464710078102581304823235436518145074482824812996511614161933313389889630935320139507075992100561077534028207257574257706278201308302642634678112591091843082665721697117838726431766741158743554298864560993255547608496686850185804659790217122426535133253371422250684486113457341827911625517128815447325958547912113242367201990672230681308819195941016156001961954700241576553750737681552256845421159386858399433450045903975167084252876848848085910156941603293424067793097271128806817514906531652407763118308162377033463203514657531210413149191213595455280387631030665594589183601575340027172997222489081631144728873621805528648768511368948639522975539046995395707688938978847084621586473529546678958226255042389998718141303055036060772003887773038422366913820397748550793178167220193346017430024134496141145991896227741842515718997898627269918236920453493946658273870473264523119133765447653295022886429174942653014656521909469613184983671431465934965489425515981067546087342348350724207583544436107294087637975025147846254526938442435644928231027868701394819091132912397475713787593612758364812687556725146456646878912169274219209708166678668152184941578590201953144030519381922273252666652671717526318606676754556170379350956342095455612780202199922615392785572481747913435560866995432578680971243966868110016581395696310922519803685837460795358384618017215468122880442252343684547233668502313239328352671318130604247460452134121833305284398726438573787798499612760939462427922917659263046333084007208056631996856315539698234022953452211505675629153637867252695056925345220084020071611220575700841268302638995272842160994219632684575364180160991884885091858259996299627148614456696661412745040519981575543804847463997422326563897043803732970397488471644906183310144691243649149542394691524972023935190633672827306116525712882959108434211652465621144702015336657459532134026915214509960877430595844287585350290234547564574848753110281101545931547225811763441710217452979668178025286460158324658852904105792472468108996135476637212057508192176910900422826969523438985332067597093454021924077101784215936539638808624420121459718286059401823614213214326004270471752802725625810953787713898846144256909835116371235019527013180204030167601567064268573820697948868982630904164685161783088076506964317303709708574052747204405282785965604677674192569851918643651835755242670293612851920696732320545562286110332140065912751551110134916256237884844001366366654055079721985816714803952429301558096968202261698837096090377863017797020488044826628817462866854321356787305635653577619877987998113667928954840972022833505708587561902023411398915823487627297968947621416912816367516125096563705174220460639857683971213093125
elixir fib.exs  0.58s user 0.24s system 96% cpu 0.849 total
```

0.58s しかかかってない。

普通に書いた方は全然終わらないのでやめた。

# まとめ

メモ化すると計算速度が目に見えて変わる。
 すごい。

# 参考文献
- [ElixirのAgentモジュールを使って値の更新とかメモ化とか - BlankTar](http://blanktar.jp/blog/2016/06/elixir-memorize-fibonacci.html)
- [竹内関数 - Wikipedia](https://ja.wikipedia.org/wiki/%E7%AB%B9%E5%86%85%E9%96%A2%E6%95%B0)