Elixirで竹内関数を計測してみた

この記事は Elixir Advent Calendar 2020 19日目の記事です。

昨日は @zacky1972さんでElixirで速度を追い求めるときのプログラミングスタイルでした。

---

竹内関数

竹内関数はベンチマークに使われる再帰的に定義された関数です。
下記のように定義されているので、たらい回し関数とも呼ばれています。

tarai(x,y,z) =
\left\{
\begin{array}{lll}
y & \textrm{if} & x \leq y\\
tarai(tarai(x-1,y,z), tarai(y-1,z,x), tarai(z-1,x,y)) & \textrm{else} & 
\end{array}
\right.

Elixirで実装

定義通りにに実装しました。

defmodule Takeuchi do
  def tarai(x,y,_) when x <= y do
    y
  end
  def tarai(x, y, z) do
    tarai(tarai(x-1,y,z), tarai(y-1,z,x), tarai(z-1,x, y))
  end
end

動的計画法を使う問題をElixirで関数型っぽく解いてみるで知った:timer.tcを使って計測してみました。

iex(1)> :timer.tc(Takeuchi, :tarai, [10,5,0])
{15000, 10}
iex(2)> :timer.tc(Takeuchi, :tarai, [12,6,0])
{156000, 12}
iex(3)> :timer.tc(Takeuchi, :tarai, [14,7,0])
{7234000, 14}
iex(4)> :timer.tc(Takeuchi, :tarai, [16,8,0])
{503249780, 16}
iex(5)> :timer.tc(Takeuchi, :tarai, [18,9,0])
{29903428454, 18}

---

時間がかかるということは知っていたんですが、実際に実行して見ると予想以上でした。

明日20日目のElixir Advent Calendar 2020は @sanpo_shiho さんのPhoenix現代アーキテクチャ入門です。よろしくお願いします。