【実装コード有り】ElixirのMapSet(集合)の使い方と集合カバー問題を解くまで

Setは非推奨

元々、Elixirに実装されていたSetという集合のモジュールは現在、非推奨となっており
MapSetを使ってくれよなと公式が言っている

なのでよほどの理由がない限りはMapSetを使えばいいんじゃないかなと

MapSetの使い方

MapSetモジュールを使うことで集合を表現することが可能
集合はリストと異なり

• 同じデータを持つことができない

という特徴がある

lst = [1,1,2,3,4,4,5,6,7] #重複ok
set_ = [1,2,3,4,5,6,7] #重複は許可されない

新規集合の作成
MapSet.newメゾットを使うことで作成可能

iex> new_set = MapSet.new([1,2,3])
#MapSet<[1, 2, 3]>

#値の型は自由っぽい
iex> new_set = MapSet.new([:a, 1, false])
#MapSet<[1, :a, false]>

既存の集合への追加
MapSet.putメゾットを使う

new_set = MapSet.new([1,2,3])
iex> MapSet.put(new_set, 4)
#MapSet<[1, 2, 3, 4]>

集合同士の結合(和集合)
MapSet.unionメゾットを使う

a_set = MapSet.new([1,2,3])
b_set = MapSet.new([2,4,5])

iex> MapSet.union(a_set, b_set)
#MapSet<[1, 2, 3, 4, 5]>

集合同士の引き算(差集合)
MapSet.differenceメゾットを使う

a_set = MapSet.new([1,2,3])
b_set = MapSet.new([2,4,5])

#[1,2,3] - [2,4,5] ([4,5]はa_setに存在しないので影響なし)
iex> MapSet.difference(a_set, b_set)
#MapSet<[1, 3]>

両方の集合に含まれている要素を求める(積集合)
MapSet.intersectionメゾットを使う

a_set = MapSet.new([1,2,3])
b_set = MapSet.new([2,3, 4,5])

iex> MapSet.intersection(a_set, b_set)

集合の大きさの取得
MapSet.sizeメゾットを使う

a_set = MapSet.new([1,2,3])
iex> MapSet.size(a_set)
3

こいつで何ができるのか

一例として集合カバー問題というテーマに取り組む
これから以下の地域にそれぞれ野菜を届ける必要がある

#岐阜, 愛知, 三重, 京都, 静岡
delivery_regions = MapSet.new([:gihu, :aichi, :mie, :kyoto, :shizuoka])

現在、この地域に配達可能な業者が以下の5つ
それぞれの集合には配達可能な地域を記述してある

companies = %{
  neko: MapSet.new([:gihu, :mie, :shizuoka]),
  inu: MapSet.new([:mie, :kyoto]),
  saru: MapSet.new([:gihu, :kyoto, :aichi]),
  kani: MapSet.new([:mie, :aichi]),
  tori: MapSet.new([:aichi, :kyoto])
}

現状では全5地域に配達可能な企業がないため複数の企業に配達を依頼する必要がある
ではどの組み合わせを考えれば最も少ない企業数で配達が可能か
これが集合カバー問題といわれるものの一例です

Elixirでの実装

先にコードと実行結果をお見せします

defmodule Algo do
  def set_optimizer(delivery_regions, stations), do: _set_optimizer(delivery_regions, stations, MapSet.new())
  defp _set_optimizer(delivery_regions, stations, accum) do
    case delivery_regions == MapSet.new() do
      true -> accum
      false ->
        {best, states_coverted} = _set_update(delivery_regions, stations, Map.keys(stations), nil, MapSet.new())
        _set_optimizer(MapSet.difference(delivery_regions, states_coverted), stations, MapSet.put(accum, best))
    end
  end
  
  defp _set_update(_, _, [], best, accum), do: {best, accum}
  defp _set_update(need, stations, [head | tail], best, accum) do
    coverd = MapSet.intersection(need, stations[head])
    case MapSet.size(coverd) > MapSet.size(accum) do
      true -> _set_update(need, stations, tail, head, coverd)
      false -> _set_update(need, stations, tail, best, accum)
    end
  end
end

結果では:nekoと:saruの業者に頼むが良いと出ている
確かにそうだね

delivery_regions = MapSet.new([:gihu, :aichi, :mie, :kyoto, :shizuoka])
companies = %{
  neko: MapSet.new([:gihu, :mie, :shizuoka]),
  inu: MapSet.new([:mie, :kyoto]),
  saru: MapSet.new([:gihu, :kyoto, :aichi]),
  kani: MapSet.new([:mie, :aichi]),
  tori: MapSet.new([:aichi, :kyoto])
}
res = Algo.set_optimizer(delivery_regions, companies)
IO.inspect(res)
#result: #MapSet<[:neko, :saru]>

