ElixirAdvent Calendar 2024

Elixirでフィボナッチ数列をいろいろ書いてみた Part. 5

Last updated at 2024-12-30Posted at 2024-12-30

@mod_poppoさんのHaskellでフィボナッチ数列〜Haskellで非実用的なコードを書いて悦に入るのはやめろ〜にインスピレーションを得て，Elixirでフィボナッチ数列をいろいろ書いてみるシリーズ記事の第4弾です．

フィボナッチ数列シリーズ

行列のべき乗を使う

\begin{pmatrix}
  F_n \\
  F_{n+1}
\end{pmatrix}
=
\begin{pmatrix}
  0 & 1 \\
  1 & 1
\end{pmatrix}^n
\begin{pmatrix}
  0 \\
  1
\end{pmatrix}

fib_benchee.exs

Mix.install([:benchee])

defmodule Fibonacci.Matrix do
  def of(n) do
    Enum.reduce(1..n, {0, 1}, fn
      _, {p, q} -> {q, p + q}
    end)
    |> elem(0)
  end
end

defmodule Fibonacci.Reduce do
  def of(n) do
    0..n
    |> Enum.reduce([], fn
      _, [] -> [0]
      _, [0] -> [1, 0]
      _, [m, n] -> [m + n, m]
    end)
    |> hd()
  end
end

IO.inspect(Fibonacci.Matrix.of(1500) == Fibonacci.Reduce.of(1500))

Benchee.run(
  %{
    "Fibonacci by Enum.reduce" => fn input -> Enum.reduce(1..100, fn _, _ -> Fibonacci.Reduce.of(input) end) end,
    "Fibonacci with Matrix" => fn input -> Enum.reduce(1..100, fn _, _ -> Fibonacci.Matrix.of(input) end) end
  },
  inputs: %{
    "1" => 1,
    "10" => 10,
    "100" => 100,
    "1000" => 1000
  }
)

実行結果

true
Operating System: macOS
CPU Information: Apple M3 Max
Number of Available Cores: 16
Available memory: 128 GB
Elixir 1.18.1
Erlang 27.2
JIT enabled: true

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
reduction time: 0 ns
parallel: 1
inputs: 1, 10, 100, 1000
Estimated total run time: 56 s

Benchmarking Fibonacci by Enum.reduce with input 1 ...
Benchmarking Fibonacci by Enum.reduce with input 10 ...
Benchmarking Fibonacci by Enum.reduce with input 100 ...
Benchmarking Fibonacci by Enum.reduce with input 1000 ...
Benchmarking Fibonacci with Matrix with input 1 ...
Benchmarking Fibonacci with Matrix with input 10 ...
Benchmarking Fibonacci with Matrix with input 100 ...
Benchmarking Fibonacci with Matrix with input 1000 ...
Calculating statistics...
Formatting results...

##### With input 1 #####
Name                               ips        average  deviation         median         99th %
Fibonacci with Matrix         572.17 K        1.75 μs   ±750.26%        1.63 μs        2.25 μs
Fibonacci by Enum.reduce      475.76 K        2.10 μs   ±520.80%           2 μs        2.88 μs

Comparison: 
Fibonacci with Matrix         572.17 K
Fibonacci by Enum.reduce      475.76 K - 1.20x slower +0.35 μs

##### With input 10 #####
Name                               ips        average  deviation         median         99th %
Fibonacci with Matrix         213.34 K        4.69 μs   ±333.13%        4.38 μs       12.50 μs
Fibonacci by Enum.reduce      194.28 K        5.15 μs   ±148.88%        4.83 μs       13.29 μs

Comparison: 
Fibonacci with Matrix         213.34 K
Fibonacci by Enum.reduce      194.28 K - 1.10x slower +0.46 μs

##### With input 100 #####
Name                               ips        average  deviation         median         99th %
Fibonacci with Matrix          22.02 K       45.41 μs     ±5.32%       45.04 μs       57.29 μs
Fibonacci by Enum.reduce       19.56 K       51.11 μs     ±5.81%       50.92 μs       62.04 μs

