Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

Elixir の Agent で計算を高速化

More than 3 years have passed since last update.

やりたいこと

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 項を計算する。

コード

  • 普通に書くとこんな感じ。
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
  • メモ化するとこんな感じ。
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

結果

速さがぜんぜん違う。

  • 普通に書いた方
$ time elixir fib_normal.exs
102334155
elixir fib_normal.exs  5.28s user 0.31s system 100% cpu 5.560 total

5.28s かかってる。

  • Agent でメモ化した方
$ 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)で試す。

コード

  • 普通に書くとこんな感じ。
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
  • メモ化でこうなる。
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 かかった。
$ time elixir tarai_normal.exs
14
elixir tarai_normal.exs  7.96s user 0.54s system 98% cpu 8.597 total
  • メモ化した方、0.35s だけで済んだ。
$ time elixir tarai_memorize.exs
14
elixir tarai_memorize.exs  0.35s user 0.16s system 103% cpu 0.489 total

ちなみに

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

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

0.58s しかかかってない。

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

まとめ

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

参考文献

t-manome
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away