Elixirで動的計画法（DP）を実装してみた（Goとの比較つき）

この記事はElixir Advent Calendar 2020の7日目です。

こんにちは @Koyo です！普段は面白法人カヤックでゲームサーバ書いています
最近趣味で 問題解決力を鍛える!アルゴリズムとデータ構造 という本を読み、そこに出てきた有名なアルゴリズムである「動的計画法」をみて、Elixirで実装するにはどうするんだ・・・！？という疑問が出てきたので実際にやってみました。

※ Elixirはイミュータブルかつ制御構文としてのforがないので配列の値を逐次的に更新するのはちょっと頭を捻る必要があります

ナップサック問題

動的計画法 とはざっくり言うと問題に対して漸化式を定義してそれを帰納的に解いていくことで効率よく問題を解く手法です。

動的計画法を適用して効率よく解ける典型問題としてナップサック問題が有名です。今回はこの問題を題材にしてみようと思います。

$n$ 個の品物があり、$i$ 番目の品物のそれぞれ重さと価値が $\rm{weight}[i], \rm{value}[i]$ となっている ($i = 0, 1, ..., n-1$)。
これらの品物から重さの総和が $W$ を超えないように選んだときの、価値の総和の最大値を求めよ。

これに対するDP漸化式は以下となります。

$\rm{dp}[i+1][w]$ := $i$ 番目までの品物の中から重さが $w$ を超えないように選んだときの、価値の総和の最大値

• 品物 $(\rm{weight}[i], \rm{value}[i])$ を選ぶ場合 ($w \ge \rm{weight}[i]$ の場合のみ)
  $$\rm{dp}[i+1][w] = \rm{dp}[i][w-\rm{weight}[i]] + \rm{value}[i]$$

• 品物 $(\rm{weight}[i], \rm{value}[i])$ を選ばない場合
  $$\rm{dp}[i+1][w] = \rm{dp}[i][w]$$

また初期条件はこちら

$$\rm{dp}[0][w] = 0　(w = 0, 1, \dots, W)$$

※問題の説明に関しては @drken さんの記事 が分かりやすいのでオススメです！
上記の説明もこちらの記事から引用させていただきました！

Goで解く

まずGoで解いてみます！
※入力は [w, v] の配列（つまり二次元配列）で表現されるとして解きます。

package main

import (
    "fmt"
    "math"
    "time"
)

func main() {
    var (
        input     = [][]int{[]int{2, 3}, []int{5, 85}, []int{1, 2}, []int{3, 6}, []int{2, 1}, []int{1, 3}}
        inputHuge = [][]int{}
    )
    for i := 0; i < 50000; i++ {
        inputHuge = append(inputHuge, input...)
    }

    var (
        start   = time.Now()
        res     = knapsack(inputHuge, 9)
        elapsed = time.Since(start)
    )
    fmt.Printf("elapsed:%v, res:%+v\n", elapsed, res)
}

func knapsack(items [][]int, maxW int) int {
    var (
        N  = len(items)
        dp = make([][]int, N+1)
    )
    for i := range dp {
        dp[i] = make([]int, maxW+1)
    }

    for i := 0; i < N; i++ {
        var (
            w = items[i][0]
            v = items[i][1]
        )
        for j := 0; j < maxW+1; j++ {
            if w <= j {
                dp[i+1][j] = int(math.Max(float64(v+dp[i][j-w]), float64(dp[i][j])))
            } else {
                dp[i+1][j] = dp[i][j]
            }
        }
    }

    return dp[N][maxW]
}

実行結果はこんな感じです。流石Goは速い！
答えも [5, 85] １つと [1, 3] を４つ取れば最大の 97 になるので合ってそうですね。

$ go run dp/main.go 
elapsed:71.8844ms, res:97

Elixir で解く

さて、Elixirで解いてみます。Goでは配列定義してforループして逐次更新していけば良かったですが、Elixirではそれができません！
どうやって解こうかな・・・ワクワク・・・

まず動的計画法せずに再帰で解いてみる

まず単に再帰だけで解いてみます

defmodule Dp do
  def solve([[]], _), do: 0
  def solve([[w, _]], max_w) when w > max_w, do: 0
  def solve([[w, v]], max_w) when w <= max_w, do: v

  def solve([[w, _] | items], max_w) when w > max_w do
    solve(items, max_w)
  end

  def solve([[w, v] | items], max_w) when w <= max_w do
    max(v + solve(items, max_w - w), solve(items, max_w))
  end
end

# これだと重すぎて死ぬのでメモ化とか必要
input = [[2, 3], [5, 85], [1, 2], [3, 6], [2, 1], [1, 3]]
input_huge = 1..200 |> Enum.reduce([], fn _, acc -> acc ++ input end)

Dp.solve(input_huge, 9) |> IO.inspect()

Elixirは関数の引数にパターンマッチを採用できるので分岐がなくシンプルになりますね！
ただこれだと、上記のような N=1200 の入力でも終わりません（Goの入力は N=300000 なのでその差は歴然）
それもそのはず、メモ化してないので同じ引数でも再度計算する必要があり入力が大きくなると計算量が爆発的に増大しちゃいますね。

ETS使ってみる

