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現代アーキテクチャ入門です。よろしくお願いします。
Author And Source
この問題について(Elixirで竹内関数を計測してみた), 我々は、より多くの情報をここで見つけました https://qiita.com/a_utsuki/items/23381fff2ac630800bf0著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .