Go to Qiita Advent Calendar 2024 Top
LoginSignup
6
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

ElixirAdvent Calendar 2024

Day 19
@zacky1972(山崎 進)infukuoka.ex：福岡Elixirコミュ

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

Last updated at Posted at 2024-12-29

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

素朴なコード

fib_benchee.exs
Mix.install([:benchee])

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
  },
  inputs: %{
    "1" => 1,
    "2" => 2,
    "3" => 3,
    "4" => 4,
    "5" => 5,
    "6" => 6,
    "7" => 7,
    "8" => 8,
    "9" => 9,
    "10" => 10
  }
)

実行結果

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, 2, 3, 4, 5, 6, 7, 8, 9
Estimated total run time: 1 min 10 s

Benchmarking Very Slow Fibonacci with input 1 ...
Benchmarking Very Slow Fibonacci with input 10 ...
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.46 M      685.64 ns  ±1989.29%         625 ns         875 ns

##### With input 10 #####
Name                          ips        average  deviation         median         99th %
Very Slow Fibonacci       29.92 K       33.42 μs    ±27.52%       33.21 μs       39.71 μs

##### With input 2 #####
Name                          ips        average  deviation         median         99th %
Very Slow Fibonacci      946.56 K        1.06 μs  ±1299.08%           1 μs        1.33 μs

##### With input 3 #####
Name                          ips        average  deviation         median         99th %
Very Slow Fibonacci      699.19 K        1.43 μs   ±844.05%        1.38 μs        1.79 μs

##### With input 4 #####
Name                          ips        average  deviation         median         99th %
Very Slow Fibonacci      468.81 K        2.13 μs   ±388.35%        2.08 μs        2.67 μs

##### With input 5 #####
Name                          ips        average  deviation         median         99th %
Very Slow Fibonacci      308.24 K        3.24 μs   ±268.69%        3.13 μs        4.42 μs

##### With input 6 #####
Name                          ips        average  deviation         median         99th %
Very Slow Fibonacci      197.26 K        5.07 μs   ±234.96%        4.96 μs        6.92 μs

##### With input 7 #####
Name                          ips        average  deviation         median         99th %
Very Slow Fibonacci      124.23 K        8.05 μs    ±52.30%        7.92 μs          11 μs

##### With input 8 #####
Name                          ips        average  deviation         median         99th %
Very Slow Fibonacci       78.44 K       12.75 μs    ±16.64%       12.58 μs       17.33 μs

##### With input 9 #####
Name                          ips        average  deviation         median         99th %
Very Slow Fibonacci       48.28 K       20.71 μs    ±10.17%       20.42 μs       27.50 μs
1 2 3 4 5 6 7 8 9 10
Very Slow Fibonacci 686 1060 1430 2130 3240 5070 8050 12750 20710 33420

Very Slow Fibonacci

実行時間を指数関数で近似できました．

memoization

fib_benchee.exs
Mix.install([:benchee])

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

defmodule Fibonacci.Memoization do
  use Agent

  def start_link(initial_value) when is_map(initial_value) do
    Agent.start_link(fn -> initial_value end, name: __MODULE__)
  end

  def of(n) do
    case Agent.get(__MODULE__, & &1) do
      map when is_map_key(map, n) -> 
        Map.get(map, n)

      _ -> 
        result = 
          case n do
            0 -> 0
            1 -> 1
            n -> of(n - 2) + of(n - 1)
          end

        Agent.update(__MODULE__, &(Map.put(&1, n, result)))
        result
    end
  end
end

Benchee.run(
  %{
    "Very Slow Fibonacci" => fn input -> Enum.reduce(1..100, fn _, _ -> Fibonacci.of(input) end) end,
    "Fibonacci with Memoization" => 
      {
        fn input -> Enum.reduce(1..100, fn _, _ -> Fibonacci.Memoization.of(input) end) end,
        before_scenario: fn input -> 
          Fibonacci.Memoization.start_link(%{})
          input
        end
      }
  },
  inputs: %{
    "1" => 1,
    "2" => 2,
    "3" => 3,
    "4" => 4,
    "5" => 5,
    "6" => 6,
    "7" => 7,
    "8" => 8,
    "9" => 9,
    "10" => 10,
    "11" => 11,
    "12" => 12,
    "13" => 13,
    "14" => 14,
    "15" => 15,
    "16" => 16,
    "17" => 17,
    "18" => 18,
    "19" => 19,
    "20" => 20
  }
)

