この記事は、fukuoka.ex Elixir／Phoenix Advent Calendar 2020 16日目です。

Elixir Advent Calendar7日目の @koyo-miyamura 君のElixirで動的計画法（DP）を実装してみた（Goとの比較つき）に刺激を受け、動的計画法関連です。

Computer Science(CS)的な部分はElixirやRubyから入った人は通っていないことが多かったり(単純に適応できない部分も多いし)するので、そういう記事があると嬉しくなる人です。

勝手に亜種的な記事を書こうとしてますが、元記事がfukuoka.exのAdvent Calendarでなく、Elixir Advent Calendarだったのは気付かないで下さい。

モチベーション

前述記事では手続き型のやり方を関数型に持ってくる場合にMapを使うことで解決していたのですが、以前純粋関数型データ構造を読んで、関数型で効率的な計算を行うにはそのまま適用するのでなく、一捻りした方が良いかな、と感じていました。

Elixirのデータ構造としてはリストに特化して最適化されている印象があり、Mapなどのデータ構造やETSのような機構を使うと、それなりのオーバーヘッドがあることが想像できるので、やはり、リストを上手く使いたい気持ちがあります。

動的計画法と一言に言っても数値型を複数個繰り返しながら使うだけで実現できるものから多次元配列が必要なものまで色々な問題があります。全てを取り上げるとQiitaの記事としては大長編になってしまうので、今回はかなり単純なもの(おそらく一番単純？)を取り上げたいと思います。

動的計画法とは

動的計画法(Wikipedia)に詳しい説明は譲りますが、複雑な問題を小さい部分問題に分解した上で、その結果をメモして再利用することで、無駄な処理を省けるようなアルゴリズムです。

同じような小さい問題が繰り返されるような、基本的に前の計算を利用して最適化を行うようなものに向いています。

DPに関しては興味がある人は、AtCoderにEducational DP Contest / DP まとめコンテストというDPの基本問題集のようなもので色んな種類の問題が解けるのでやってみて下さい。

適用できる問題

代表的な問題は

再帰的に数値を変えながら処理を繰り返すもの
- フィボナッチ数列など
複数個のものから最適な組み合わせで選択したい場合
- ナップザック問題など

などなどです。

Elixirで解いてみる

では、手続き型言語では動的計画法で解く問題を関数型っぽく(個人の所感)解いてみます。

フィボナッチ数列

再帰や動的計画法の練習で有名なフィボナッチ数列をElixirの再帰で書くと下記のような感じです。

defmodule Fibonacci do
  def fib(n) when n < 2 do
    n
  end
  def fib(n) do
    fib(n - 1) + fib(n - 2)
  end
end

これを Fibonacci.fib(5) で呼び出すと
fib(5) -> fib(4)+fib(3) -> (fib(3)+fib(2))+fib(3)) -> ((fib(2)+fib(1))+fib(2))+fib(3) ...
と最終的にfib(1)+fib(0)だらけになって、それぞれの処理に重複する関数が発生します。

これは正しく動きますが、絶対に書いちゃいけないプログラムです。末尾再帰にもなりません。

計算量

O-記法で表すと、これはO(2ⁿ)という非常に残念な計算量になります。

T(n) = T(n-1) + T(n-2)
　　= T(n-2) + T(n-3) + T(n-3) + T(n-4)
...
T(n) = 2・2・...2 = 2ⁿ

ちなみにこいつに100辺りを与えると、結果を待ってる間に漫画の単行本が一冊読めます。ネオジオCD並の処理速度ですね。ええ、そういう世代の人です。

関数型っぽくリファクタ

リストを効率的に使ってみます。
メモというか、伝言ゲーム的な前の計算の受け渡しですね。

defmodule Fibonacci2 do
  def fib(n) when n < 2 do
    n
  end
  def fib(n) do
    2..n |> Enum.reduce([1, 0], fn _, [a, b] -> [a+b, a] end) |> hd
  end
end

計算量

それぞれのfib(n)に対して1度の処理なのでO(N)になります。

比較

再帰とリスト利用をそれぞれを fib(50) で速度比較します。

iex(1)> :timer.tc(Fibonacci, :fib, [50]) |> elem(0) |> Kernel./(1_000_000)
749.452361
iex(2)> :timer.tc(Fibonacci2, :fib, [50]) |> elem(0) |> Kernel./(1_000_000)
5.0e-6

