Elixirにおける反復,再帰および尾呼最適化

Elixirはリストのようなデータ構造をループするために再帰を使用します.大部分のそれの上でより高いレベル抽象化を通して隠されますEnum クラスは、いくつかの場合、再帰的な関数を書く場合、よりパフォーマンスを発揮できます.エリキシル錬金術のこのエピソードでは、これらのケースのいくつかを見つけようとします.
途中で、我々は体の再帰と尾部再帰関数について学びます.後者はしばしばより速くなっているように扱われますが、我々はそれが必ずしも真実であるというわけではないケースを見ます.右に飛び込みましょう!

列挙
エリクサーの機能を提供するEnum コレクションを列挙するモジュールです.

def sum_numbers1(list) do
  list
  |> Enum.filter(&is_number/1)
  |> Enum.reduce(0, fn n, sum -> n + sum end)
end

この例はリストを受け取り、そのリスト内のすべての数値の合計を返します.入力リストに非数値項目があるかもしれないのでEnum.filter/2 その項目だけを選択するis_number/1 trueを返します.その後、残りの値はEnum.reduce/3 .

sum_numbers1([1, 2, "three", 4, %{}]) # => 7

このソリューションが動作している間、それは結果を得るために全体のリストを2回繰り返します.これをより多くのパフォーマーにするには、代わりにこれを行うことができる再帰的な関数を書くことを選びます.

再帰
再帰的な関数は、1つの実行でタスク(非数値項目を削除し、残りを追加する)を行うことができます.これは、リスト内のすべての項目のために自分自身を呼び出すと、各項目をどうするかを決定するパターンマッチングを使用します.

# 1
def sum_numbers2([head | tail]) when is_number(head) do
  sum_numbers2(tail) + head
end

# 2
def sum_numbers2([_head | tail]) do
  sum_numbers2(tail)
end

# 3
def sum_numbers2([]) do
  0
end

の代わりに、Enum モジュールは、リストが空になるまでこのソリューションを呼び出します.つの関数頭を使用します.

リスト(頭)の最初の項目が番号であるとき、我々は電話しますsum_numbers2/1 リストの残り(頭以外の何でも、尾と呼ばれます)で.この呼び出しは、我々の現在の頭を加える数を返します.

頭が数字でないとき、我々はそれを呼び出すことによってそれをドロップしますsum_numbers2/1 機能尾だけ.

リストが空の場合、0を返します.

sum_numbers2([1, 2, "three", 4, %{}]) # => 7

この関数を[1, 2, "three", 4, %{}] , the sum_numbers2/1 関数は、結果を取得するには、次の順序で繰り返し呼び出されます.

sum_numbers2([1, 2, "three", 4, %{}])

sum_numbers2([2, "three", 4, %{}]) + 1

sum_numbers2(["three", 4, %{}]) + 1 + 2

sum_numbers2([4, %{}]) + 1 + 2

sum_numbers2([%{}]) + 1 + 2 + 4

sum_numbers2([]) + 1 + 2 + 4

0 + 1 + 2 + 4

このリストは、関数がどのようにして我々が結果になるまで簡略化されたかを示します.一度、各項目に加えて、プラスの最後に空のリストをもう一度.
機能は各反復のために自分自身を呼び出すので、リスト内の各項目はstack frame 呼び出しスタックに追加する.これは、各項目がその結果を要求するために実行される必要がある関数への呼び出しを保証するためです.スタックスタックにスタックフレームを追加するには、いくつかのメモリを割り当てる必要があります.

テール再帰とテールコール最適化
メモリのフットプリントを最小限に保つために、Erlangのようないくつかの言語で、Elxirはテールコール最適化を実装します.コードの小さな書き直しで、スタックフレームが追加され、メモリが割り当てられるのを防ぐことができます.

# 1
def sum_numbers3(list) do
  do_sum_numbers3(list, 0)
end

# 2
defp do_sum_numbers3([head | tail], sum) when is_number(head) do
  do_sum_numbers3(tail, sum + head)
end

# 3
defp do_sum_numbers3([_head | tail], sum) do
  do_sum_numbers3(tail, sum)
end

# 4
defp do_sum_numbers3([], sum) do
  sum
end

この例は、以前からの関数のさらに別の実装です.ただし、この例は末尾再帰的です.つまり、継続する前に自分自身への呼び出しを待つ必要はありません.アキュムレータを維持することによってsum ) 関数呼び出しの代わりに、現在の値を保持します.

The sum_numbers3/1 関数はpublic関数です.do_sum_numbers3/2 関数を渡されたリストとアキュムレータの0 で始める.

前の例とほぼ同じです.do_sum_numbers3/2 's最初の関数頭は、数字頭でリストにマッチします.それはリストの尾でそれ自体を呼びます、そして、頭はアキュムレーターに加えられます.

頭が数字でないとき、第3の機能頭は何かを変えることなく、尾と現在のアキュムレータでそれ自体を呼ぶことによってそれを落とします.

最後に、exit節はアキュムレータを返します.

関数の最後にそれを呼び出して、すべての計算された値でアキュムレータを通過することによって、Erlang VMはテール呼び出し最適化と呼ばれているトリックを実行することができます.代わりに、関数の先頭までジャンプして、現在のフレームを使用します.
テール呼び出しの最適化は、スタックの問題に実行せずに関数を呼び出すことができます.

def sleep, do: sleep

この例では、継続的に自分自身を呼び出す関数を実装します.tail呼び出しの最適化なしで、この関数はスタックエラーを生成します.