実行結果

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, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 3, 4, 5, 6, 7, 8, 9
Estimated total run time: 4 min 40 s

Benchmarking Fibonacci with Memoization with input 1 ...
Benchmarking Fibonacci with Memoization with input 10 ...
Benchmarking Fibonacci with Memoization with input 11 ...
Benchmarking Fibonacci with Memoization with input 12 ...
Benchmarking Fibonacci with Memoization with input 13 ...
Benchmarking Fibonacci with Memoization with input 14 ...
Benchmarking Fibonacci with Memoization with input 15 ...
Benchmarking Fibonacci with Memoization with input 16 ...
Benchmarking Fibonacci with Memoization with input 17 ...
Benchmarking Fibonacci with Memoization with input 18 ...
Benchmarking Fibonacci with Memoization with input 19 ...
Benchmarking Fibonacci with Memoization with input 2 ...
Benchmarking Fibonacci with Memoization with input 20 ...
Benchmarking Fibonacci with Memoization with input 3 ...
Benchmarking Fibonacci with Memoization with input 4 ...
Benchmarking Fibonacci with Memoization with input 5 ...
Benchmarking Fibonacci with Memoization with input 6 ...
Benchmarking Fibonacci with Memoization with input 7 ...
Benchmarking Fibonacci with Memoization with input 8 ...
Benchmarking Fibonacci with Memoization with input 9 ...
Benchmarking Very Slow Fibonacci with input 1 ...
Benchmarking Very Slow Fibonacci with input 10 ...
Benchmarking Very Slow Fibonacci with input 11 ...
Benchmarking Very Slow Fibonacci with input 12 ...
Benchmarking Very Slow Fibonacci with input 13 ...
Benchmarking Very Slow Fibonacci with input 14 ...
Benchmarking Very Slow Fibonacci with input 15 ...
Benchmarking Very Slow Fibonacci with input 16 ...
Benchmarking Very Slow Fibonacci with input 17 ...
Benchmarking Very Slow Fibonacci with input 18 ...
Benchmarking Very Slow Fibonacci with input 19 ...
Benchmarking Very Slow Fibonacci with input 2 ...
Benchmarking Very Slow Fibonacci with input 20 ...
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.39 M        0.72 μs  ±2294.72%        0.67 μs        0.96 μs
Fibonacci with Memoization      0.0129 M       77.31 μs     ±5.92%       76.25 μs       97.25 μs

Comparison: 
Very Slow Fibonacci               1.39 M
Fibonacci with Memoization      0.0129 M - 107.23x slower +76.59 μs

##### With input 10 #####
Name                                 ips        average  deviation         median         99th %
Very Slow Fibonacci              29.46 K       33.94 μs     ±6.86%       33.50 μs          46 μs
Fibonacci with Memoization       12.52 K       79.85 μs     ±7.83%       78.29 μs      100.00 μs

Comparison: 
Very Slow Fibonacci              29.46 K
Fibonacci with Memoization       12.52 K - 2.35x slower +45.91 μs

##### With input 11 #####
Name                                 ips        average  deviation         median         99th %
Very Slow Fibonacci              18.01 K       55.52 μs     ±6.33%       54.88 μs       72.42 μs
Fibonacci with Memoization       12.49 K       80.05 μs     ±8.09%       78.50 μs      101.38 μs

Comparison: 
Very Slow Fibonacci              18.01 K
Fibonacci with Memoization       12.49 K - 1.44x slower +24.52 μs

##### With input 12 #####
Name                                 ips        average  deviation         median         99th %
Fibonacci with Memoization       12.32 K       81.16 μs     ±4.84%       82.50 μs       93.96 μs
Very Slow Fibonacci              11.16 K       89.62 μs    ±15.19%       88.17 μs      110.58 μs

Comparison: 
Fibonacci with Memoization       12.32 K
Very Slow Fibonacci              11.16 K - 1.10x slower +8.46 μs

