やわらかテック

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

【レポート】第8回清流elixir勉強会を開催しました【競プロ(Cake and Donuts)@Elixir2】

トピック

今回で第8回目の勉強会を開催致しました
elixir-sr.connpass.com

隔週で勉強会を開催して早3ヶ月...
当初はElixirについてほとんど知らなかったが、現在ではある程度語れるレベルにはなった
Elixirを勉強しないという気持ちから、この面白い言語を多くの人に薦めたいと思うようになった

次回の勉強会ではElixirの入門会のようなことをしようと思う

清流elixir-infomation
開催場所: 丸の内(愛知)
参加人数: 3 -> 2
コミュニティ参加人数 : 10 -> 10 20190629現在

第8回の活動内容

www.okb-shelf.work

簡潔に述べると内容は第6回の続き
Elixirでの実装力を高めるために、競プロ問題をElixirで解いてみようということになった
素晴らしい。実際に何問か解いてみて難しさがよく分かった

Elixirでの標準入力の受け取りに関しては上記のリンクの記事を参照してほしい
今回、挑戦した問題はこちら

atcoder.jp

4ドルのケーキと7ドルのケーキをx個, y個買った時にN円になる組み合わせは存在するかどうか
入力 N
存在する場合: Yes と出力
存在しない場合: Noと出力

単純な組み合わせ問題ではあるが、Elixirでの実装ではかなり頭を使わされた

いろいろな試行錯誤

最初に思いついたことは

  • 4の倍数
  • 7の倍数
  • 11の倍数(4+7)

であればいいんじゃね?と
今思えば、思考不足だが当初はいい線いってるなぁと思いコードに起こしてみた

defmodule Main do
  def main do
    # Nの入力を受け取る
    total_price = IO.gets("") |> String.trim() |> String.to_integer()
    # それぞれの倍数で割り切れるか確認
    judge = Enum.map([4,7,11], fn x -> rem(total_price, x) == 0 end)
    case true in judge do
      true -> "Yes"
      false -> "No"
    end
  end
end

ある程度のケースに対応できるようだが、詰めが甘かった
以下のようなケースではうまく判定ができない

71 -> 7 * 9 + 4 * 2
23 -> 7 * 1 + 4 * 4
45 -> 7 * 3 + 4 * 6

そりゃそうだ。11の倍数でokでは対応出来ていなかった
なので、次に全組み合わせのパターン検索を行なってみた
どういうことかというと

--7 * 0のとき--
7 * 0 + 4 * 1 = 4
7 * 0 + 4 * 2 = 8
:
:
7 * 0 + 4 * n = 4 * n

--7 * 1のとき--
7 * 1 + 4 * 1 = 11
7 * 1 + 4 * 2 = 15
:
:
7 * 1 + 4 * n = 7 + 4 * n

:
:
--7 * nのとき--
7 * n + 4 * 1 = 7 * n + 4
7 * n + 4 * 2 = 7 * n + 8
:
:
7 * n + 4 * n2 = 7 * n + 4 * n2

こんな感じ。Enumを使ってコードに起こしてみる

defmodule Main do
  def main do
    total_price = IO.gets("") |> String.trim() |> String.to_integer()
    res = Enum.map(0..total_price, fn big_num ->
        Enum.map(1..total_price, fn small_num ->
          # 7* n1 + 4 * n2 が入力値に一致した場合にtrueを返す
          if 7 * big_num + 4 * small_num == total_price do
            IO.puts("--> big: #{big_num}, small: #{small_num} ==> #{big_num * 7 + small_num * 4}")
            true
          else
            false
          end
        end)
      end)
      # リストを2次元から1次元に結合
      |> Enum.reduce(fn x, acc -> x ++ acc end)
      # trueが含まれているかを確認
      |> Enum.member?(true)
    if res, do: IO.puts("Yes"), else: IO.puts("No")
  end
end

# 71の時
Main.main()
71
--> big: 1, small: 16 ==> 71
--> big: 5, small: 9 ==> 71
--> big: 9, small: 2 ==> 71
Yes
:ok

# 23の時
--> big: 1, small: 4 ==> 23
Yes
:ok

# 45の時
--> big: 3, small: 6 ==> 45
Yes
:ok

# 16の時
--> big: 0, small: 4 ==> 16
Yes
:ok

とりあえずはいい感じ
しかしながら、現状ではそれぞれ

  • 7: 0..入力値まで
  • 4: 1..入力値まで

のrangeを使っているのでかなりパフォーマンスが悪い
7 +* nの値が入力値を超えた時点で処理が終わるようにしたいので以下のように変更
rangeの上限値には割り算の数値に余りが存在する場合には+1を行なっている

num = 71
res3 = Enum.reduce(1..(div(num, 7) + if rem(num, 7) == 0, do: 0, else: 1), fn x, _acc -> x end)
IO.puts(res3)

# 11

これで無駄な処理が行われないようにできるはず

defmodule Main do
  def main do
    total_price = IO.gets("") |> String.trim() |> String.to_integer()
    # div->割り算に rem->余り が0でなければ1を足し合わせる
    res = Enum.map(0..(div(total_price, 7) + if rem(total_price, 7) == 0, do: 0, else: 1), fn big_num ->
            Enum.map(0..(div(total_price, 4) + if rem(total_price, 4) == 0, do: 0, else: 1), fn small_num ->
              if 7 * big_num + 4 * small_num == total_price do
                IO.puts("--> big: #{big_num}, small: #{small_num} ==> #{big_num * 7 + small_num * 4}")
                true
              else
                false
              end
            end)
          end)
      |> Enum.reduce(fn x, acc -> x ++ acc end)
      |> Enum.member?(true)
    if res, do: IO.puts("Yes"), else: IO.puts("No")
  end
end