#全ての地域が含まれている
#:neko => [:gihu, :mie, :shizuoka]
#:saru => [:gihu, :kyoto, :aichi]

このモジュールは2つの再帰で動かしている
set_optimizerの関数で配達したい地域が全て満たされているかを判定させており
そうでない場合に再び再帰が行われる

set_optimizer

def set_optimizer(delivery_regions, stations), do: _set_optimizer(delivery_regions, stations, MapSet.new())
  defp _set_optimizer(delivery_regions, stations, accum) do
    #第1引数(配達したい地域)が空なら終了
    case delivery_regions == MapSet.new() do
      true -> accum
      false ->
        {best, states_coverted} = _set_update(delivery_regions, stations, Map.keys(stations), nil, MapSet.new())
        #_set_updateの結果を配達したい地域から引く
        _set_optimizer(MapSet.difference(delivery_regions, states_coverted), stations, MapSet.put(accum, best))
    end
end

_set_update

defp _set_update(_, _, [], best, accum), do: {best, accum} #companiesの列挙が終わった時に終了
defp _set_update(need, stations, [head | tail], best, accum) do
  #accum(1つ前の値)との差分をみる
  coverd = MapSet.intersection(need, stations[head])
  case MapSet.size(coverd) > MapSet.size(accum) do
    true -> _set_update(need, stations, tail, head, coverd) #頼む業者を更新&配達可能地域を保持
    false -> _set_update(need, stations, tail, best, accum) #更新なし
  end
end

こんなところでしょうか
最近の悩みはifとcaseの使い分けどうしようかという問題
今回のようなtrue, falseだけの単純な分岐ではifを使うべきとは思いつつも
個人的な可読性についてはcaseの方が上かなと

ただunlessには人権がない

Elixirでダイクストラ法を実装して最短経路を求めるまで

グラフと最短経路

こんなグラフのネットワークがあったとする

Start, A, B, Goalをそれぞれノードといい
6,2,3...のような数字をエッジの重み(ここでは距離)という

StartからGoalへの最短経路は見て分かるように

Start -> B -> A -> Goal

になるかと思う

これがこのグラフでのStartからGoalへの最短経路となる

ではこの最短経路をアルゴリズム使って求められへんの？っていう賢い人が現れる
それで開発されたのがダイクストラ法というアルゴリズム

しかし説明をすると長くなる & 図が大量に必要なので省略する
(すでに書籍や先駆者の有志の方が最高に分かりやすい説明をしてくださっているため)

「ダイクストラ法　解説」　などで検索してみてください

データ構造について

まずはデータの構造を定める
ここ数日、アルゴリズムの実装をして感じていることは
アルゴリズムのロジックを組む際の難易度はデータ構造に大きく依存するということ

シンプルなデータ構造で表現できた場合にはコードはあまり複雑にならない
データ構造に無駄があったり、欠陥があるとその分、コード部分で苦労をする

「このデータ構造が最もふさわしい」というベストアンサーは決めにくいが
シンプルであればシンプルであるほど良いというのが自分の中での答えかなと思ってます

ダイクストラ法に必要な3つのデータ

• グラフ情報(graph)
• コスト情報(costs)
• 親ノード情報(parents)

をそれぞれ以下のように定めた(書籍を参考に実装した)

グラフ情報

#それぞれのノードがどのノードに接続しているか(距離も付与)
#start: %{a: 6, b: 2},
#start --6--> a
#start --2--> b ということを表現している
graph = %{
  start: %{a: 6, b: 2},
  a: %{fin: 2},
  b: %{a: 3, fin: 5},
  fin: %{}
}

コスト情報

#startから接続しているノードまでの距離
#startと接続していないノードにはinfinityをセット
costs = %{
  a: graph.start.a,
  b: graph.start.b,
  fin: :infinity
}

親ノード情報

#startから接続しているノードのノード名
#そのほかはnilとしておく
parents = %{
  a: :start,
  b: :start,
  fin: nil
}

1つにまとめられそうな気もするが、あまり複雑化させるよりはいくつかに分別して方が経験上良い
データの準備は以上で次にコードを実装する

Elixirでのダイクストラ法の実装

まずは全体のコードをお見せします