Comparison: 
Fibonacci with Matrix          22.02 K
Fibonacci by Enum.reduce       19.56 K - 1.13x slower +5.71 μs

##### With input 1000 #####
Name                               ips        average  deviation         median         99th %
Fibonacci with Matrix           761.80        1.31 ms     ±1.90%        1.31 ms        1.40 ms
Fibonacci by Enum.reduce        754.01        1.33 ms     ±2.85%        1.32 ms        1.44 ms

Comparison: 
Fibonacci with Matrix           761.80
Fibonacci by Enum.reduce        754.01 - 1.01x slower +0.0136 ms

	1	10	100	1000
Fibonacci by Enum.reduce	2010	5150	51110	1330000
Fibonacci with Matrix	1750	4690	45410	1310000

Fibonacci with Matrix は素晴らしく速いですね！

オリジナルのフィボナッチとの比較

fib_benchee.exs

Mix.install([:benchee])

defmodule Fibonacci.Matrix do
  def of(n) do
    Enum.reduce(1..n, {0, 1}, fn
      _, {p, q} -> {q, p + q}
    end)
    |> elem(0)
  end
end

defmodule Fibonacci do
  def of(n)
  def of(0), do: 0
  def of(1), do: 1
  def of(n), do: of(n - 2) + of(n - 1)
end
Benchee.run(
  %{
    "Very Slow Fibonacci" => fn input -> Enum.reduce(1..100, fn _, _ -> Fibonacci.of(input) end) end,
    "Fibonacci with Matrix" => fn input -> Enum.reduce(1..100, fn _, _ -> Fibonacci.Matrix.of(input) end) end
  },
  inputs: %{
    "1" => 1,
    "2" => 2,
    "3" => 3,
    "4" => 4,
    "5" => 5,
    "6" => 6,
    "7" => 7,
    "8" => 8,
    "9" => 9
  }
)

実行結果

Operating System: macOS
CPU Information: Apple M3 Max
Number of Available Cores: 16
Available memory: 128 GB
Elixir 1.18.1
Erlang 27.2
JIT enabled: true

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
reduction time: 0 ns
parallel: 1
inputs: 1, 2, 3, 4, 5, 6, 7, 8, 9
Estimated total run time: 2 min 6 s

Benchmarking Fibonacci with Matrix with input 1 ...
Benchmarking Fibonacci with Matrix with input 2 ...
Benchmarking Fibonacci with Matrix with input 3 ...
Benchmarking Fibonacci with Matrix with input 4 ...
Benchmarking Fibonacci with Matrix with input 5 ...
Benchmarking Fibonacci with Matrix with input 6 ...
Benchmarking Fibonacci with Matrix with input 7 ...
Benchmarking Fibonacci with Matrix with input 8 ...
Benchmarking Fibonacci with Matrix with input 9 ...
Benchmarking Very Slow Fibonacci with input 1 ...
Benchmarking Very Slow Fibonacci with input 2 ...
Benchmarking Very Slow Fibonacci with input 3 ...
Benchmarking Very Slow Fibonacci with input 4 ...
Benchmarking Very Slow Fibonacci with input 5 ...
Benchmarking Very Slow Fibonacci with input 6 ...
Benchmarking Very Slow Fibonacci with input 7 ...
Benchmarking Very Slow Fibonacci with input 8 ...
Benchmarking Very Slow Fibonacci with input 9 ...
Calculating statistics...
Formatting results...

##### With input 1 #####
Name                            ips        average  deviation         median         99th %
Very Slow Fibonacci          1.41 M        0.71 μs  ±1889.67%        0.67 μs        0.92 μs
Fibonacci with Matrix        0.58 M        1.73 μs   ±783.76%        1.58 μs        2.25 μs

Comparison: 
Very Slow Fibonacci          1.41 M
Fibonacci with Matrix        0.58 M - 2.43x slower +1.02 μs