こちらも上手く出力された
ただ、Enum.mapでは途中で条件に一致した場合に処理を停止することが出来ない
今回は全パターンの探索を行うことよりもそのパターンが存在する時点で探索を終了してYesを出力すれば良い
なので、無理やり再帰関数で上記のEnum.mapで行なっている処理を再現して、条件に一致した時点で停止するようにした

無駄にすごく長くなってしまって何かうーん...って感じ
やりたいことは出来たと思うけど

defmodule Main do
  def main() do
    # 入力値を受け取り計算を行う関数に渡す
    total_price = IO.gets("") |> String.trim() |> String.to_integer()
    can_buy(total_price, 0)
  end
  # 入力値を超えた時点で終了してNoを出力
  def can_buy(num, accum) when num < 7 * accum, do: IO.puts("No")
  def can_buy(num, accum) do
    if calc(num, accum) do
      IO.puts("Yes")
    else
      can_buy(num, accum + 1)
    end
  end
  def calc(num, accum), do: _calc(num, accum, 0)
  # 7 * n1 + 4 * n2の値が入力値を超えた時点でfalseを返し、次のn1に
  def _calc(num, _big_accum, accum) when num < 4 * accum, do: false
  def _calc(num, big_accum, accum) do
    if 7 * big_accum + 4 * accum == num do
      true
    else
      _calc(num, big_accum, accum + 1)
    end
  end
end

パフォーマンスは若干良くなったような気がするが、コードの記述時間はEnum.mapの方が圧倒的に早い
課題点としてはEnum.mapの途中で処理を終了できればと思う

何か方法はありそうだが、どうなのか...
とりあえずやりたいことはできたので良かった

競プロ難しいわ~

次回について

冒頭でも触れた通り、ある程度Elixirへの知見が溜まってきたため、そろそろElixir入門会を実施したいと思う
コミュニティの人を増やしたいという狙いもある
内容は

  • リストをパイプ演算子Enumでゴリゴリ回す
  • マルチプロセスで並列処理をゴリゴリ回す
  • パターンマッチでFizzBuzzを作る

あたりを考えているが、まだ詰めきれていないので考えなければ

【Elixirで学ぶCS】ElixirでそれっぽいALUが実装できるまで