##### With input 13 #####
Name                                 ips        average  deviation         median         99th %
Fibonacci with Memoization       12.14 K       82.36 μs     ±5.22%       83.50 μs       98.83 μs
Very Slow Fibonacci               6.91 K      144.71 μs     ±5.42%      142.17 μs      174.67 μs

Comparison: 
Fibonacci with Memoization       12.14 K
Very Slow Fibonacci               6.91 K - 1.76x slower +62.35 μs

##### With input 14 #####
Name                                 ips        average  deviation         median         99th %
Fibonacci with Memoization       12.51 K       79.92 μs     ±6.14%       79.21 μs       93.83 μs
Very Slow Fibonacci               4.27 K      234.23 μs     ±4.30%      230.34 μs      277.22 μs

Comparison: 
Fibonacci with Memoization       12.51 K
Very Slow Fibonacci               4.27 K - 2.93x slower +154.31 μs

##### With input 15 #####
Name                                 ips        average  deviation         median         99th %
Fibonacci with Memoization       12.20 K       81.99 μs     ±6.64%       82.29 μs      101.21 μs
Very Slow Fibonacci               2.65 K      376.73 μs     ±3.19%      372.30 μs      427.34 μs

Comparison: 
Fibonacci with Memoization       12.20 K
Very Slow Fibonacci               2.65 K - 4.59x slower +294.74 μs

##### With input 16 #####
Name                                 ips        average  deviation         median         99th %
Fibonacci with Memoization       11.98 K       83.45 μs     ±5.81%       83.38 μs      103.54 μs
Very Slow Fibonacci               1.64 K      608.78 μs     ±3.20%      602.09 μs      702.37 μs

Comparison: 
Fibonacci with Memoization       11.98 K
Very Slow Fibonacci               1.64 K - 7.29x slower +525.32 μs

##### With input 17 #####
Name                                 ips        average  deviation         median         99th %
Fibonacci with Memoization       11.92 K       83.90 μs     ±5.44%       84.04 μs      101.04 μs
Very Slow Fibonacci               1.01 K      987.62 μs     ±2.98%      974.99 μs     1119.12 μs

Comparison: 
Fibonacci with Memoization       11.92 K
Very Slow Fibonacci               1.01 K - 11.77x slower +903.72 μs

##### With input 18 #####
Name                                 ips        average  deviation         median         99th %
Fibonacci with Memoization       11.94 K      0.0837 ms     ±5.48%      0.0839 ms       0.101 ms
Very Slow Fibonacci               0.62 K        1.60 ms     ±2.21%        1.60 ms        1.72 ms

Comparison: 
Fibonacci with Memoization       11.94 K
Very Slow Fibonacci               0.62 K - 19.11x slower +1.52 ms

##### With input 19 #####
Name                                 ips        average  deviation         median         99th %
Fibonacci with Memoization       11.70 K      0.0855 ms     ±6.24%      0.0848 ms       0.102 ms
Very Slow Fibonacci               0.38 K        2.60 ms     ±2.99%        2.58 ms        2.92 ms

Comparison: 
Fibonacci with Memoization       11.70 K
Very Slow Fibonacci               0.38 K - 30.44x slower +2.52 ms

##### With input 2 #####
Name                                 ips        average  deviation         median         99th %
Very Slow Fibonacci             922.46 K        1.08 μs  ±1279.19%        1.04 μs        1.46 μs
Fibonacci with Memoization       11.73 K       85.25 μs     ±4.56%       84.71 μs         101 μs

Comparison: 
Very Slow Fibonacci             922.46 K
Fibonacci with Memoization       11.73 K - 78.64x slower +84.16 μs

##### With input 20 #####
Name                                 ips        average  deviation         median         99th %
Fibonacci with Memoization       11.66 K      0.0857 ms     ±4.90%      0.0848 ms       0.103 ms
Very Slow Fibonacci               0.24 K        4.23 ms     ±2.61%        4.21 ms        4.60 ms

Comparison: 
Fibonacci with Memoization       11.66 K
Very Slow Fibonacci               0.24 K - 49.33x slower +4.14 ms

