Help us understand the problem. What is going on with this article?

ElixirのEnum.filter_map/3、実は速くなかった説

More than 1 year has passed since last update.

Elixir 1.5(結構前ですね)から Enum.filter_map/3 がdeprecatedになりました。
フォーラムでもなんでなのか、というスレッドがありました(Why Enum.filter_map is deprecated? | Elixir Forum

filter_mapfilter |> map だとリストをなめる回数が倍になるから遅くなるのでは?と思ったのですが、測定しているのを見かけなかったので軽く測定しました

測定

コード

defmodule Targets do
  import Integer

  def list, do: Enum.to_list(1..10_000)
  def map_fun, do: fn i -> [i, i * i] end

  def filter_map do
    list |> Enum.filter_map(&is_even/1, map_fun)
  end

  def filter_then_map do
    list |> Enum.filter(&is_even/1) |> Enum.map(map_fun)
  end

  def flat_map do
    list
    |> Enum.flat_map(fn
      x when x |> is_even() -> [x |> map_fun.()]
      _ -> []
    end)
  end

  def comprehensions do
    for n <- list, is_even(n), do: map_fun.(n)
  end
end

Benchee.run(%{
  "filter_map" => &Targets.filter_map/0,
  "filter |> map" => &Targets.filter_then_map/0,
  "flat_map" => &Targets.flat_map/0,
  "comprehensions" => &Targets.comprehensions/0
})

結果

Operating System: macOS
CPU Information: Intel(R) Core(TM) i7-6567U CPU @ 3.30GHz
Number of Available Cores: 4
Available memory: 16 GB
Elixir 1.9.0
Erlang 22.0

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 28 s

Benchmarking comprehensions...
Benchmarking filter |> map...
Benchmarking filter_map...
Benchmarking flat_map...

Name                     ips        average  deviation         median         99th %
comprehensions        1.77 K      564.92 μs    ±16.07%         537 μs      939.67 μs
filter |> map         1.43 K      698.73 μs    ±16.88%         646 μs     1172.80 μs
filter_map            1.35 K      742.58 μs    ±16.73%         717 μs     1273.34 μs
flat_map              1.33 K      752.49 μs    ±19.94%         682 μs     1258.67 μs

Comparison: 
comprehensions        1.77 K
filter |> map         1.43 K - 1.24x slower +133.81 μs
filter_map            1.35 K - 1.31x slower +177.66 μs
flat_map              1.33 K - 1.33x slower +187.57 μs

いや filter |> map 速いじゃん…
今回はfilter部分で要素が半分になるのですが、要素数が減ったのが原因なのかと思ってフィルターをAll Trueにしたバージョンもやってみましたが、

Name                     ips        average  deviation         median         99th %
comprehensions        1.06 K      944.05 μs    ±24.59%      911.00 μs     1533.15 μs
filter |> map         1.03 K      969.13 μs    ±21.81%      862.00 μs     1482.06 μs
filter_map            1.01 K      990.51 μs    ±23.25%      953.00 μs     1581.86 μs

Comparison: 
comprehensions        1.06 K
filter |> map         1.03 K - 1.03x slower +25.09 μs
filter_map            1.01 K - 1.05x slower +46.47 μs

やはり順位は変わらず。

考察

Enum.filter_map/3 の定義は以下のようになっています (Elixir 1.9.0)

enum.ex
@doc false
@deprecated "Use Enum.filter/2 + Enum.map/2 or for comprehensions instead"
def filter_map(enumerable, filter, mapper) when is_list(enumerable) do
  for element <- enumerable, filter.(element), do: mapper.(element)
end

def filter_map(enumerable, filter, mapper) do
  enumerable
  |> reduce([], R.filter_map(filter, mapper))
  |> :lists.reverse()
end

…これまんま Targets.comprehensions じゃん なんで遅いんだ…

対して Enum.filter の実装はListの再帰呼び出しでした

enum.ex
@spec filter(t, (element -> as_boolean(term))) :: list
def filter(enumerable, fun) when is_list(enumerable) do
  filter_list(enumerable, fun)
end

def filter(enumerable, fun) do
  reduce(enumerable, [], R.filter(fun)) |> :lists.reverse()
end

defp filter_list([head | tail], fun) do
  if fun.(head) do
    [head | filter_list(tail, fun)]
  else
    filter_list(tail, fun)
  end
end

defp filter_list([], _fun) do
  []
end

for文より速い…のか…?
Enum.map はErlangの :lists.map に移譲してありました。

for文が効率悪いならなんでcomprehensionが一番早かったのか説明ができないし実に謎ですが、とりあえず今回の例だと filter_map/3 速くなかったしdeprecatedになるわな、という感じでした

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away