なにこれ(3度目

Elixirでコンピューターサイエンスを学ぶシリーズの第3弾で以下記事の続編です
www.okb-shelf.work

この本を参考に勉強しつつコードを書いています

相変わらず内容に結構つまづいている
今、土日はだいたいこの本 + cousera使ってcsを勉強している
内容的には最初の方はよりレイヤーが深い話なので挫折しやすいってのがよく分かる
確かに論理ゲートとかいきなり言われてもなぁとは思いつつ、挫折しつつ何とか続いている

なんとか2章の終わりのALUまでを実装できたのでまとめておく

ALUについて

一言でいうとCPUのコアになる演算を行う部分
xとyの入力をリセットしたり、反転させたり、足し合わせたりってことやらが可能

このALUを利用してCPUは演算を行なっている
詳しい仕組みやなぜこの回路でALUが動作するのかという説明は行わない

上記で紹介した書籍などを参考にしてほしい
自分は全テストケースが通ったからOK程度の認識でいる

前回から追加したゲート

先に予備知識となる「sel」について説明する
selは何も難しいものではなくて、入力のどちらを採用するか(0or1)を回路に伝えるためのものである

# sel = 0のとき
input = [x, y]
sel = 0
out = x

# sel = 1のとき
input = [x, y]
sel = 1
out = y

ALUを実現するために、新たなゲートが必要になるのでざっくりと説明しておく

  • Mux回路 -> 複数の入力(x, yの2つ)からselの値を使用して1つを選択
  • Dmux回路 -> 受け取った値をどの位置に通すかを選択

Mux回路については先ほど紹介している & イメージがしやすいと思うが
Dmux回路の説明は言語の限界があるので許して欲しい
Mux回路同様に具体的な値の動き方を見てみる

# sel = 0のとき
val = 1
sel = 0
out = [1, 0]

# sel = 0のとき
val = 1
sel = 1
out = [0, 1]

先ほど説明する際に使用した「位置」という言葉はリストのindex位置だと思ってくれれば良い
入力された値をどのindexに格納して次に渡すかをDmux回路で行なっている

ElixirでMux回路とDmux回路を実装する

まずはシンプルにElixirのパターンマッチを使用して簡易なものを作成してイメージを確かめる

defmodule SimpleMux do
  def mux([a, _b], 0), do: a
  def mux([_a, b], 1), do: b
  def dmux(x, 0), do: {x, 0}
  def dmux(x, 1), do: {0, x}
end

Elixirっぽくていいね。異世界転生かってぐらいのチート実装
それぞれの回路でselのパターンは2種類しかないので楽勝

簡単なテストを実行しておく
まずはMux回路について

mux_test= [
  SimpleMux.mux([0,0], 0) == 0,
  SimpleMux.mux([0,0], 1) == 0,
  SimpleMux.mux([1,0], 0) == 1,
  SimpleMux.mux([1,0], 1) == 0,
  SimpleMux.mux([0,1], 0) == 0,
  SimpleMux.mux([0,1], 1) == 1,
  SimpleMux.mux([1,1], 0) == 1,
  SimpleMux.mux([1,1], 1) == 1,
]
IO.inspect(mux_test)
# [true, true, true, true, true, true, true, true]

次にDmux回路について

dmux_test = [
  SimpleMux.dmux(0, 0) == {0, 0},
  SimpleMux.dmux(0, 1) == {0, 0},
  SimpleMux.dmux(1, 0) == {1, 0},
  SimpleMux.dmux(1, 1) == {0, 1}
]

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

しかし、この方法はゲート理論の実装から逸れたものになってしまうのでNG(Elixirごめんな)
なのでnotやandなどの他の回路を使って実装する。回路図はぐぐってね
実装は以前より引き続き使用しているRogicalGateモジュールに追加した

defmodule RogicalGate do
  def nand(1, 1), do: 0
  def nand(_x, _y), do: 1
  def or_(x, y), do: nand(nand(x, x), nand(y, y))
  def not_(x), do: nand(x, x)
  def and_(x, y), do: not_(nand(x,y))
  def xor_(x, y), do: or_(and_(x,not_(y)), and_(not_(x),y))
  def mux([x, y], sel) do
    not_sel = not_(sel)
    or_(and_(x, not_sel), and_(y, sel))
  end
  def dmux(x, sel) do
    not_sel = not_(sel)
    {and_(x, not_sel), and_(x, sel)}
  end
end

先ほどのテストを流用。同じことなのでまとめて行う

mux_test= [
  RogicalGate.mux([0,0], 0) == 0,
  RogicalGate.mux([0,0], 1) == 0,
  RogicalGate.mux([1,0], 0) == 1,
  RogicalGate.mux([1,0], 1) == 0,
  RogicalGate.mux([0,1], 0) == 0,
  RogicalGate.mux([0,1], 1) == 1,
  RogicalGate.mux([1,1], 0) == 1,
  RogicalGate.mux([1,1], 1) == 1,
]

dmux_test = [
  RogicalGate.dmux(0, 0) == {0, 0},
  RogicalGate.dmux(0, 1) == {0, 0},
  RogicalGate.dmux(1, 0) == {1, 0},
  RogicalGate.dmux(1, 1) == {0, 1}
]

IO.inspect(mux_test)
# [true, true, true, true, true, true, true, true]
IO.inspect(dmux_test)
# [true, true, true, true]

理論をキッチリ守ることが出来た
次にMux回路とDmux回路をnbit対応させる
実装には以前より使用しているNbitRogicalGateを使用しているが、少し内容を変更している
回路の関数をnbitに対応させるヘルパー関数を用意してmux回路用の変換関数を追加した

defmodule NbitRogicalGate do
  # [x,y]のような入力を2つ受ける回路の変換関数
  def nbit_converter(inputs, gate_func), do: Enum.map(inputs, fn [x, y] -> gate_func.(x, y) end)
  # [x]のような入力を1つ受ける回路(not)の変換関数
  def nbit_not(inputs, gate_func), do: Enum.map(inputs, fn x -> gate_func.(x) end)
  # [[x,y],sel]のような入力を2つ(リストとsel)受ける回路(mux)の変換関数
  def nbit_mux(inputs, gate_func), do: Enum.map(inputs, fn [[x,y], sel] -> gate_func.([x,y], sel)  end)

  def nand(inputs), do: nbit_converter(inputs, &RogicalGate.nand/2)
  def not_(inputs), do: nbit_not(inputs, &RogicalGate.not_/1)
  def or_(inputs), do: nbit_converter(inputs, &RogicalGate.or_/2)
  def and_(inputs), do: nbit_converter(inputs, &RogicalGate.and_/2)
  def xor_(inputs), do: nbit_converter(inputs, &RogicalGate.xor_/2)

  # ここに追加したよ~
  def mux(inputs), do: nbit_mux(inputs, &RogicalGate.mux/2)
  def dmux(inputs), do: nbit_converter(inputs, &RogicalGate.dmux/2)
end

動作を確認

res = NbitRogicalGate.mux([[[1,0], 0], [[0,0], 1], [[0,1], 1], [[1,1], 1]])
IO.inspect(res)
# [1, 0, 1, 1]

res_dmux = NbitRogicalGate.dmux([[1,0], [0,1], [1,1], [0,0]])
IO.inspect(res_dmux)
# [{1, 0}, {0, 0}, {0, 1}, {0, 0}]

良い感じっぽい
準備もそこそこ出来たのでALUの実装に移る

ALUの実装の前に...

ALUの内部構造について、ざっくりと触れておく
ALUは以下の値を受け取って値の演算を行う関数になる
(nはビット数-1とする。16bitの時は15 -> 0..15)

それぞれの入力値についてまとめる

  • x[0..n] -> 入力値x群
  • y[0..n] -> 入力値y群
  • zx(0or1 -> sel) -> xの値を全て0にするかどうか
  • nx(0or1 -> sel) -> xの値を全て反転するかどうか
  • zy(0or1 -> sel) -> yの値を全て0にするかどうか
  • ny(0or1 -> sel) -> yの値を全て反転するかどうか
  • f(0or1 -> sel) -> and(x, y)とadd(x, y)のどちらを採用するか
  • no(0or1 -> sel) -> 出力値を反転するかどうか

zxはおそらくzero_x, nxはnot_xの略だと思っている
で何?ってなると思うので4bitの演算の動きをサンプルデータを追って見ていく
これで少しはイメージを掴んでもらえればと思う

# 入力値xとy
x = [0,1,1,0]
y = [1,0,0,0]

# sel値
zx = 0
nx = 1
zy = 1
ny = 1
f = 0
no = 1

# xのデータに対しての変換
# zx = 0より(0にしない)
x = [0,1,1,0]

# nx = 1より(値を反転)
x = [1,0,0,1]

# yのデータに対しての変換
# zy = 1より(0にする)
y = [0,0,0,0]

# ny = 1より(値を反転)
y = [1,1,1,1]


# この時点でのxとyの値 -------------
x = [1,0,0,1]
y = [1,1,1,1]
# -----------------------------------

# f = 0より and(x, y)を採用
# こんな感じで処理していく
# [and(1,1), and(0,1), and(0,1), and(1,1)
fout = [1,0,0,1]

# no = 1よりfoutを反転
out = [0,1,1,0]

と、こんな感じで特に難しいことをやっているわけではない
このselの組み合わせで演算に必要なパターン18種が全て表現可能だそう
やっぱり考えた人が天才すぎる...

最終的な出力値のoutと別にzrとngという2つの出力値がある
zrは出力値に1が含まれていれば0を返す
ngは最上位bit(一番上の桁)が1なら1を返す

これでALUの実装の準備が本当に整った
さっそく上記の処理を論理ゲートを使って実装してみる

ALUの実装

先にコードの全体をお見せする
演算を行うメインの関数はcompute関数になる
他の関数については下記で説明をする

defmodule ALU do
  def lst_converter(x, y), do: Enum.map(Enum.zip(x, y), fn {a, b} -> [a, b] end)
  def lst_converter(x, y, sel), do: Enum.map(Enum.zip(x, y), fn {a, b} -> [[a, b], sel] end)
  def val_creater(val, len), do: Enum.map(1..len, fn _ -> val end)
  def compute(x, y, zx, nx, zy, ny, f, no) do
    nxout = common_calc_gate(x, zx, nx)
    nyout = common_calc_gate(y, zy, ny)

    merge_nx_ny = lst_converter(nxout, nyout)
    xandyout = NbitRogicalGate.and_(merge_nx_ny)
    xaddyout = NbitAdder.nbit_adder(merge_nx_ny)

    input_f = lst_converter(xandyout, xaddyout, f)
    fout = NbitRogicalGate.mux(input_f)
    not_fout = NbitRogicalGate.not_(fout)
    merge_fout = lst_converter(fout, not_fout, no)
    out = NbitRogicalGate.mux(merge_fout)
    ng = Enum.at(out, 0)
    zr = if Enum.member?(out, 1), do: 0, else: 1
    {out, zr, ng}
  end
  def common_calc_gate(lst, zero_key, not_key) do
    false_ = val_creater(0, length(lst))
    inputs = lst_converter(lst, false_, zero_key)
    mux_out = NbitRogicalGate.mux(inputs)
    not_out = NbitRogicalGate.not_(mux_out)

    inputs_out = lst_converter(mux_out, not_out, not_key)
    NbitRogicalGate.mux(inputs_out)
  end
end

補助関数について

演算をよしなに進めるためにリストの構造を変化させるlst_converter関数とval_creater関数をそれぞれ実装している
lst_converter関数は2つのリストを以下のように変換している

x = [1,0,1,1]
y = [1,1,1,0]

converted = lst_converter(x, y)
# [[1, 1], [0, 1], [1, 1], [1, 0]] 

# selがある場合(引数が3つの方にマッチ)
x = [1,0,1,1]
y = [1,1,1,0]
sel = 0

converted = lst_converter(x, y, sel)
# [[[1, 1], 0], [[0, 1], 0], [[1, 1], 0], [[1, 0], 0]] 

val_creater関数は受け取った値を指定サイズ分のリストにして返す

val = 1
len = 8
created = val_creater(val, len)
# [1, 1, 1, 1, 1, 1, 1, 1]

ALUのメイン実装

先ほど説明したzx -> nxとzy -> nyの処理は全く同じ処理なので
common_calc_gateという関数で一般化している
論理ゲートでifの動きを再現したい時はmuxを使えば上手くいく

def common_calc_gate(lst, zero_key, not_key) do
    false_ = val_creater(0, length(lst))
    inputs = lst_converter(lst, false_, zero_key)
    # 全て0のリストと入力リストのどちらを採用するか
    mux_out = NbitRogicalGate.mux(inputs)
    not_out = NbitRogicalGate.not_(mux_out)

    # zxもしくはzyの出力を反転するかどうか
    inputs_out = lst_converter(mux_out, not_out, not_key)
    NbitRogicalGate.mux(inputs_out)
  end

次にcommon_calc_gate関数を通して出力された2つのリストからandとaddを実行する
あとはfとnoのselを考慮して先ほどと同じ仕組みでifをmuxで再現する
ngとzrについてはEnumを使って算出しているが、参考にしたコードでもスライス使ってたので良しとした
zrの方だけOrで書き直してもいいかもしれない

defmodule ALU do
  def compute(x, y, zx, nx, zy, ny, f, no) do
    nxout = common_calc_gate(x, zx, nx)
    nyout = common_calc_gate(y, zy, ny)

    # リストを整形
    merge_nx_ny = lst_converter(nxout, nyout)

    # andとaddを計算
    xandyout = NbitRogicalGate.and_(merge_nx_ny)
    xaddyout = NbitAdder.nbit_adder(merge_nx_ny)

    # リストを整形
    input_f = lst_converter(xandyout, xaddyout, f)

    # andかaddのどちらを採用するか
    fout = NbitRogicalGate.mux(input_f)
    not_fout = NbitRogicalGate.not_(fout)
    merge_fout = lst_converter(fout, not_fout, no)

    # 値を反転するかどうか(sel: no)
    out = NbitRogicalGate.mux(merge_fout)

    # ngとzrの値を取得
    ng = Enum.at(out, 0)
    zr = if Enum.member?(out, 1), do: 0, else: 1
    {out, zr, ng}
  end

今回作成するALUはオーバーフローに対応させないため 以前実装した加算器からオーバーフローの対応を一時的に抜いておく

defmodule NbitAdder do
  #再帰関数: リストが空になったら終了
  # accumにcarryの追加をしないように変更
  # defp _nbit_adder([], carry, accum), do: [carry] ++ accum
  defp _nbit_adder([], _carry, accum), do: accum
  defp _nbit_adder([[a1, b1] | tail], carry, accum) do
    {c0, s0} = full_adder(a1, b1, carry)
    _nbit_adder(tail, c0, [s0] ++ accum)
  end
end

一応、ALUの実装は出来たのでやはりテストコードを実行する

x = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
y = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

test1 = [
  ALU.compute(x,y,1,0,1,0,1,0) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
  ALU.compute(x,y,1,1,1,1,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],0,0},
  ALU.compute(x,y,1,1,1,0,1,0) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
  ALU.compute(x,y,0,0,1,1,0,0) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
  ALU.compute(x,y,1,1,0,0,0,0) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
  ALU.compute(x,y,0,0,1,1,0,1) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
  ALU.compute(x,y,1,1,0,0,0,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
  ALU.compute(x,y,0,0,1,1,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
  ALU.compute(x,y,1,1,0,0,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],0,0},
  ALU.compute(x,y,0,1,1,1,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],0,0},
  ALU.compute(x,y,1,1,0,1,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
  ALU.compute(x,y,0,0,1,1,1,0) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
  ALU.compute(x,y,1,1,0,0,1,0) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],0,1},
  ALU.compute(x,y,0,0,0,0,1,0) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
  ALU.compute(x,y,0,1,0,0,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],0,0},
  ALU.compute(x,y,0,0,0,1,1,1) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
  ALU.compute(x,y,0,0,0,0,0,0) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
  ALU.compute(x,y,0,1,0,1,0,1) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1}
]