defmodule Algo do
  def dijkstra(graph, costs, parents, processed) do
    node = _search_minimize_cost_in_graph(costs, processed)
    case node do
      :empty -> {costs, parents}
      _ ->
        neighbors = graph[node]
        {n_costs, n_parents} = _node_update(node, Map.keys(neighbors), costs[node], costs, neighbors, parents)
        dijkstra(graph, n_costs, n_parents, processed ++ [node])
    end
  end

  defp _node_update(_, [], _, costs, _, parents), do: {costs, parents}
  defp _node_update(node, [head | tail], cost, costs, neighbors, parents) do
    new_cost = cost + neighbors[head]
    if costs[head] > new_cost do
      n_costs = Map.put(costs, head, new_cost)
      n_parents = Map.put(parents, head, node)
      _node_update(node, tail, cost, n_costs, neighbors, n_parents)
    else
      _node_update(node, tail, cost, costs, neighbors, parents)
    end
  end
  
  def creater(res, start_atom, end_atom) do
    _creater(res, start_atom, end_atom, [end_atom])
  end
  def _creater(res, start_atom, next_atom, accum) do
    end_val = res[next_atom]
    if end_val == start_atom do
      [start_atom] ++ accum
    else
      _creater(res, start_atom, end_val, [end_val] ++ accum)
    end
  end

  defp _search_minimize_cost_in_graph(costs, processed) do
    rest_node = Map.keys(costs) |> Enum.filter(fn x -> x not in processed end)
    case rest_node == [] do
      true -> :empty
      false -> Enum.reduce(rest_node, :infinity, fn x, accum ->
        if accum > costs[x] do
          x
        else
          accum
        end
      end)
    end
  end
end

この先の説明部分については完全に自己満足なので
結果を先にお見せします

graph = %{
  start: %{a: 6, b: 2},
  a: %{fin: 1},
  b: %{a: 3, fin: 5},
  fin: %{}
}

costs = %{
  a: graph.start.a,
  b: graph.start.b,
  fin: :infinity,
}

parents = %{
  a: :start,
  b: :start,
  fin: nil
}

res = Algo.dijkstra(graph, costs, parents, [])
#res: {%{a: 5, b: 2, fin: 6}, %{a: :b, b: :start, fin: :a}}

{_a, b} = res
root = Algo.creater(b, :start, :fin)
#root: [:start, :b, :a, :fin]

別のグラフで試してみる

graph = %{
  start: %{a: 6, b: 2, c: 1},
  a: %{fin: 1},
  b: %{a: 3, fin: 5},
  c: %{a: 6, fin: 2},
  fin: %{}
}

costs = %{
  a: graph.start.a,
  b: graph.start.b,
  c: graph.start.c,
  fin: :infinity,
}

parents = %{
  a: :start,
  b: :start,
  c: :start,
  fin: nil
}

res = Algo.dijkstra(graph, costs, parents, [])
{_a, b} = res
root = Algo.creater(b, :start, :fin)

#root: [:start, :c, :fin]

良い感じですね 実装についてはここまでです
どんな動きをしているかが気になる方は以下をどうぞ

作成したモジュールについて

最短経路を求めるこのモジュールは4つの関数から成り立っている

• dijkstra(メイン関数)
• _node_update(条件に従いノード情報を更新する関数)
• creater(dijkstraの結果から最短経路を作成する関数)
• _search_minimize_cost_in_graph(最も手数が少ないノードを探索する関数)

順にコードを見ていく

dijkstra

def dijkstra(graph, costs, parents, processed) do
    #隣接しているノードの中で最も距離が近い(コストが低い)ノードを探索
    node = _search_minimize_cost_in_graph(costs, processed)
    case node do
      #もう探索できるノードがない場合
      :empty -> {costs, parents}
      _ ->
        #探索した最もコストの低いノードに隣接しているノードを取得(マッチ)
        neighbors = graph[node]
        #ノード情報をアップデート
        {n_costs, n_parents} = _node_update(node, Map.keys(neighbors), costs[node], costs, neighbors, parents)
        #今調べたノードを探索済み(accumに追加)して再帰
        dijkstra(graph, n_costs, n_parents, processed ++ [node])
    end
end

_node_update

#探索できるノードが無くなったら終了
defp _node_update(_, [], _, costs, _, parents), do: {costs, parents}
defp _node_update(node, [head | tail], cost, costs, neighbors, parents) do
  #次のノードまでの合計距離
  new_cost = cost + neighbors[head]
  #現時点で発見されているコストよりも別ルートの方が最短かどうか
  if costs[head] > new_cost do
    #コスト情報と親情報を上書き
    n_costs = Map.put(costs, head, new_cost)
    n_parents = Map.put(parents, head, node)
    _node_update(node, tail, cost, n_costs, neighbors, n_parents)
  else
    _node_update(node, tail, cost, costs, neighbors, parents)
  end