##### With input 2 #####
Name                            ips        average  deviation         median         99th %
Very Slow Fibonacci        931.45 K        1.07 μs  ±1252.44%           1 μs        1.38 μs
Fibonacci with Matrix      495.09 K        2.02 μs   ±419.01%        1.92 μs        2.75 μs

Comparison: 
Very Slow Fibonacci        931.45 K
Fibonacci with Matrix      495.09 K - 1.88x slower +0.95 μs

##### With input 3 #####
Name                            ips        average  deviation         median         99th %
Very Slow Fibonacci        696.63 K        1.44 μs   ±808.65%        1.38 μs        1.92 μs
Fibonacci with Matrix      420.12 K        2.38 μs   ±415.39%        2.25 μs        3.25 μs

Comparison: 
Very Slow Fibonacci        696.63 K
Fibonacci with Matrix      420.12 K - 1.66x slower +0.94 μs

##### With input 4 #####
Name                            ips        average  deviation         median         99th %
Very Slow Fibonacci        465.50 K        2.15 μs   ±396.15%        2.08 μs        2.88 μs
Fibonacci with Matrix      363.66 K        2.75 μs   ±335.59%        2.58 μs        3.75 μs

Comparison: 
Very Slow Fibonacci        465.50 K
Fibonacci with Matrix      363.66 K - 1.28x slower +0.60 μs

##### With input 5 #####
Name                            ips        average  deviation         median         99th %
Fibonacci with Matrix      327.94 K        3.05 μs   ±324.63%        2.88 μs        4.25 μs
Very Slow Fibonacci        307.30 K        3.25 μs   ±260.37%        3.13 μs        4.33 μs

Comparison: 
Fibonacci with Matrix      327.94 K
Very Slow Fibonacci        307.30 K - 1.07x slower +0.20 μs

##### With input 6 #####
Name                            ips        average  deviation         median         99th %
Fibonacci with Matrix      292.98 K        3.41 μs   ±212.03%        3.21 μs        8.67 μs
Very Slow Fibonacci        196.20 K        5.10 μs   ±138.86%        4.96 μs        6.92 μs

Comparison: 
Fibonacci with Matrix      292.98 K
Very Slow Fibonacci        196.20 K - 1.49x slower +1.68 μs

##### With input 7 #####
Name                            ips        average  deviation         median         99th %
Fibonacci with Matrix      271.75 K        3.68 μs   ±291.31%        3.46 μs        9.67 μs
Very Slow Fibonacci        124.97 K        8.00 μs    ±63.10%        7.83 μs       10.96 μs

Comparison: 
Fibonacci with Matrix      271.75 K
Very Slow Fibonacci        124.97 K - 2.17x slower +4.32 μs

##### With input 8 #####
Name                            ips        average  deviation         median         99th %
Fibonacci with Matrix      249.91 K        4.00 μs   ±162.08%        3.75 μs        5.75 μs
Very Slow Fibonacci         78.12 K       12.80 μs    ±22.94%       12.63 μs       17.46 μs

Comparison: 
Fibonacci with Matrix      249.91 K
Very Slow Fibonacci         78.12 K - 3.20x slower +8.80 μs

##### With input 9 #####
Name                            ips        average  deviation         median         99th %
Fibonacci with Matrix      232.67 K        4.30 μs   ±160.95%        4.04 μs       10.38 μs
Very Slow Fibonacci         48.32 K       20.70 μs     ±7.37%       20.54 μs       27.08 μs

Comparison: 
Fibonacci with Matrix      232.67 K
Very Slow Fibonacci         48.32 K - 4.82x slower +16.40 μs

	1	2	3	4	5	6	7	8	9
Very Slow Fibonacci	710	1070	1440	2150	3250	5100	8000	12800	20700
Fibonacci with Matrix	1730	2020	2380	2750	3050	3410	3680	4000	4300

5で逆転しましたね．

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up