IO.inspect(test1)
# [true, true, true, true, true, true, true, ... true, true, true, true] すべてtrue
x = [0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1]
y = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1]

test2 = [
  ALU.compute(x,y,1,0,1,0,1,0) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],1,0},
  ALU.compute(x,y,1,1,1,1,1,1) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],0,0},
  ALU.compute(x,y,1,1,1,0,1,0) == {[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],0,1},
  ALU.compute(x,y,0,0,1,1,0,0) == {[0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1],0,0},
  ALU.compute(x,y,1,1,0,0,0,0) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1],0,0},
  ALU.compute(x,y,0,0,1,1,0,1) == {[1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0],0,1},
  ALU.compute(x,y,1,1,0,0,0,1) == {[1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0],0,1},
  ALU.compute(x,y,0,0,1,1,1,1) == {[1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1],0,1},
  ALU.compute(x,y,1,1,0,0,1,1) == {[1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1],0,1},
  ALU.compute(x,y,0,1,1,1,1,1) == {[0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0],0,0},
  ALU.compute(x,y,1,1,0,1,1,1) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0],0,0},
  ALU.compute(x,y,0,0,1,1,1,0) == {[0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0],0,0},
  ALU.compute(x,y,1,1,0,0,1,0) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0],0,0},
  ALU.compute(x,y,0,0,0,0,1,0) == {[0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0],0,0},
  ALU.compute(x,y,0,1,0,0,1,1) == {[0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0],0,0},
  ALU.compute(x,y,0,0,0,1,1,1) == {[1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,0],0,1},
  ALU.compute(x,y,0,0,0,0,0,0) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],0,0},
  ALU.compute(x,y,0,1,0,1,0,1) == {[0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1],0,0},
]