end

_node_updateが呼ばれる以前にこんなことが起きている

• Startから最もコストが低いノードはBノード
• Bノードに隣接しているノードを全て取得(Aとfin)

この情報を元に_node_updateが呼ばれる
例えばBノードからAノードへの探索をする場合には元々のコストは以下のようになっている

ノード名	距離(コスト)
A	6
B	2
fin	infinity

しかし、_node_updateが呼ばれ現状のAルートへの道のりよりも
Bを経由してAに行った方が近いことが分かる

head = :a #Aノード
new_cost = cost + neighbors[head]
#new_cost = 2 + 3 -> 5
#このコストは現状の6よりも小さい

従ってコストを更新する

ノード名	距離(コスト)
A	5
B	2
fin	infinity

さらに親ノードの情報も更新する
更新前

ノード名	距離(コスト)
A	start
B	start
fin	infinity

更新後

ノード名	距離(コスト)
A	B
B	start
fin	nil

creater
この関数についてはオマケなのであまり深く語る部分はない
dijkstraの戻り値の第2要素を使ってresからrootを生成しているだけ

res = %{a: :b, b: :start, fin: :a}
root = Algo.creater(res)

iex> root
[:start, :b, :a, :fin] #道順になっている

_search_minimize_cost_in_graph

defp _search_minimize_cost_in_graph(costs, processed) do
  #探索済みのノードを破棄
  rest_node = Map.keys(costs) |> Enum.filter(fn x -> x not in processed end)
  case rest_node == [] do
    true -> :empty
    #[:a, :b, :fin]から最小コストを持つノードを探索
    false -> Enum.reduce(rest_node, :infinity, fn x, accum ->
      if accum > costs[x] do
        x
      else
        accum
      end
    end)
  end
end

長くなってしまいましたが、おそらくコード自体はもっと短くできるかと思います
とりあえずは実装してみるを原動力に書いているのでその点はご了承ください。リファクタリングはElixir力が高まってからチャレンジしてみようと思います

【サンプルコード有り】ElixirとFakerを使ってサンプルデータを作る方法

githubの探検中に面白いものを見つける