どちらが速いですか.
我々は、同じ機能の3つの実装を書きました.最初の使用Enum.filter/2 and Enum.reduce/3 リストをフィルタリングして合計し、リストを2回繰り返します.それを修正するために、我々はもう一つの試みでそれをした再帰的な機能を使用しました.

letters = Enum.map(?a..?z, fn x -> <<x::utf8>> end)
numbers = Enum.to_list(0..10_000)
list = Enum.shuffle(letters ++ numbers)

Benchee.run(
  %{
    "Enum.filter/2 and Enum.reduce/3" => fn -> Recursion.sum_numbers1(list) end,
    "Body-recursive" => fn -> Recursion.sum_numbers2(list) end,
    "Tail-recursive" => fn -> Recursion.sum_numbers3(list) end
  },
  time: 10,
  memory_time: 2
)

我々のソリューションをベンチマークするために、我々は使用しますBenchee . それぞれの関数の文字列と数字のシャッフルリストを準備します.

Name                                      ips        average  deviation         median         99th %
Tail-recursive                       107.35 K        9.32 μs    ±21.39%           9 μs          14 μs
Body-recursive                        55.65 K       17.97 μs   ±662.77%          14 μs          34 μs
Enum.filter/2 and Enum.reduce/3       20.86 K       47.94 μs    ±51.46%          46 μs          85 μs

Comparison:
Tail-recursive                       107.35 K
Body-recursive                        55.65 K - 1.93x slower
Enum.filter/2 and Enum.reduce/3       20.86 K - 5.15x slower

Memory usage statistics:

Name                               Memory usage
Tail-recursive                              0 B
Body-recursive                              0 B
Enum.filter/2 and Enum.reduce/3         16064 B

このマシンでのテストでは、体の再帰的なバージョンはEnum.filter/2 and Enum.reduce/3 . 尾の再帰的なバージョンは、ほぼ2倍の高速広告体の再帰的なものだった.

尾の呼び出しの再帰は常に高速ですか?
そのベンチマークの結果はかなり確信しているように見えますが、テール再帰は常に体の再帰より速くありません.実際、それは7 myths of Erlang performance .
末尾の再帰的呼び出しは、通常、いくつかの状況ではボディ再帰関数がより速くなる前に見た例のようなリストの縮小に対して高速です.この関数は、リストをマッピングする際にしばしばtrueとなります.ここで、関数はリストを受け取り、リストを1つの値に減らすことなくリストを返します.

def double_numbers1(list) do
  list
  |> Enum.filter(&is_number/1)
  |> Enum.map(fn n -> n * 2 end)
end

def double_numbers2([]) do
  []
end

def double_numbers2([head | tail]) when is_number(head) do
  [head * 2 | double_numbers2(tail)]
end

def double_numbers2([_head | tail]) do
  double_numbers2(tail)
end

def double_numbers3(list) do
  list
  |> do_double_numbers3([])
  |> Enum.reverse()
end

defp do_double_numbers3([], acc) do
  acc
end

defp do_double_numbers3([head | tail], acc) when is_number(head) do
  do_double_numbers3(tail, [head * 2 | acc])
end

defp do_double_numbers3([_head | tail], acc) do
  do_double_numbers3(tail, acc)
end

この例は、以前に見た例のようなものですが、すべての数字を一緒に追加したり、単一の数に減らしたりする代わりにdouble_numbers/1 関数はすべての数値を2倍にし、リスト内でそれらを返します.
以前と同様に、3つの実装があります.最初の用途Enum.filter/2 and Enum.map/2 リストを2回繰り返すと、2番目はbody recursiveで、最後はtail recursiveです.返される前に、tail recursive関数はリストを逆にする必要があります.
注:チェックアウトexample project より多くの可能な実装の比較のために、リスト理解とリストを逆にしない尾再帰的なバージョンのように.

Name                                   ips        average  deviation         median         99th %
body-recursive                     36.86 K       27.13 μs    ±39.82%          26 μs          47 μs
tail-recursive                     27.46 K       36.42 μs  ±1176.74%          27 μs          80 μs
Enum.filter/2 and Enum.map/2       12.62 K       79.25 μs   ±194.81%          62 μs         186 μs

Comparison:
body-recursive                     36.86 K
tail-recursive                     27.46 K - 1.34x slower
Enum.filter/2 and Enum.map/2       12.62 K - 2.92x slower

Memory usage statistics:

Name                            Memory usage
body-recursive                      15.64 KB
tail-recursive                      20.09 KB - 1.28x memory usage
Enum.filter/2 and Enum.map/2        31.33 KB - 2.00x memory usage

これらの実装のそれぞれについてベンチマークを実行すると、この場合はボディ再帰版が最速であることがわかります.テール再帰バージョンのリストを逆にすることで、改善されたパフォーマンステール呼び出し最適化が無効になります.

いつものように
これは、エリキシルの再帰への我々の観察を結びます.親指のように彼らがそれを返す前に結果を逆にする必要がないならば、尾再帰関数はより速いです.これは、リスト全体で別の反復を必要とするためです.最初の例のように、テール再帰関数は通常、リストを減らすのが速い.
どちらが最良のアプローチは状況によって異なります.ミッションクリティカルループについては、どのソリューションが高速であるかを測定するベンチマークを書くのは通常、あなたのベストベットです.
再帰の詳細については、必ず読んでくださいthis overview 利用可能なメソッドの、そしていつ使用するか.あなたがこの記事が好きならばsubscribe to the mailing list あなたはより多くのエリクサー錬金術を読んでみたい!