IO.inspect(test2)
# [true, true, true, true, true, true, true, ... true, true, true, true] すべてtrue

いいですね。そろそろこのテスト方法はしんどくなってきたが
ライブラリなしで実行できるので割と気に入っている

とりあえず、情報学部でも何でもないがALUの実装までをElixirで出来た
Elixirの実装の前にhdlというもので実装を行なっており、hdl + Elixirで実装するため
かなり時間がかかっているが言語を変えて実装してみるというのは非常に勉強になる
Elixirの勉強になる上にcsの勉強にもなるため、この勉強法はかなりアリだと思っている

めちゃくちゃ長くなってしまった。過去最高の13000文字。どひゃー

ベンチャーで働く新卒のエンジニアが新卒研修に行かされて感じたこと

バックグラウンド

タイトルでざっくりと述べているが、一応新卒の22歳です
名古屋の某ベンチャー企業でエンジニアとして勤務しています(社名は伏せる)
改めて自分のブログを見てみるとプロフィールの詳細が無かったので
情報の信頼性を高めるためにも自分が何者なのかをスキルベースで述べておく

okbについて

  • 仕事内容:
    • webエンジニア(フロント、バック経験あり)
    • 機械学習の案件管理と開発
  • スキル(経験技術(frameworkは除く)):

とはいっても、情報学部の卒ではないため、知識はあんまりない
今必死になってコンピューターサイエンスの勉強をしています
なんでエンジニアになったのかというと自分に自信がなかったから

大学3年生の時に周りが必死こいて就活してるのを見て「やばいな」と思い
手に職をつけるために技術を磨く必要があると思い、悩んだ末にコンピューター(プログラミング)を選択した

現在、勤務している企業にインターンとして大学3年生の時に参加してアルバイトを経て今に至る
新卒といいつつも業務に関しては一応2年目という扱いになっている

何が起きたのか

ベンチャー企業なので研修という制度はもちろんない
新卒のエンジニアといいつつも、お客様のところに足を運んでヒアリングをするということもよくある
当然僕は

  • 名刺の受け渡し
  • 言葉遣い
  • ビジネスマナー

など研修も受けていないので疎く、セールスの方に指摘されることがあった
「いくらエンジニアでも基礎ぐらいはつけないとね」ということで

気がついたら某所で開催されている新卒研修(マナー講座)に同期(年上)と参加していた(させられていた)

当日のざっくりした内容

某研修をディスるためにこの記事を書いているわけではないので特定がされない範疇で列挙する

  • 講師の自己紹介
  • グループワーク(自己紹介やらどんな会社で働いているか)
  • 正しい言葉遣い(謙譲語や尊敬語、丁寧語)
  • お昼休憩
  • 電話の受け取り方
  • 相手を喜ばせるには
  • クレーマー対応
  • 質問