DPするにはメモ化する必要がありますが、Elixirで状態を扱うには一工夫必要です。Agentモジュールなど、プロセスに状態を持たせる手法もありますが、今回はETSを使ってみます。
ETS は Erlang Term Storage の略で、Elixirの土台であるErlangに標準で組み込まれているインメモリストレージです。
詳しい説明は以下をどうぞ。
https://elixirschool.com/ja/lessons/specifics/ets/

ETSを使ってDPでナップザック問題を解くとこんな感じです。
Enum.with_index/1 を使うと、indexを振ってくれるので便利！

defmodule Dp do
  def solve(items, max_w) do
    :ets.new(__MODULE__, [:set, :protected, :named_table])

    0..max_w |> Enum.each(fn w -> insert(0, w, 0) end)

    for {[w, v], i} <- Enum.with_index(items), j <- 0..max_w do
      if w <= j do
        res = max(lookup(i, j - w) + v, lookup(i, j))
        insert(i + 1, j, res)
      else
        insert(i + 1, j, lookup(i, j))
      end
    end

    lookup(length(items), max_w)
  end

  defp insert(i, w, res) do
    :ets.insert(__MODULE__, {{i, w}, res})
    res
  end

  defp lookup(i, w) do
    [{_, res}] = :ets.lookup(__MODULE__, {i, w})
    res
  end
end

Erlangの:timerモジュールを使って、雑に計測してみるとこんな感じ。

input = [[2, 3], [5, 85], [1, 2], [3, 6], [2, 1], [1, 3]]
input_huge = 1..50000 |> Enum.reduce([], fn _, acc -> acc ++ input end)

:timer.tc(Dp, :solve, [input_huge, 9]) |> IO.inspect()

$ elixir dp_ets.exs
{3685769, 97}

:timer モジュールはマイクロ秒単位で返してくるので、大体3.6sくらいで解けてそう。

※なお筆者の実行環境は以下です。

• Windows10
  • WSL(Windows Subsystem for Linux)
• Erlang/OTP 22
• Elixir 1.9.4 (compiled with Erlang/OTP 21)

Mapでも解ける

とここまでの結果をElixirコミュニティに共有したところ、@piacerex さんがより効率的なコードを書いてくださったので紹介します。
そもそも1関数で完結できるので、ETS使う必要はなく単なるMapを使うことでより高速にできるとのこと（そりゃそうでしたｗ）。

Mapをこんな感じの構造にしてしまえば、2次元配列のように扱えますね！

iex> table = %{ 0 => 0..9 |> Enum.reduce( %{}, & Map.put( &2, &1, 2 ) ) }
%{
  0 => %{
    0 => 2,
    1 => 2,
    2 => 2,
    3 => 2,
    4 => 2,
    5 => 2,
    6 => 2,
    7 => 2,
    8 => 2,
    9 => 2
  }
}
iex> table[ 0 ][ 5 ]
2

defmodule Dp do
  def solve_map(items, max_w) do
    table = %{0 => 0..max_w |> Enum.reduce(%{}, &Map.put(&2, &1, 0))}

    table =
      Enum.reduce(Enum.with_index(items), table, fn {[w, v], i}, table ->
        add_i =
          0..max_w
          |> Enum.reduce(table[i], fn j, tmp ->
            add_j =
              if w <= j do
                max(table[i][j - w] + v, table[i][j])
              else
                table[i][j]
              end

            Map.put(tmp, j, add_j)
          end)

        Map.put(table, i + 1, add_i)
      end)

    table[length(items)][max_w]
  end
end

同じように以下のコードを加えて測定してみました

input = [[2, 3], [5, 85], [1, 2], [3, 6], [2, 1], [1, 3]]
input_huge = 1..50000 |> Enum.reduce([], fn _, acc -> acc ++ input end)

:timer.tc(Dp, :solve_map, [input_huge, 9]) |> IO.inspect()

$ elixir dp/dp7.exs
{1670776, 97}

大体1.6秒くらいかな。筆者の実行環境ではETSより約2.2倍速くなってそうでした。

まとめ

ElixirでもDPはできる！ということが分かったのは個人的に大きな収穫でした！
C++やGoなどで書かれたコードを移植する際にもいくつか使えそうなテクが見つかったので、今後何かに使えそうです！

ETSを使ったりMap使ったりして動的計画法を解いてみましたが、結果的には実行速度はETS > Map でした。ただETSはグローバルなインメモリストレージとして使えるので、そういうメモ化が必要なDPであれば効果的に使えそうですね（今回のナップザック問題ではMapで十分でした）。

Goと比較してみると流石にGoの方が速いですね。もっとElixirの特性（並列性能の高さとか）を活かしたいい解き方があるのかもですが、ザっと試した感じではこれが限界でした（Flowというライブラリ使って改変も試してみたけどDPテーブル埋める順序が大事なので工夫しないと難しそう）。

ただこの記事でアルゴリズムに与えた入力はDPテーブルのNが圧倒的に大きくWが小さいので、NとWのバランス揃えてみるとまた結果変わるかもです。
また今回は計算速度に関しては厳密な測定をしたいわけではないので、大まかな傾向だけしか把握してませんがあしからず。

ちなみに状態を管理するのにETSではなくAgentを使って解くパターンもありますが、@piacerex さんが実装したところ、ETSの方が高速みたいでした。
みなさんも興味あれば色んな解法試してみてください！

次回は @im_miolab さんの記事です！