やわらかテック

興味のあること。業務を通して得られた発見。個人的に試してみたことをアウトプットしています🍵

【実装コード有り】Elixirで近しいデータを予想するためにk近傍法を実装した

k近傍法とは

ざっと説明するとAというデータとBというデータが
どれだけ近しいかを予測するためのアルゴリズム
仕組みは超簡単で以下のようなデータがあったとする

size(大きさ)は1~5の5段階
is_red(見た目)は1~5の5段階
has_seed(種があるかないか)は0or1

apple = %{size: 2, is_red: 5, has_seed: 0}
water_melon = %{size: 5, is_red: 1, has_seed: 1}

まずこのappleとwater_melonの2つのデータの距離(どれだけ似ているか)を計算する
値が小さければ小さいほど距離が近いということになる
算出にはシンプルに三角比でお馴染みのピタゴラスの定理を使う
ユークリッド距離と呼ばれているらしい

Elixirで計算してみると以下のようになる

  • :math.pow() : 乗数を算出するErlangメゾット
  • :math.sqrt() : 平方根を算出するErlangメゾット
sum_val = :math.pow(2-5, 2) + :math.pow(5-1, 2) + :math.pow(0-1, 2)
dis = :math.sqrt(sum_val)

iex> dis
5.0990195135927845

試しに青リンゴのデータを用意して距離を算出してみる

blue_apple = %{size: 3, is_red: 1, has_seed: 0}
sum_val = :math.pow(2-3, 2) + :math.pow(5-1, 2) + :math.pow(0-0, 2)
dis = :math.sqrt(sum_val)

iex> dis
4.123105625617661

さきほどよりは小さくなったが色の特徴量の数値が値に大きく影響しているのが分かる
(特徴量選択や正規化には触れない)

appleとの距離の算出結果が複数個あるとする(label: 分類名, dis: 距離)

cal_res = [
  %{label: :apple, dis: 1.0},
  %{label: :water_melon, dis: 5.0},
  %{label: :water_melon, dis: 2.0},
  %{label: :apple, dis: 2.5},
  %{label: :apple, dis: 1.5},
]

k近傍法では距離の値の小さいものからk個取得して多数決をとる
k = 3としてデータを取得する

fetch_data = [
  %{label: :apple, dis: 1.0},
  %{label: :water_melon, dis: 2.0},
  %{label: :apple, dis: 1.5},
]

取得したデータのラベルをまとめると

[:apple, :water_melon, :apple]

となり、このデータで多数決を取ると最終的な予想結果はappleとなる

Elixirでの実装

与えるデータがappleとorangeのどちらに似ているかを予想させてみる

fruits = [
  %{size: 2, is_red: 2, label: :orange},
  %{size: 2, is_red: 3, label: :orange},
  %{size: 4, is_red: 4, label: :apple},
  %{size: 1, is_red: 1, label: :orange},
  %{size: 5, is_red: 5, label: :apple},
  %{size: 3, is_red: 4, label: :apple},
]

#このデータはapple? orange?
target_data = %{size: 4, is_red: 3}

#取得する値の数(k)
knn_neighbor_num = 3

まずは全体のコードと結果を表示

defmodule KNN do
  def main(target_data, datas, knn_neighbor_num) do
    calc_res = calc_distance(target_data, datas, knn_neighbor_num)
    count_res = count_common_val_in_lst(calc_res)
    Enum.reduce(Map.keys(count_res), fn x, accum -> 
      if count_res[x] > count_res[accum] do
        x
      else
        accum
      end
    end)
  end
  def calc_distance(target_data, datas, knn_neighbor_num) do
    datas
      |> Enum.map(fn row ->
          calc_res = Enum.map(Map.keys(target_data), fn z -> :math.pow((target_data[z] - row[z]),2) end)
          %{score: :math.sqrt(Enum.sum(calc_res)), label: row[:label]}
        end)
      |> Enum.sort_by(&(&1.score))
      |> Enum.slice(0..knn_neighbor_num-1)
      |> Enum.map(&(&1.label))
  end

  def count_common_val_in_lst(lst), do: _count_common_val_in_lst(lst, %{}, [])
  defp _count_common_val_in_lst([], accum, _), do: accum
  defp _count_common_val_in_lst([head | tail], accum, labels) do
    case Enum.member?(labels, head) do
      true ->
        n_accum = Map.put(accum, head, accum[head]+1)
        _count_common_val_in_lst(tail, n_accum, labels)
      false -> 
        n_accum = Map.put(accum, head, 1)
        _count_common_val_in_lst(tail, n_accum, labels ++ [head])
    end
  end
end

IO.puts(KNN.main(target_data, fruits, knn_neighbor_num))
#apple