記憶が正しければ、こんな内容だったと思う
グループワークは上にだけ書いているが実際には各所で
「これについてはどう思う」かということを議論(雑談)をしている

とはいいつつも、グループの意見を出しても先生の過去の経験がベストアンサーになるので
グループワークの意味は全く無かった(ただ名刺交換が出来ただけ)

説明の無さと価値観の違い

この研修に参加して一番強く思ったことは見出しの通り
マナーとか所作に関しては基本だしその通りだと思うし、お客様に対して敬意を払うのは当然
ただ、そのためにあれやこれやを全部やってあげるというのはどうなのかと思った

実際に研修で出てきた話に「エンジニアからの説明がクソ」というものがあった
この話は先生の当時の話だと伺っているので1970年あたりを想定して聞いていた
お偉いさんにコンピューターの説明をしてくれと依頼したところ、カタカナばかりで全然分からないとエンジニアが怒られたらしい
再度、丁寧に説明したところ、「君は説明する気があるの?」とエンジニアが再び叱責されたそう

先生はこのエンジニアのことをダメなやつと語っていたが本当にそうなのか

そもそも状況の説明が一切なく、なぜ説明することになったかが分からないのに
説明の内容がクソだったと言われても、当事者じゃない僕らには分からないっすわ

要するに先生のただの感想でしかなくてマナーがどうとか関係なかった
説明を聞く側の人間は最低限の勉強はしたのかということも話もなく
何というか時代の価値観の違いのようなものを感じた

偏見かもしれないが2回り程度上の世代の方は人にしてもらうという考え方がベースにある気がする

  • お茶は淹れてもらう
  • コピーはとってもらう
  • タクシーを読んでもらう

など、そういった仕事が生まれたのも頷ける

それに対して同世代の人たちはお茶は自分で淹れるし、コピーも自分でやる
「してもらう」という価値観が違いすぎて自分の頭ではよく理解できなかった

この話題に対して、他の参加者が何を思ったのかは凄く気になる

やべぇやつがいる

こんな自分でも新卒のためのマナー講座っていう題目だから、普段は私服だがスーツを着用していった
会場に着いてみると、思った通り皆スーツで来場していた

一安心と思いつつ、会場をよく見渡してみると普通に私服のやついる
まぁ、それは指定がなかったら別にいいとする

自分が勝手にスーツを着ていっただけなので

しかし、驚いた
よく見ると髪は金髪でピアスついてる

今日はホスト・ホステスの研修なのかと思うぐらい。しかも一人ではなく同じ会社から何人も

なるほど。確かにこういう人がいるからこそ、こういうマナー講座が必要なのか
ということを密かに悟った

自分の会社のありがたさ

無事に研修が終わり、会社に戻ったところで先輩に今日の内容(上で書いたようなこと)を報告した
そうしたところ、こんなような言葉が返ってきた

「世の中にはこういう理不尽がたくさんあるんやで」

確かになぁ。自分には絶対、我慢できへんなぁと思い自分の置かれている環境のありがたさが分かった
先輩にはいつ話しかけてもいいし、お茶を淹れる必要もない

その上、ありとあらゆる業務を経験させてもらっている(ベンチャーならではこそ)
もはや同期の新卒とは経験が違うなと思った

自分が優れているということではなく環境のありがたさが身に染みた
とはいえ残業はしたくないので、どんどん強くなってさらに生産性を上げなければと強く思った

今回のマナー研修を通じて学んだことは「理不尽がある」ということ
結局帰ってきてから先輩から聞いたnode.jsのノンブロッキング処理の話がその日、一番衝撃的だったけど