圧倒的ですね。
ちなみに、:timer.tc(モジュール名, 関数シンボル, 引数リスト) の戻りのタプルの1つ目の要素がマイクロ秒の処理時間なので、それを秒に直してます。

Mapも使ってみる(おまけ)

これ、かなりムズいですね。上手くやらないとMapを更新してくれない。

defmodule Fibonacci3 do
  defp create(dp, n) when n < 2 do
    Map.put(dp, n, n)
  end
  defp create(dp, n) do
    if not Map.has_key?(dp, n) do
      dp =
        if not Map.has_key?(dp, n-1) do
          create(dp, n-1)
        else
          dp
        end
      dp =
        if not Map.has_key?(dp, n-2) do
          create(dp, n-2)
        else
          dp
        end
      Map.put(dp, n, Map.get(dp, n-1) + Map.get(dp, n-2))
    else
      dp
    end
  end
  def fib(n) do
    dp = create(Map.new, n)
    Map.get(dp, n)
  end
end

[2020/12/23 追記]
@torifukukaiou さんがElixir その2 Advent Calendar 2020 23日目でリファクタしてくれました！感謝！
・・・しかし、速度はオリジナル(これ)が一番速いというのはパターンマッチとかのオーバーヘッドですかね？

計算量

例えば Fibonacci3.fib(5) を呼んだ場合、create(%{}, 5)の最初のdpの再バインド(n-1)から始まる再帰で全てMapに入ります。0はcreate(%{}, 2)の2回目の再バインド(n-2)で入っています。ログ出して確認しましたが、計算自体はcreateが0~Nで1回ずつ呼ばれO(N)の計算量になります。

比較

リストのバージョンとの比較をしてみます。再帰は予選でお亡くなりになりました。

iex(3)> :timer.tc(Fibonacci3, :fib, [50]) |> elem(0)
33
iex(4)> :timer.tc(Fibonacci2, :fib, [50]) |> elem(0)
9
iex(5)> :timer.tc(Fibonacci3, :fib, [100]) |> elem(0)
138
iex(6)> :timer.tc(Fibonacci2, :fib, [100]) |> elem(0)
9
iex(7)> :timer.tc(Fibonacci3, :fib, [1000]) |> elem(0)
1102
iex(8)> :timer.tc(Fibonacci2, :fib, [1000]) |> elem(0)
100
iex(9)> Fibonacci2.fib(1000)
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

[2020/12/17更新]: 秒からマイクロ秒にしました。
やはりオーバーヘッドがあるのか、Mapの方が多少遅いですね。気にならない程度の差ですが･･･。関数呼び出しもオーバーヘッドになっていると思います。書き方が悪いのもあるかも知れない。リストのバージョンはコードも簡潔です。MapはCNNのコンボリューションでも使ったんですが、どうしても重めになってしまいます。Elixir初心者なので、下手くそなのかも知れませんが。

桁数すごいな･･･。これちゃんと計算できてんのかなー。

まとめ

今回の記事では動的計画法の一部を扱いましたが、関数型では手続き型の順次処理の"手順"にこだわらずに関数型の利点を活かしたアルゴリズムやデータの使い方ができる場合、そちらの方が効率が良いと思います。また、そういうやり方を考えるのは面白いし、「純粋関数型アルゴリズム」のような関数型に最適化されたアルゴリズムが発展していくと面白い気がします。

ちなみに、参考記事を否定するつもりではなく、リストで解決できるなら、その方が良いかも？という程度です。
本当はDPまとめコンテストのB問題までは解説しようかと思いましたが、執筆時間と記事の文量の問題でこの辺で、時間あればまた今度、という感じで。

B問題に関しては1〜K個のzipした情報をreduceで渡しながら引き継いでいけばできるかと思います。
0/1ナップザック問題も同様に、空間計算量を減らしたバージョンで、重さ分頭を削ったリストで計算してガッチャンコしたりすればリストで同じ計算量を実現できるかなぁ、とか(<-説明雑過ぎ)。

どうしても多次元配列を使わないとできないパターンはもう少し頭使わないとですが。

それでは来年もElixirを盛り上げて行きましょう(お前はもっとやれよ、と言われそうですがｗ）。

17日目は @dimanche さんのElixirでナンプレを解くコードを書いてみたです。

動的計画法を使う問題をElixirで関数型っぽく解いてみる