##### With input 3 #####
Name                                 ips        average  deviation         median         99th %
Very Slow Fibonacci             695.91 K        1.44 μs   ±843.66%        1.38 μs        1.83 μs
Fibonacci with Memoization       11.68 K       85.64 μs     ±5.24%       85.29 μs      102.88 μs

Comparison: 
Very Slow Fibonacci             695.91 K
Fibonacci with Memoization       11.68 K - 59.60x slower +84.21 μs

##### With input 4 #####
Name                                 ips        average  deviation         median         99th %
Very Slow Fibonacci             460.09 K        2.17 μs   ±468.75%        2.08 μs        2.92 μs
Fibonacci with Memoization       11.72 K       85.34 μs     ±4.99%       84.83 μs      102.13 μs

Comparison: 
Very Slow Fibonacci             460.09 K
Fibonacci with Memoization       11.72 K - 39.27x slower +83.17 μs

##### With input 5 #####
Name                                 ips        average  deviation         median         99th %
Very Slow Fibonacci             309.01 K        3.24 μs   ±276.02%        3.13 μs        4.17 μs
Fibonacci with Memoization       11.72 K       85.30 μs     ±4.64%       84.63 μs      101.79 μs

Comparison: 
Very Slow Fibonacci             309.01 K
Fibonacci with Memoization       11.72 K - 26.36x slower +82.06 μs

##### With input 6 #####
Name                                 ips        average  deviation         median         99th %
Very Slow Fibonacci             195.39 K        5.12 μs   ±144.98%        4.96 μs        6.92 μs
Fibonacci with Memoization       11.70 K       85.45 μs     ±4.79%       84.75 μs      103.25 μs

Comparison: 
Very Slow Fibonacci             195.39 K
Fibonacci with Memoization       11.70 K - 16.70x slower +80.33 μs

##### With input 7 #####
Name                                 ips        average  deviation         median         99th %
Very Slow Fibonacci             123.82 K        8.08 μs    ±59.04%        7.88 μs       10.92 μs
Fibonacci with Memoization       11.70 K       85.50 μs     ±4.33%       84.75 μs      101.51 μs

Comparison: 
Very Slow Fibonacci             123.82 K
Fibonacci with Memoization       11.70 K - 10.59x slower +77.42 μs

##### With input 8 #####
Name                                 ips        average  deviation         median         99th %
Very Slow Fibonacci              76.18 K       13.13 μs    ±23.33%       12.75 μs       17.67 μs
Fibonacci with Memoization       11.71 K       85.41 μs     ±5.24%       84.79 μs      104.17 μs

Comparison: 
Very Slow Fibonacci              76.18 K
Fibonacci with Memoization       11.71 K - 6.51x slower +72.28 μs

##### With input 9 #####
Name                                 ips        average  deviation         median         99th %
Very Slow Fibonacci              47.50 K       21.05 μs     ±8.93%       20.46 μs       28.46 μs
Fibonacci with Memoization       11.69 K       85.53 μs    ±11.58%       84.63 μs      101.88 μs

Comparison: 
Very Slow Fibonacci              47.50 K
Fibonacci with Memoization       11.69 K - 4.06x slower +64.47 μs
With input 20

Name ips average deviation median 99th %
Fibonacci with Memoization 11.66 K 0.0857 ms ±4.90% 0.0848 ms 0.103 ms
Very Slow Fibonacci 0.24 K 4.23 ms ±2.61% 4.21 ms 4.60 ms

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Very Slow Fibonacci 720 1080 1440 2170 3240 5120 8080 13130 21060 33940 55520 89620 144710 234230 376730 608780 987620 1600000 2600000 4230000
Fibonacci with Memoization 77310 85250 85640 85340 85300 85450 85500 85410 85530 79850 80050 81160 82360 79920 81990 83450 83900 83700 85500 85700

Very Slow Fibonacci vs Fibonacci with Memoization

11くらいまでだとVery Slow Fibonacciの方が速く，12以降でFibonacci with Memoizationの方が速くなることがわかります．プロセスを用いたので，Memoizationのオーバーヘッドが思ったより大きいですね．

つづく．

6
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?