なんだこれは(褒め言葉

github.com
hexdocs.pm

Faker is a pure Elixir library for generating fake data.

fmfm...
どうやらフェイクデータを色々作れるライブラリだそうです
公式ドキュメントを見てみると

• 名前
• アドレス
• 地名
• ポケモン etc...

など様々なフェイクデータが用意されている模様

Fakerのインストール

今回は作成したデータのcsv出力までを行いたいのでついでにcsvもインストールしておく
いつも通りに新規プロジェクトを作成する

mix new create_fake

./create_fake/mix.exsのdepsに以下を追記

#この2つを追加
defp deps do
    [
      {:faker, "~> 0.12"},
      {:csv, "~> 2.3"},
    ]
  end

いつも通りコマンドを叩き、外部ライブラリをダウンロードする

cd create_fake
mix deps.get

さらにtest/test_helper.exsに以下を追加

Faker.start()

これで準備は完了

とりあえずデータを作ってみる

まずは存在しない人間の情報を作ってみることにした
持たせる情報は

• email
• 地域
• 名前(ファーストネームとラストネーム)
• 電話番号
• 好きな食べ物
• 年齢

上記の6つでマップ形式でサンプルデータを作成する

FakerとErlangモジュールの:randを使ってコードを書くとこんな感じに

iex> %{
  email: Faker.Internet.email(),
  city: Faker.Address.En.city(),
  name: Faker.Name.En.first_name() <> " " <> Faker.Name.En.last_name(),
  phone: Faker.Phone.EnUs.phone(),
  food: Faker.Food.dish(),
  age: trunc(:rand.uniform() * 100)
}

%{
  age: 26,
  city: "East Malachi",
  email: "dorcas1964@bergstrom.biz",
  food: "Fettuccine Alfredo",
  name: "Aniya Herzog",
  phone: "957/391-6739"
}

うまく生成された
もう一度、実行してみると全く別のデータが作成された

%{
  age: 39,
  city: "Nolan",
  email: "ashly.romaguera@johnson.org",
  food: "Chilli con carne",
  name: "Marta Yost",
  phone: "409.287.2291"
}

このままだと単一のデータしか生成されないので
指定数分のデータをリストに格納して作成できるように変更

defmodule CreateMock do
  def user_info(num) do
    1..num |> Enum.map(fn _ -> _user_info() end)
  end
  defp _user_info do
    %{
      email: Faker.Internet.email(),
      city: Faker.Address.En.city(),
      name: Faker.Name.En.first_name() <> " " <> Faker.Name.En.last_name(),
      phone: Faker.Phone.EnUs.phone(),
      food: Faker.Food.dish(),
      age: trunc(:rand.uniform() * 100) #Erlangモジュールを使って乱数を生成
    }
  end
end

呼び出してみると良さげに生成されている

iex(11)> CreateMock.user_info(3)
[
  %{
    age: 40,
    city: "Nicolas",
    email: "david2068@langosh.org",
    food: "Philadelphia maki",
    name: "Gwen Weber",
    phone: "930.422.1730"
  },
  %{
    age: 52,
    city: "Bayer",
    email: "yvonne2077@reynolds.biz",
    food: "Linguine with clams",
    name: "Favian Cummings",
    phone: "421/864-1117"
  },
  %{
    age: 86,
    city: "Haley",
    email: "gracie2021@hettinger.info",
    food: "Cheeseburger",
    name: "Margarette Ratke",
    phone: "(867) 614-8718"
  }
]

次にありそうなテストの成績データを生成してみる
持たせる情報は

• 名前
• 点数
• 科目名

の3つ

もう説明することは特にないのでコードと結果を先にお見せします

defmodule CreateMock do
  #デフォルトでmath(数学)を設定
  def exam_info(num, subject \\ "math") do
    1..num |> Enum.map(fn _ -> _exam_info(subject) end)
  end
  defp _exam_info(subject) do
    %{
      name: Faker.Name.En.first_name() <> " " <> Faker.Name.En.last_name(),
      score: trunc(:rand.uniform() * 100),
      subject: subject
    }
  end
end

iex(12)> CreateMock.exam_info(3)
[
  %{name: "General Wisoky", score: 55, subject: "math"},
  %{name: "Alessia Cummings", score: 23, subject: "math"},
  %{name: "Lilian Senger", score: 43, subject: "math"}
]

いいですね
フェイクデータの作成に関してはここで終了です
せっかくなのでcsvに書き出すことにします

生成したデータのcsvへの書き出し

生成したデータ(リストinマップ)の形式を
csvライブラリを使って書き出せるように指定形式の2次元のリストに変換します
ついでにheaderも挿入する

def output_data_to_csv(lst, header, file_name) do
    #ファイルを作成
    file = File.open!(file_name <> ".csv", [:write, :utf8])
    lst
      |> Enum.map(&(Enum.map(Map.to_list(&1), fn x ->
            {_, val} = x
            val
          end)
        ))
      |> List.insert_at(0, header)
      |> CSV.encode
      |> Enum.each(&IO.write(file, &1))
  end

少しトリッキー(自称)なのはこの部分

Enum.map(&(Enum.map(Map.to_list(&1), fn x ->
            {_, val} = x
            val
          end)
        ))

まずは作成したデータをMap.to_listを使ってまずはリスト形式に変換する

res = [
  %{name: "Kennith Kling", score: 18, subject: "math"},
  %{name: "Oliver O'Connell", score: 36, subject: "math"},
  %{name: "Nicole Gutkowski", score: 6, subject: "math"},
  %{name: "Blanche Deckow", score: 19, subject: "math"},
  %{name: "Lysanne Gleichner", score: 62, subject: "math"},
]

iex> Enum.map(res, &(Map.to_list(&1)))
[
  [name: "Kennith Kling", score: 18, subject: "math"],
  [name: "Oliver O'Connell", score: 36, subject: "math"],
  [name: "Nicole Gutkowski", score: 6, subject: "math"],
  [name: "Blanche Deckow", score: 19, subject: "math"],
  [name: "Lysanne Gleichner", score: 62, subject: "math"],
]

このままだとkeyの値も含まれているため取り除きたい

data = [name: "Kennith Kling", score: 18, subject: "math"],

このデータに対してIO.inspectをそれぞれの要素に実行するとタプルになっていることが分かる

iex> Enum.map(data, &(IO.inspect(&1)))
{name: "Kennith Kling"}
{score: 18}
{subject: "math}

なのでパターンマッチを使ってvalueのみを取り出す必要があり
こんなコードになったわけです

Enum.map(&(Enum.map(Map.to_list(&1), fn x ->
            {_, val} = x
            val
          end)
        ))

あとはcsvのドキュメントに従ってheaderを追加して書き出しているだけです
呼び出してみます

iex> fake_data = CreateMock.exam_info(20)
iex> CreateMock.output_data_to_csv(fake_data, ["name", "score", "subject"], "score")
:ok

無事にscore.csvが生成されました

name,score,subject
Kennith Kling,18,math
Oliver O'Connell,36,math
Nicole Gutkowski,6,math
:
:
Blanche Deckow,19,math

これうまく使えれば、勉強会とかでのデータ準備がめちゃくちゃ楽になりますね

Elixirでqueue使って幅優先探索を実装する

Elixirにqueueがなかった件

しかし、Erlangには用意されていた
Erlangの公式ドキュメントにばっちしqueueについて記述されている
Elixirで解決できない時はErlangのドキュメントを見るというのは本当ですね

Elixirからのqueueの使い方

新規のqueue作成
2つのリストを持つタプルの形式で値が返ってくる

que = :queue.new()

iex> que
{[], []}

queueに新たなデータを追加

new_que = :queue.in("okb", que)

iex> new_que
{["okb"], []}

先頭に待ち構えているデータの確認

iex> :queue.get(new_que)
"okb"

.getメゾットでは取得したデータが元のqueueに残っているままなので
取得したデータが削除されるようにするには以下のようにする

iex(12)> :queue.out(new_que)
{{:value, "okb"}, {[], []}}

取得に成功するとタプルの第1要素に:valueというタプルと共に取得した値が返ってくる
第2要素には取得後のqueueが返ってくる(今取得した値は含まれていない)

こいつにパターンマッチさせるにはこんな感じでいける

{{:value, value}, rest} = res
iex> value
"okb"

iex> rest
{[], []}

基本的に使うのはこのあたりなんじゃないかと勝手に思ってます
以上を踏まえてElixirで幅優先探索を実装します

ゆるく分かる幅優先探索について

すでにもっと分かりやすく解説してくださっている記事などたくさんあるのでざっくりと

僕の友人にプログラマーがいるか知りたいとします
この場合にどのように調べていくべきでしょうか

まずは連絡の取れる友人に一通り聞いて回り、プログラマーがいるかどうか確認します
もしこの時点でプログラマーを発見できれば探索は終了です(試行回数:1)

しかし、友人からプログラマーを発見できなかった場合は次の試行に移ります
次の手は自分の友人の友人にプログラマーがいるかどうかを確認します
友達の友達ってやつですね
この時点でプログラマーを発見できれば探索は終了です(試行回数:2)

見つからなかった場合は友達の友達の友達をあたります
この試行を発見できるまで、もしくは試行回数が上限に達するまで行います(試行回数:n)

このようにまずは近い(友人)ところを全て調べて
次に遠い(友人の友人)ところを順次、調べていくというのが
幅優先探索だと思っています

幅優先探索にはグラフが必要不可欠
友人関係というネットワークをグラフを使って表現するとこのような図になる

またグラフをデータで表現するとこんな感じの構造になる

friends = %{
  okb: [:a, :b, :c, :d],
  a: [:e],
  b: [], #友人がいない(悲しいね)
  c: [:e, :f],
  d: [:f],
  e: [],
  f: [:g],
  g: []
}

Elixirで書いてみる

bfsというヘルパー関数を用いて中心のネットワーク位置を決定している
要は誰を中心として探索を行うかということを決めている

defmodule Algo do
  def bfs(graph, center, target) do
    #中心地点を決定し、queueを新規作成して追加
    que = :queue.in(graph[center], :queue.new())
    _bfs(graph, target, que)
  end
  defp _bfs(graph, target, que) do
    #queueから値を取り出して判定
    case :queue.out(que) do
      {{:value, val}, rest} ->
        if target in val do
          #対象のデータが見つかれば終了
          {:exist, target}
        else
          #取得したリストの要素を1つずつqueueに追加していく
          next_que = Enum.reduce(val, rest, fn key, que -> :queue.in(graph[key], que) end)
          _bfs(graph, target, next_que)
        end
      #queueが空になったら終了
      {:empty, _} -> :not_found
    end
  end
end

呼び出しはこんな感じになる

#グラフの用意(もっと面白いやつを作ればよかった)
graph = %{
    okb: [:a, :b, :c],
    b: [:d, :e],
    a: [:e],
    c: [:f, :g],
    d: [],
    e: [],
    f: [],
    g: []
}

res = Algo.bfs(graph, :okb,:f)
IO.inspect(res)

#result: {:exist, :f}

いつものように簡易テストを行なってみる

tests = [
  Algo.bfs(graph, :okb, :f) == {:exist, :f},
  Algo.bfs(graph, :okb, :h) == {:not_found},
  Algo.bfs(graph, :b, :f) == {:not_found},
  Algo.bfs(graph, :c, :f) == {:exist, :f}
]

IO.inspect(tests)
#result:
#[true, true, true, true]

いい感じですね
ただこのままだと無向グラフの場合に無限ループを引き起こす可能性があるので
一度queueに追加された値はqueueに追加しないように処理を追加します
既に追加された値はどうかはaccumを使って判定しています

defmodule Algo do
  def bfs(graph, center, target) do
    que = :queue.in(graph[center], :queue.new())
    _bfs(graph, target, que, [])
  end
  defp _bfs(graph, target, que, accum) do
    case :queue.out(que) do
      {{:value, val}, rest} ->
        if target in val do
          {:exist, target}
        else
          #accumに存在していないデータのみ抽出
          val = Enum.filter(val, fn x -> x not in accum end)
          next_accum = val ++ accum
          next_que = Enum.reduce(val, rest, fn key, que -> :queue.in(graph[key], que) end)
          _bfs(graph, target, next_que, next_accum)
        end
      {:empty, _} -> {:not_found}
    end
  end
end

簡易テストを実行

tests = [
  Algo.bfs(graph, :okb, :f) == {:exist, :f},
  Algo.bfs(graph, :okb, :h) == {:not_found},
  Algo.bfs(graph, :b, :f) == {:not_found},
  Algo.bfs(graph, :c, :f) == {:exist, :f}
]

IO.inspect(tests)
#result:
#[true, true, true, true]

queueの使い方を色々、試すのに時間がかかった
Elixirでのデータの動かし方についてはかなりマシになってきたとは思ってます(自己満
もっとこうした方が良いよなどありましたら教えてください

【実装コード有り】アルゴリズム初心者がセレクトソートとクイックソートをElixirで実装する

ソートの必要性について

www.okb-shelf.work

前回の記事で実装した二分探索は対象のリストがソートされていることが前提であり、つまりはリストをソートしてくれるアルゴリズムが必要になるということ
え？もうEnum.sort()あるけど?とは言わない約束
一度自分で実装することが大事なんじゃないかと勝手に思ってます

セレクトソートについて

超シンプルなソート方法です
リストから最小値を取得して新たな配列に順次追加してくというもの
シンプルなリストを使って実際の動きを見てみる

簡単な例

lst = [7,3,2,5,4,8,9,1,10,6]
sorted_lst = []

#1回目
min_num = 1
lst = [7,3,2,5,4,8,9,10,6]
sorted_lst = [1]

#2回目
min_num = 2
lst = [7,3,2,5,4,8,9,10,6]
sorted_lst = [1,2]
:
:
#10回目
min_num = 10
lst = []
sorted_num = [1,2,3,4,5,6,7,8,9,10]

とりあえずElixirで実装してみる

Elixirでのセレクトソート
最小値の探索とベースのリストから最小値の削除には Enum.min()とList.delete()メゾットをコンボで行なっている
同じ数値が現れても問題なく操作を行える

iex(13)> min = Enum.min([1,1,2,3,4,5])
1
iex(14)> List.delete([1,1,2,3,4,5], min)
[1, 2, 3, 4, 5]

こいつを使ってセレクトソートを実装するとこんな感じになった

defmodule Algo do
  def select_sort(lst) do
    _select_sort(lst, [])
  end
  defp _select_sort([], accum), do: accum
  defp _select_sort(lst, accum) do
    min_num = lst |> Enum.min()
    next_lst = List.delete(lst, min_num)
    _select_sort(next_lst, accum ++ [min_num])
  end
end

正しく動作しているかを簡易テストで確かめる

tests = [
  Algo.select_sort([1,4,3,7,5,1,2,13,9,23,5,57]) == [1, 1, 2, 3, 4, 5, 5, 7, 9, 13, 23, 57],
  Algo.select_sort([]) == [],
  Algo.select_sort([1]) == [1],
  Algo.select_sort([2,4,3,5]) == [2,3,4,5],
  Algo.select_sort([4,2,6,7,8,3,12,1,3,76,345,0,67]) == [0, 1, 2, 3, 3, 4, 6, 7, 8, 12, 67, 76, 345]
]

IO.inspect(tests)
#[true, true, true, true, true]

いい感じですね
ただ、この方式だとリストの要素数だけ上記の試行を行う必要がある
そのため10億個の要素があるようなリストが現れた日には詰む
より手順の少ないソートが必要になる

クイックソートについて

言葉で説明するのが難しいので実データの動きを見ていく
先ほど同様にシンプルなリストを用意した

lst = [7,3,2,5,4,8,9,1,10,6]

ではソートを開始
lstの先頭の値を取得してsorted_lstに追加していく
追加する際は昇順になるように適宜行う

#1回目
lst = [3,2,5,4,8,9,1,10,6]
sorted_lst = [7]

#2回目
lst = [2,5,4,8,9,1,10,6]
sorted_lst = [3,7]

#3回目
lst = [5,4,8,9,1,10,6]
sorted_lst = [2,3,7]

#4回目
lst = [4,8,9,1,10,6]
sorted_lst = [2,3,5,7]
:
:
#10回目
lst = [6]
sorted_lst = [1,2,3,4,5,6,7,8,9,10]

クイックソートはどのように要素を取得するかによって試行回数が大きく変化するらしい
今回はElixirのheadとtailを使いたかったので先頭の要素をマッチさせて取得している
この取得した要素のことをピポットと言い、ピポットの取得方法によって性能が変化する

Elixirでのクイックソート
quick_sort()とappend()でそれぞれ再帰している
quick_sort()では受け取ったリストから先頭を取得してソート済み配列に追加していく
追加の際には昇順になるように追加したいのでappend()で判定しつつ良しなに追加する

defmodule Algo do
  def quick_sort(lst), do: _quick_sort(lst, [])
  defp _quick_sort([], accum), do: accum
  defp _quick_sort([head | tail], accum) do
    res = append(head, accum, [])
    _quick_sort(tail, res)
  end
  def append(num, [], accum), do: accum ++ [num]
  def append(num, [head | tail], accum) do
    case num > head do
      true -> append(num, tail, accum ++ [head])
      false -> accum ++ [num] ++ [head] ++ tail
    end
  end
end

同様にテストを試す

tests = [
  Algo.quick_sort([1,4,3,7,5,1,2,13,9,23,5,57]) == [1, 1, 2, 3, 4, 5, 5, 7, 9, 13, 23, 57],
  Algo.quick_sort([]) == [],
  Algo.quick_sort([1]) == [1],
  Algo.quick_sort([2,4,3,5]) == [2,3,4,5],
  Algo.quick_sort([4,2,6,7,8,3,12,1,3,76,345,0,67]) == [0, 1, 2, 3, 3, 4, 6, 7, 8, 12, 67, 76, 345]
]

IO.inspect(tests)
#result
#[true, true, true, true, true]

もう少し短く早くできたのでこちらもどうぞ
たぶんこれが一番早いと思います(大嘘

defmodule Algo do
  def quick_sort(lst) when length(lst) < 2, do: lst
  def quick_sort([head | tail]) do
    smaller = Enum.filter(tail, &(&1 <= head))
    bigger = Enum.filter(tail, &(&1 > head))
    quick_sort(smaller) ++ [head] ++ quick_sort(bigger)
  end
end

二分探索のように

• ピポット以上の値を持つリスト
• ピポット以下の値を持つリスト

の2つに分割してソートを行なっていく

lst = [3,2,5,4,8,9,1,10,6]
fetch_num = 3
smaller = [2,1]
bigger = [5,4,8,9,10,6]

quick_sort(smaller) ++ [fetch_num] ++ quick_sort(bigger)
#最終形はこんな感じになる
[1] ++ [2] ++ [3] ++ [4] ..... [10]

また簡易テストを試す

tests = [
  Algo.quick_sort([1,4,3,7,5,1,2,13,9,23,5,57]) == [1, 1, 2, 3, 4, 5, 5, 7, 9, 13, 23, 57],
  Algo.quick_sort([]) == [],
  Algo.quick_sort([1]) == [1],
  Algo.quick_sort([2,4,3,5]) == [2,3,4,5],
  Algo.quick_sort([4,2,6,7,8,3,12,1,3,76,345,0,67]) == [0, 1, 2, 3, 3, 4, 6, 7, 8, 12, 67, 76, 345]
]

IO.inspect(tests)
#result
#[true, true, true, true, true]

いい感じですね
こういう書き方をスパッと思いつける人間になりたいです