色々と勉強になりました(ざっくり

【第7回清流elixir勉強会@fukuoka.exさん】Elixirのシギルについて調べて色々試した【リモートでジョイン】

トピック

昨週に引き続き、清流elixirの第7回目の勉強会を開催させて頂きました
今回は清流elixirのみではなく福岡を拠点に活動されているfukuoka.exさんのもくもく会
リモートでジョインさせて頂きました

fukuokaex.connpass.com

もくもく会を主催されているkogaさん
色々とご準備頂きまして有難うございました

なんと昨日のリモートのもくもく会

  • 北海道
  • 東京
  • 愛知
  • 高知
  • 福岡

が繋がったらしいです。実質日本一週ですわ

それで僕はElixirのシギルたるものがずっと気になっていたのでもくもくとまとめた
ほとんど、喋りながらやってた気がする笑

シギルって

そもそもシジル? シギルどっち?
両方存在してるけどどっちが正しいのか?
(プログラミングelixirではシジルだけど...)

とりあえず以下、シギルとして扱う

「~」を先頭に書くことでシギルというものを扱うことが可能
プログラミングelixirによると

  • ~C
  • ~c
  • ~S
  • ~s
  • ~W
  • ~w
  • ~r
  • ~R

の4種類(小文字と大文字)が用意されている
とりあえず~sは動いた

~s(hello world)
# "hello world"

いろいろと試しつつ動かしてみる

~sと~Sについて

さきほどは~sに英字を渡したが日本語でも問題なくいけた

~s(こんにちは)
# "こんにちは"

数値でも問題ない模様

~s(114514)
# "114514"

~sと~Sの違いは?

~sをつかうと演算やら値の埋め込みしてくれるようだ
1/2(0.5)の演算結果が出力値に含まれている

~s(hello world #{1 / 2})
# "hello world 0.5"

変数の埋め込みも問題ない

val = "okb"
~s(hello world #{val})
# "hello world okb"

合わせて""やら''を使えるっぽい

~s(hello world #{"okb"})
# "hello world okb"

~s(hello world #{'okb'})
# "hello world okb"

~Sの場合は演算やら値の埋め込みは行われない

~S(hello world #{1 / 2})
# "hello world \#{1 / 2}"

~Sは変数名や関数名を文字列に変換するのに便利そう
基本的には~sの方が使い勝手は良さげですね

~cと~Cについて

~cの場合はシングルクオートで表示される
これは文字リストというものらしく、~s(string)とは仕様が異なる
文字リストに関しては下記に改めて記述する
~cでも同様に演算渡せるっぽい

~c(hello world)
# 'hello world'
~c(hello world #{1/2})
# 'hello world 0.5'

~Cの場合はやはり値の埋め込みが出来ない

~C(hello world #{1/2})
# 'hello world \#{1/2}'
~C(hello world)
# 'hello world'

ここまでで分かったことは

  • ~sのような小文字のものは値の埋め込みや演算が可能
  • ~Sのような大文字のものはそのまま出力される

ということ

シギルをStringモジュールに渡せるかどうか

どうやら~cだとerrorになってしまう
これは文字リストであって文字列ではないからということ

String.first(~c(hello world))
# (FunctionClauseError) no function clause matching in String.Unicode.next_grapheme_size/1

~sだとStringモジュールが使えた
やはり~sはstringとして扱われている

String.first(~s(hello world))
# "h"
String.graphemes(~s(hello world))
# ["h", "e", "l", "l", "o", " ", "w", "o", "r", "l", "d"]

パイプで遊べた(最高

String.graphemes(~s(hello world)) |> Enum.filter(&(&1 == "h"))
# ["h"]

文字リストについて

文字列はUTF-8エンコードされたバイナリ
文字リストは文字(コードポイント)のリスト

なるほど完全に理解した(すっとぼけ
文字リストは``で囲ってあげるとシギルでなくても作れるらしい
コードポイントってなんやねん~
?a(アルファベット)と記述することでコードポイントを確認することが可能

?a
# 97

?b
# 98

?c
# 99

何か出た。逆でも出た

[98]
# 'b'

厳密に考えるとリストin数値が文字リストとして扱われているということか
''で囲われているからstringではないということになるので普通にEnumやらが使えるということ?

'okb' |> Enum.map(&(IO.puts(&1)))
111
107
98
# [:ok, :ok, :ok]

おお、思った通りにEnumが使える
ただの数値として文字リストの要素が扱われているかどうかを確認してみる

Enum.map('okb', &(is_integer(&1)))
# [true, true, true]

ということなので以下が通る

Enum.sum('okb')
# 316

長くなりそうなので文字リストに関しては今回のテーマとそれるので、ここらへんで終了
文字をリストで扱えることに気づく
使い道はまだ思いつけていない。便利そうでまだ、うーんって感じ

~wと~Wについて

~wとすることで受け取った情報がリストに変換されている

~w[hello world okb]
["hello", "world", "okb"]

やはり受け渡しが出来た

val = "okb"

~w[hello world #{val}]
["hello", "world", "okb"]

~Wでは...もう語ることはない

~W[hello world #{val}]
["hello", "world", "\#{val}"]

リストになるのでもちろんパイプで遊べる(最高

~w[hello world #{val}]
|> Enum.filter(&(String.length(&1) > 4))
|> Enum.reduce(&(&2 <> &1))
"helloworld"

どうやら最後に付け合わせる文字でモードが変わる模様

  • a -> atom
  • c -> string list
  • s -> string
#a
~w[hello world #{val}]a
[:hello, :world, :okb]

#c
~w[hello world #{val}]c
['hello', 'world', 'okb']

#s
~w[hello world #{val}]s
["hello", "world", "okb"]

これは便利
String.splitでは全てがstringになるのでatomを生成できれば
マップのkeyを生成したりと使い道は色々とありそう

以上、シギルについて2時間で調査できた内容です

今回の勉強会の感想

もくもく会には何回か参加したことがあったが、リモートでの勉強会参加は初めてだった
あまり表に顔は出す人間ではないが非常に新鮮で同じものに興味のある方と共に学べたことが素晴らしい体験だった

ぜひまた参加したいです
fukuoka.exさんが月1回程度の頻度で開催されていらっしゃるので
ぜひ会場(全国各地)でお会いしましょう

【Elixirで学ぶCS】Elixirで加算器を実装するまで

なにこれ(既視感

前回の記事の続編です

www.okb-shelf.work

まだ挫折してないです

www.oreilly.co.jp

この本を勉強しているつもりなのですが、普通に難しい
僕のレベルが低いのもあるが、説明があるようでなかったりと結局ググらないと分からない部分が多い
まぁ、そこは自分で実装して理解しろやってコンセプトなんだと思いますがね

加算器について

数日前は唸りに唸って考えていたが、今思えば何も難しくなくてやっていることはシンプルだった
「ただの足し算マシーン」ということでした

一応の専門用語として

  • carry(桁上がり)
  • sum(下の例では1桁目の値)

というものがある 以下の例を見て頂きたい。aとbはそれぞれ入力値を指している

a b carry sum
1 0 0 1
0 0 0 0
1 1 1 0

ただの2進数の足し算でしかない
a+bが2になった時に桁上がりが発生するため、条件a = b = 1のときにcarryの値が1になっており
sumの値が0になっている
普段使っている10進数の計算となんら変わらないということが伝われば幸いです

今行ったこの演算をするための演算器を半加算器というそうです

しかしながら半加算器のみではcarry(桁上がり)の値を次の加算に用いることが出来ない
どういうことかというと

a0 = 1
b0 = 1
carry0 = 1
sum0 = 0

#carry(桁上がりなので10)を用いて半加算器でもう一度、加算を行う
a1(先ほどのcarry値) = 1
b1 = 1
carry1 = 1
sum = 0

せっかくの桁上がりが消滅して、また同じ桁で加算を行ってしまっている
これだと役に立たないので桁上がりを考慮した加算器が必要になる
それが全加算器とよばれるもので桁上がりを考慮した加算器というわけになる

全加算器では入力がa, bに合わせてz(桁上がり値)の3つを受け取る
イメージしやすいように先に論理表をお見せする

a b z carry sum
1 0 0 0 1
1 1 0 1 0
1 0 1 1 0
1 1 1 1 1

見てお判りかと思うが、単にa+bの加算を行った後にzを加算しているだけ
zを桁上がり値と見なせば全加算器と半加算器を組み合わせれば
上手く桁上がりを考慮した加算器が作れそうだと思う

#半加算器の加算
a0 = 1
b0 = 1
carry0 = 1 = z
sum0 = 0 

#全加算器の加算
a1 = 1
b1 = 1
z = 1
carry = 1
sum = 1

全加算器を複数個用意すれば、複数桁の加算を行うことが可能となる

elixirでの実装

まずはcarryとsumを求める関数を作成する
このcarryとsumはそれぞれ

  • carry = andゲート
  • sum = xorゲート

の出力に等しい
carryは入力が(1, 1)の時に1を返す
sumは入力が(1, 0)もしくは(0, 1)の時に1を返すため上記が当てはまる

前回に実装した論理ゲートを用いてそれぞれを無名関数で実装するとこんな感じに

sum_ = fn x, y -> RogicalGate.xor_(x,y) end
carry_ = fn x, y -> RogicalGate.and_(x,y) end

で、あとはこいつらを組み合わせて半加算器を作成する
(回路図はググってね)

half_adder = fn x, y -> {carry_.(x,y), sum_.(x,y)} end

タプルで返していることに深い意味はない(戻り値の要素が4以下だったのでタプルを採用)
簡単なテストを実行してみる

half_adder_test = [
  half_adder.(0, 0) == {0, 0},
  half_adder.(0, 1) == {0, 1},
  half_adder.(1, 0) == {0, 1},
  half_adder.(1, 1) == {1, 0}
]

IO.inspect(half_adder_test)
[true, true, true, true]

いいね
続いて全加算器を実装する
回路上では2つの半加算器を用意して、それぞれの出力をorに通すことで作成可能
(回路図はググってね)

all_adder = fn x, y, z ->
  {res1_x, res1_y} = half_adder.(x, y)
  {res2_x, res2_y} = half_adder.(res1_y, z)
  {RogicalGate.or_(res1_x, res2_x), res2_y}
end

同様に簡単なテストを実行する

all_adder_test = [
  all_adder.(0,0,0) == {0,0},
  all_adder.(0,1,0) == {0,1},
  all_adder.(1,0,0) == {0,1},
  all_adder.(1,1,0) == {1,0},
  all_adder.(0,0,1) == {0,1},
  all_adder.(0,1,1) == {1,0},
  all_adder.(1,0,1) == {1,0},
  all_adder.(1,1,1) == {1,1},
]

IO.inspect(all_adder_test)
[true, true, true, true, true, true, true, true]

いいね
先ほども述べたように後は全加算器を追加していくだけで演算の桁を増やすことが可能であり
試しに4bitの加算器を作成してみた(4桁目はcarry用(桁上がり))

bit_adder_4 = fn [a0, b0], [a1, b1], [a2, b2] ->
  {c0, s0} = half_adder.(a0, b0)
  {c1, s1} = all_adder.(a1, b1, c0)
  {c2, s2} = all_adder.(a2, b2, c1)
  [c2, s2, s1, s0]
end

IO.inspect(bit_adder_4.([1,1], [1,1], [1,1]))
[1, 1, 1, 0]

引数は以下のように捉えて頂きたい

  1 1 1  
+ 1 1 1  
--------  
 1 1 1 0

4bitにもなるとテストパターンが多すぎるので割愛
せっかくなのでnbitに対応する加算器も作ってみた

今まで作成したcarryやらhalf_adderを全てモジュール内関数に置き換えている
すっきりしたね
nbit対応には再帰関数を使用しているが、Enum.reduceとかで書ける気がする

defmodule NbitAdder do
  def sum_(x, y), do: RogicalGate.xor_(x,y)
  def carry_(x, y), do: RogicalGate.and_(x,y)
  def half_adder(x, y), do: {carry_(x,y), sum_(x,y)}
  def full_adder(x, y, z) do
    {res1_x, res1_y} = half_adder(x, y)
    {res2_x, res2_y} = half_adder(res1_y, z)
    {RogicalGate.or_(res1_x, res2_x), res2_y}
  end
  #例外処理: 引数が不正な場合に:errorを返す
  def nbit_adder([]), do: :error
  def nbit_adder([[]]), do: :error
  def nbit_adder([[a0, b0] | tail]) do
    {c0, s0} = half_adder(a0, b0)
    _nbit_adder(tail, c0, [s0])
  end
  
  #再帰関数: リストが空になったら終了
  defp _nbit_adder([], carry, accum), do: [carry] ++ accum
  defp _nbit_adder([[a1, b1] | tail], carry, accum) do
    {c0, s0} = full_adder(a1, b1, carry)
    _nbit_adder(tail, c0, [s0] ++ accum)
  end
end

基本的に難しいことは特にやってなくて、算出した結果をaccumlatorに随時、追加しているだけである
再帰関数が終了した際に、carryの値を加えるのを忘れたぐらいで割とスラスラ書けた
とりあえず、何か実行してみる

res1 = NbitAdder.nbit_adder([[1,1], [1, 1], [1,1], [1,1]])
IO.inspect(res)

#[1, 1, 1, 1, 0]

res2 = NbitAdder.nbit_adder([[1,0], [0, 1], [1,1], [1,0]])
IO.inspect(res)

#[1, 0, 0, 0, 1]

手計算で確認しましたが、良さげですね
この加算器の組み合わせてでコンピューターが動いていると思うと
考えた人はマジで天才ですわ...