Fibonacci sequence
Mix.install([
{:benchee, "~> 1.3.0"}
])
Introduction
シンプルな再帰的処理
-
n が与えられてから F(n) が求まるまでに指数時間の計算が必要となるため、実用的ではない
mod = MnishiguchiFib.SimpleRecursion
defmodule mod do
def calc(0), do: 0
def calc(1), do: 1
def calc(n), do: calc(n - 2) + calc(n - 1)
end
0..20 |> Enum.map(&mod.calc/1)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
指数関数的なコールを必要としない再帰的処理
mod = MnishiguchiFib.NonexponentialRecursion
defmodule mod do
def calc(n, prev_acc \\ 0, acc \\ 1)
def calc(n, _, _) when n < 0, do: :error
def calc(0, _, _), do: 0
def calc(1, _, acc), do: acc
def calc(n, prev_acc, acc), do: calc(n - 1, acc, prev_acc + acc)
end
0..20 |> Enum.map(&mod.calc/1)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
一般項の公式
mod = MnishiguchiFib.Formula
defmodule mod do
def calc(n) do
round((((1 + 5 ** 0.5) / 2) ** n - ((1 - 5 ** 0.5) / 2) ** n) / 5 ** 0.5)
end
end
0..20 |> Enum.map(&mod.calc/1)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
Map でメモ化
mod = MnishiguchiFib.MemoWithMap
defmodule mod do
def calc(number) do
{value, _} = calc(number, %{0 => 0, 1 => 1})
value
end
def calc(number, lookup) when number in 0..1, do: {number, lookup}
def calc(number, lookup) when is_map_key(lookup, number), do: {lookup[number], lookup}
def calc(number, lookup) do
{value1, lookup} = calc(number - 1, lookup)
{value2, lookup} = calc(number - 2, lookup)
value = value1 + value2
{value, Map.put(lookup, number, value)}
end
end
0..20 |> Enum.map(&mod.calc/1)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
ETS でメモ化
mod = MnishiguchiFib.MemoWithEts
defmodule mod do
alias __MODULE__.Fib
alias __MODULE__.FibCache
def calc(number) do
Fib.init()
Fib.calc(number)
end
defmodule Fib do
def init(), do: FibCache.init_table()
def calc(number) when number in 0..1, do: number
def calc(number) do
case FibCache.get_value(number) do
nil ->
value = calc(number - 1) + calc(number - 2)
FibCache.put_value(number, value)
value
value ->
value
end
end
end
defmodule FibCache do
@ets_table __MODULE__
def init_table() do
case :ets.whereis(@ets_table) do
:undefined ->
:ets.new(@ets_table, [:set, :named_table, :public])
:created
_ ->
:ets.delete_all_objects(@ets_table)
:cleared
end
end
def get_value(number) do
case :ets.lookup(@ets_table, number) do
[{^number, value}] -> value
[] -> nil
end
end
def put_value(number, value) do
:ets.insert(@ets_table, {number, value})
end
end
end
0..20 |> Enum.map(&mod.calc/1)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
Bench
defmodule MnishiguchiFib.Bench do
def run(n \\ 20) do
[
MnishiguchiFib.SimpleRecursion,
MnishiguchiFib.NonexponentialRecursion,
MnishiguchiFib.Formula,
MnishiguchiFib.MemoWithMap,
MnishiguchiFib.MemoWithEts
]
|> Map.new(fn mod -> {mod, &mod.calc/1} end)
|> Benchee.run(inputs: %{"n" => n})
end
end
MnishiguchiFib.Bench.run()
Operating System: macOS
CPU Information: Apple M1 Pro
Number of Available Cores: 10
Available memory: 32 GB
Elixir 1.16.0
Erlang 26.2.1
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: n
Estimated total run time: 35 s
Benchmarking Elixir.MnishiguchiFib.SimpleRecursion with input n ...
Benchmarking Elixir.MnishiguchiFib.NonexponentialRecursion with input n ...
Warning: The function you are trying to benchmark is super fast, making measurements more unreliable!
This holds especially true for memory measurements or when running with hooks.
See: https://github.com/bencheeorg/benchee/wiki/Benchee-Warnings#fast-execution-warning
You may disable this warning by passing print: [fast_warning: false] as configuration options.
Benchmarking Elixir.MnishiguchiFib.Formula with input n ...
Benchmarking Elixir.MnishiguchiFib.MemoWithMap with input n ...
Benchmarking Elixir.MnishiguchiFib.MemoWithEts with input n ...
Calculating statistics...
Formatting results...
##### With input n #####
Name ips average deviation median 99th %
Elixir.MnishiguchiFib.NonexponentialRecursion 17.63 M 56.72 ns ±3839.40% 54.20 ns 70.80 ns
Elixir.MnishiguchiFib.Formula 3.99 M 250.38 ns ±13617.62% 167 ns 333 ns
Elixir.MnishiguchiFib.MemoWithMap 1.17 M 856.69 ns ±1588.02% 791 ns 1000 ns
Elixir.MnishiguchiFib.MemoWithEts 0.34 M 2957.96 ns ±330.84% 2875 ns 3250 ns
Elixir.MnishiguchiFib.SimpleRecursion 0.0192 M 51955.08 ns ±7.29% 51334 ns 62543 ns
Comparison:
Elixir.MnishiguchiFib.NonexponentialRecursion 17.63 M
Elixir.MnishiguchiFib.Formula 3.99 M - 4.41x slower +193.66 ns
Elixir.MnishiguchiFib.MemoWithMap 1.17 M - 15.10x slower +799.97 ns
Elixir.MnishiguchiFib.MemoWithEts 0.34 M - 52.15x slower +2901.23 ns
Elixir.MnishiguchiFib.SimpleRecursion 0.0192 M - 915.93x slower +51898.36 ns
%Benchee.Suite{
system: %Benchee.System{
elixir: "1.16.0",
erlang: "26.2.1",
jit_enabled?: true,
num_cores: 10,
os: :macOS,
available_memory: "32 GB",
cpu_speed: "Apple M1 Pro"
},
configuration: %Benchee.Configuration{
parallel: 1,
time: 5000000000.0,
warmup: 2000000000.0,
memory_time: 0.0,
reduction_time: 0.0,
pre_check: false,
formatters: [Benchee.Formatters.Console],
percentiles: ~c"2c",
print: %{configuration: true, benchmarking: true, fast_warning: true},
inputs: [{"n", 20}],
input_names: ["n"],
save: false,
load: false,
unit_scaling: :best,
assigns: %{},
before_each: nil,
after_each: nil,
before_scenario: nil,
after_scenario: nil,
measure_function_call_overhead: false,
title: nil,
profile_after: false
},
scenarios: [
%Benchee.Scenario{
name: "Elixir.MnishiguchiFib.NonexponentialRecursion",
job_name: "Elixir.MnishiguchiFib.NonexponentialRecursion",
function: &MnishiguchiFib.NonexponentialRecursion.calc/1,
input_name: "n",
input: 20,
before_each: nil,
after_each: nil,
before_scenario: nil,
after_scenario: nil,
tag: nil,
run_time_data: %Benchee.CollectionData{
statistics: %Benchee.Statistics{
average: 56.72362881385124,
ips: 17629337.56021991,
std_dev: 2177.8450145095926,
std_dev_ratio: 38.39396491463163,
std_dev_ips: 676860167.7552809,
median: 54.2,
percentiles: %{50 => 54.2, 99 => 70.8},
mode: 54.2,
minimum: 41.6,
maximum: 4986000.6,
relative_more: nil,
relative_less: nil,
absolute_difference: nil,
sample_size: 5726842
},
samples: [91.7, 58.4, 54.1, 54.1, 54.1, 54.2, 54.2, 50.0, 54.1, 54.2, 54.2, 54.2, 54.1,
54.1, 54.1, 445.8, 50.0, 62.5, 58.4, 62.5, 58.3, 58.4, 58.4, 54.2, 54.2, 54.2, 58.3, 58.3,
54.2, 54.2, 66.7, 54.2, 54.2, ...]
},
memory_usage_data: %Benchee.CollectionData{
statistics: %Benchee.Statistics{
average: nil,
ips: nil,
std_dev: nil,
std_dev_ratio: nil,
std_dev_ips: nil,
median: nil,
percentiles: nil,
mode: nil,
minimum: nil,
maximum: nil,
relative_more: nil,
relative_less: nil,
absolute_difference: nil,
sample_size: 0
},
samples: []
},
reductions_data: %Benchee.CollectionData{
statistics: %Benchee.Statistics{
average: nil,
ips: nil,
std_dev: nil,
std_dev_ratio: nil,
std_dev_ips: nil,
median: nil,
percentiles: nil,
mode: nil,
minimum: nil,
maximum: nil,
relative_more: nil,
relative_less: nil,
absolute_difference: nil,
sample_size: 0
},
samples: []
}
},
%Benchee.Scenario{
name: "Elixir.MnishiguchiFib.Formula",
job_name: "Elixir.MnishiguchiFib.Formula",
function: &MnishiguchiFib.Formula.calc/1,
input_name: "n",
input: 20,
before_each: nil,
after_each: nil,
before_scenario: nil,
after_scenario: nil,
tag: nil,
run_time_data: %Benchee.CollectionData{
statistics: %Benchee.Statistics{
average: 250.37981430461147,
ips: 3993932.189690829,
std_dev: 34095.77576373041,
std_dev_ratio: 136.1762163552433,
std_dev_ips: 543878573.9715089,
median: 167.0,
percentiles: %{50 => 167.0, 99 => 333.0},
mode: 167,
minimum: 83,
maximum: 61531745,
relative_more: 4.414030264641173,
relative_less: 0.22655032703571468,
absolute_difference: 193.65618549076024,
sample_size: 12329870
},
samples: [2625, 208, 208, 167, 209, 209, 20583, 250, 208, 167, 1250, 250, 166, 208, 167,
209, 167, 208, 208, 208, 167, 209, 208, 250, 209, 208, 166, 167, 209, 208, 1125, 166, ...]
},
memory_usage_data: %Benchee.CollectionData{
statistics: %Benchee.Statistics{
average: nil,
ips: nil,
std_dev: nil,
std_dev_ratio: nil,
std_dev_ips: nil,
median: nil,
percentiles: nil,
mode: nil,
minimum: nil,
maximum: nil,
relative_more: nil,
relative_less: nil,
absolute_difference: nil,
sample_size: 0
},
samples: []
},
reductions_data: %Benchee.CollectionData{
statistics: %Benchee.Statistics{
average: nil,
ips: nil,
std_dev: nil,
std_dev_ratio: nil,
std_dev_ips: nil,
median: nil,
percentiles: nil,
mode: nil,
minimum: nil,
maximum: nil,
relative_more: nil,
relative_less: nil,
absolute_difference: nil,
sample_size: 0
},
samples: []
}
},
%Benchee.Scenario{
name: "Elixir.MnishiguchiFib.MemoWithMap",
job_name: "Elixir.MnishiguchiFib.MemoWithMap",
function: &MnishiguchiFib.MemoWithMap.calc/1,
input_name: "n",
input: 20,
before_each: nil,
after_each: nil,
before_scenario: nil,
after_scenario: nil,
tag: nil,
run_time_data: %Benchee.CollectionData{
statistics: %Benchee.Statistics{
average: 856.6918655303979,
ips: 1167280.839512672,
std_dev: 13604.451314142527,
std_dev_ratio: 15.880215351081564,
std_dev_ips: 18536671.10665251,
median: 791.0,
percentiles: %{50 => 791.0, 99 => 1000.0},
mode: 750,
minimum: 666,
maximum: 17205290,
relative_more: 15.102910082529908,
relative_less: 0.06621240506203747,
absolute_difference: 799.9682367165466,
sample_size: 4893091
},
samples: [2792, 1292, 1750, 1125, 1084, 1459, 1125, 1083, 1333, 1041, 1042, 1209, 1041,
1000, 1166, 1000, 958, 1208, 1042, 959, 1167, 1000, 4542, 1209, 1125, 1084, 1291, 1042,
1000, 1208, 1042, ...]
},
memory_usage_data: %Benchee.CollectionData{
statistics: %Benchee.Statistics{
average: nil,
ips: nil,
std_dev: nil,
std_dev_ratio: nil,
std_dev_ips: nil,
median: nil,
percentiles: nil,
mode: nil,
minimum: nil,
maximum: nil,
relative_more: nil,
relative_less: nil,
absolute_difference: nil,
sample_size: 0
},
samples: []
},
reductions_data: %Benchee.CollectionData{
statistics: %Benchee.Statistics{
average: nil,
ips: nil,
std_dev: nil,
std_dev_ratio: nil,
std_dev_ips: nil,
median: nil,
percentiles: nil,
mode: nil,
minimum: nil,
maximum: nil,
relative_more: nil,
relative_less: nil,
absolute_difference: nil,
sample_size: 0
},
samples: []
}
},
%Benchee.Scenario{
name: "Elixir.MnishiguchiFib.MemoWithEts",
job_name: "Elixir.MnishiguchiFib.MemoWithEts",
function: &MnishiguchiFib.MemoWithEts.calc/1,
input_name: "n",
input: 20,
before_each: nil,
after_each: nil,
before_scenario: nil,
after_scenario: nil,
tag: nil,
run_time_data: %Benchee.CollectionData{
statistics: %Benchee.Statistics{
average: 2957.9568087869884,
ips: 338071.19733099965,
std_dev: 9786.25159189019,
std_dev_ratio: 3.308449793052718,
std_dev_ips: 1118491.5828468304,
median: 2875.0,
percentiles: %{50 => 2875.0, 99 => 3250.0},
mode: 2875,
minimum: 2708,
maximum: 6815615,
relative_more: 52.146819070656676,
relative_less: 0.019176625110057882,
absolute_difference: 2901.2331799731373,
sample_size: 1585253
},
samples: [10583, 3083, 3001, 3208, 2917, 2917, 3417, 2959, 3250, 3583, 3042, 59335, 23458,
10668, 3125, 3458, 3042, 3167, 3584, 2917, 2833, 3083, 2875, 3541, 3125, 2875, 2875, 3125,
2875, 2876, ...]
},
memory_usage_data: %Benchee.CollectionData{
statistics: %Benchee.Statistics{
average: nil,
ips: nil,
std_dev: nil,
std_dev_ratio: nil,
std_dev_ips: nil,
median: nil,
percentiles: nil,
mode: nil,
minimum: nil,
maximum: nil,
relative_more: nil,
relative_less: nil,
absolute_difference: nil,
sample_size: 0
},
samples: []
},
reductions_data: %Benchee.CollectionData{
statistics: %Benchee.Statistics{
average: nil,
ips: nil,
std_dev: nil,
std_dev_ratio: nil,
std_dev_ips: nil,
median: nil,
percentiles: nil,
mode: nil,
minimum: nil,
maximum: nil,
relative_more: nil,
relative_less: nil,
absolute_difference: nil,
sample_size: 0
},
samples: []
}
},
%Benchee.Scenario{
name: "Elixir.MnishiguchiFib.SimpleRecursion",
job_name: "Elixir.MnishiguchiFib.SimpleRecursion",
function: &MnishiguchiFib.SimpleRecursion.calc/1,
input_name: "n",
input: 20,
before_each: nil,
after_each: nil,
before_scenario: nil,
after_scenario: nil,
tag: nil,
run_time_data: %Benchee.CollectionData{
statistics: %Benchee.Statistics{
average: 51955.083857507954,
ips: 19247.3945907315,
std_dev: 3788.8924615142605,
std_dev_ratio: 0.07292630826861293,
std_dev_ips: 1403.6414312913184,
median: 51334.0,
percentiles: %{50 => 51334.0, 99 => 62543.0},
mode: 51376,
minimum: 50709,
maximum: 555427,
relative_more: 915.9337112935401,
relative_less: 0.0010917820663983817,
absolute_difference: 51898.3602286941,
sample_size: 95865
},
samples: [56751, 53917, 55584, 56460, 52751, 51418, 51416, 51376, 51376, 51334, 51376,
51334, 51376, 51375, 51376, 51501, 51418, 51334, 52167, 51334, 51542, 51542, 51251, 51501,
51459, 51251, 51376, 51501, 51418, ...]
},
memory_usage_data: %Benchee.CollectionData{
statistics: %Benchee.Statistics{
average: nil,
ips: nil,
std_dev: nil,
std_dev_ratio: nil,
std_dev_ips: nil,
median: nil,
percentiles: nil,
mode: nil,
minimum: nil,
maximum: nil,
relative_more: nil,
relative_less: nil,
absolute_difference: nil,
sample_size: 0
},
samples: []
},
reductions_data: %Benchee.CollectionData{
statistics: %Benchee.Statistics{
average: nil,
ips: nil,
std_dev: nil,
std_dev_ratio: nil,
std_dev_ips: nil,
median: nil,
percentiles: nil,
mode: nil,
minimum: nil,
maximum: nil,
relative_more: nil,
relative_less: nil,
absolute_difference: nil,
sample_size: 0
},
samples: []
}
}
]
}