与えたデータはk近傍法ではappleと予想された
確かに、fruitsのデータと比べてみるとappleっぽい(適当

各関数について

calc_distance

ターゲットデータとその他(今回でいうとfruits)の距離の算出を行なっている
特徴量の数は変動するのでターゲットデータからkeyを生成するようにした
パイプとEnumめっさ使ってElixirっぽく書けた気がする

def calc_distance(target_data, datas, knn_neighbor_num) do
  datas
     |> Enum.map(fn row ->
        #列挙したデータとターゲットデータの距離を算出
        calc_res = Enum.map(Map.keys(target_data), fn z -> :math.pow((target_data[z] - row[z]),2) end)
        %{score: :math.sqrt(Enum.sum(calc_res)), label: row[:label]} 
      end)
    |> Enum.sort_by(&(&1.score)) #scoreの順にリストinマップをソート
    |> Enum.slice(0..knn_neighbor_num-1) #上位k個だけを取得
    |> Enum.map(&(&1.label)) #keyがラベルの値(appleとかorange)を返す
end

count_common_val_in_lst

calc_distanceの戻り値を使って各ラベルがいくつあるのかをカウントする
[apple, apple, banana, orange, orange, apple]というデータからは

res = %{
  apple: 3,
  banana: 1,
  orange: 2
}

というようなマップを生成する

def count_common_val_in_lst(lst), do: _count_common_val_in_lst(lst, %{}, [])
defp _count_common_val_in_lst([], accum, _), do: accum
defp _count_common_val_in_lst([head | tail], accum, labels) do
  #labels(記入したラベルを保持するためのaccum)にheadが存在しているかどうか
  case Enum.member?(labels, head) do
    true ->
      n_accum = Map.put(accum, head, accum[head]+1) #指定のラベルがkeyの値を上書き
      _count_common_val_in_lst(tail, n_accum, labels)
    false -> 
      n_accum = Map.put(accum, head, 1) #新規のラベルをkeyとして作成して1をセット
      _count_common_val_in_lst(tail, n_accum, labels ++ [head])
  end
end

main

上の2つの関数を組み合わせてcountしたmapを作成して
その値から一番カウントが大きな値を返す

def main(target_data, datas, knn_neighbor_num) do
  calc_res = calc_distance(target_data, datas, knn_neighbor_num)
  count_res = count_common_val_in_lst(calc_res)
  Enum.reduce(Map.keys(count_res), fn x, accum -> 
    if count_res[x] > count_res[accum] do
      x
    else
      accum
    end
  end)
end

データはこんな感じで変化していく

#calc_distance
calc_res =[
  %{score: 1, labels: apple},
  %{score: 4, labels: orange},
  %{score: 2, labels: apple},
]

#count_common_val_in_lst
count_res = %{
  apple: 2
  orange: 1
}

#last return
--> apple

可能な限りEnum.reduceとかでやりたい反面、中々上手くいかずに再帰関数を使うハメになる
個人的にaccumを2つもてるEnum.reduce_neo()みたいなのを作ろうと思った

【実装コード有り】Elixirでタイポ発見器を最長共通部分列を使って作る

プログラムでタイプミスを修正する難しさ

以下のような変数があったとする
user_input_textは自身で入力したテキストで"apple"と入力したつもりが
間違えて"anpple"と入力してしまっている

user_input_text = "anpple"
answer_text = "apple"

他にもタイプミスはいろんなパターンが考えられる

"aple"
"aale"
"applue"
"apule"

少し大袈裟なものもあるが、人間視点でいえば
「あ、こいつはappleって打ちたかったんやな〜」ってことが何となく分かる
従って添削する場合にappleと修正してあげれば良い

しかし、機械視点ではタイプミスから共通のパターンを見つけて修正するのは難しい

"aple" => "apple"
"aale" => "apple"
"applue" => "apple"
"apule" => "apple"

こんな時に使えるのが最長共通部分列たるもの

最長共通部分列とは

説明するよりも結果見た方が早いので"apple"と"anpple"の最長共通部分列を求めてみる
まずはこんな感じのテーブルを用意

wrong/answer a n p p l e
a - - - - - -
p - - - - - -
p - - - - - -
l - - - - - -
e - - - - - -

まずはのanswerの"apple"の"a"から見ていく
"a"の視点で行に"a"があった場合に、"a"の行に1で埋め込む

wrong/answer a n p p l e
a 1 #発見 1 1 1 1 1
p - - - - - -
p - - - - - -
l - - - - - -
e - - - - - -

さらにwrongのa列を調査済みにするために1で埋め込む

wrong/answer a n p p l e
a 1 1 1 1 1 1
p 1 - - - - -
p 1 - - - - -
l 1 - - - - -
e 1 - - - - -

この作業を繰り返し行う
値が一致しない場合は現在の最大値(この場合では1)を埋め込む

wrong/answer a n p p l e
a 1 1 1 1 1 1
p 1 1 2 2 2 2
p 1 1 2 - - -
l 1 1 2 - - -
e 1 1 2 - - -
wrong/answer a n p p l e
a 1 1 1 1 1 1
p 1 1 2 2 2 2
p 1 1 2 3 3 3
l 1 1 2 3 - -
e 1 1 2 3 - -
wrong/answer a n p p l e
a 1 1 1 1 1 1
p 1 1 2 2 2 2
p 1 1 2 3 3 3
l 1 1 2 3 4 4
e 1 1 2 3 4 -
wrong/answer a n p p l e
a 1 1 1 1 1 1
p 1 1 2 2 2 2
p 1 1 2 3 3 3
l 1 1 2 3 4 4
e 1 1 2 3 4 5

これでテーブルの埋め込みは完了 テーブルの最大値が最長共通部分列となる
今回は最長共通部分列が5となった

正解テキストが"banana"の場合はどうなるか
埋め込み過程については同作業なので省略

text a n p p l e
b 0 0 0 0 0 0
a 0 0 0 0 0 0
n 0 0 0 0 0 0
a 0 0 0 0 0 0
n 0 0 0 0 0 0
a 0 0 0 0 0 0

こんな感じの算出をプログラムで行いたい

Elixirでの実装

先にコードと結果をお見せします
Enum.reduce使ってスマートに書けないなぁと色々と試行錯誤したものの断念
アキュムレーターを2つ持たせられたり、条件に一致したら列挙を中止するなどがEnumでできたら嬉しい

defmodule Sample do
  def main(input_val, ans_val) when input_val == ans_val, do: :good
  def main(input_val, ans_val), do: _main(String.graphemes(input_val), ans_val, 0)
  defp _main([], _, counter), do: counter
  defp _main([head | tail], ans_val, counter) do
    str_lst = String.graphemes(ans_val)
    [_n_head | n_tail] = str_lst
    case type_judge(str_lst, head) do
      :hit -> _main(tail, List.to_string(n_tail), counter+1)
      :empty -> _main(tail, List.to_string(n_tail), counter)
    end
  end
  
  def type_judge([], _), do: :empty
  def type_judge([head | tail], compare_str) do
    if String.contains?(compare_str, head) do
      :hit
    else
      type_judge(tail, compare_str)
    end
  end
end

簡単なテストの実行をしてみる

tests = [
  Checker.main("apple", "anpple") == 5,
  Checker.main("apple", "apple") == :good,
  Checker.main("banana", "anpple") == 0,
  Checker.main("banana", "anapple") == 1,
  Checker.main("fish", "fosh") == 3
]

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

良い感じですね
動作に関しては問題なさげだけど、もっとシンプルなコードにしたい

コードの解説

main関数

#入力と答えの候補が一致している場合は終了
def main(input_val, ans_val) when input_val == ans_val, do: :good

#文字列をリストに変換して_mainに渡す
def main(input_val, ans_val), do: _main(String.graphemes(input_val), ans_val, 0)
defp _main([], _, counter), do: counter
defp _main([head | tail], ans_val, counter) do
  #正解テキストをリストに変換
  str_lst = String.graphemes(ans_val)
  #次の再帰用に先頭文字列を削除(スライスでやれればいいが...)
  [_n_head | n_tail] = str_lst
  case type_judge(str_lst, head) do
    :hit -> _main(tail, List.to_string(n_tail), counter+1)
    :empty -> _main(tail, List.to_string(n_tail), counter)
  end
end

type_judge
コードに関しては説明することは特になし
貰った文字列同士が一致しているか調べてるのみ
一致した場合に再帰せずに終了

def type_judge([], _), do: :empty
def type_judge([head | tail], compare_str) do
  if String.contains?(compare_str, head) do
    :hit
  else
    type_judge(tail, compare_str)
  end
end

今思えばこれただの「==」でよかったなと
思った通り、普通に動いてる

def type_judge([], _), do: :empty
def type_judge([head | tail], compare_str) do
  if compare_str == head do
    :hit
  else
    type_judge(tail, compare_str)
  end
end

tests = [
  Checker.main("apple", "anpple") == 5,
  Checker.main("apple", "apple") == :good,
  Checker.main("banana", "anpple") == 0,
  Checker.main("banana", "anapple") == 1,
  Checker.main("fish", "fosh") == 3
]

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

【実装コード有り】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でダイクストラ法を実装して最短経路を求めるまで

グラフと最短経路

こんなグラフのネットワークがあったとする
f:id:takamizawa46:20190503162633p:plain

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

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

Start -> B -> A -> Goal

になるかと思う
f:id:takamizawa46:20190503163004p:plain

これがこのグラフでの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...
どうやらフェイクデータを色々作れるライブラリだそうです
公式ドキュメントを見てみると

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

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()

これで準備は完了

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

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

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

FakerErlangモジュールの: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

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