読者です 読者をやめる 読者になる 読者になる

mitsu's techlog

通信ネットワークの研究してる大学院生です。備忘録も兼ねて技術系の話を適当に

Areas on the Cross-Section Diagram 解き方メモ

模式断面図の面積 | アルゴリズムとデータ構造 | Aizu Online Judgeを解く時に苦労したのでそのメモφ(・

問題

模式断面図の面積 | アルゴリズムとデータ構造 | Aizu Online Judgeに書いてある通りです、ってのも素っ気ないので以下にスクショ貼ります。

f:id:mtdtx9:20170424200941p:plain

図のような状況において、水たまりそれぞれの面積と全体の面積を出すという問題です。

入力として\_/の列を受け取り、出力は全総面積、水たまりの数、各水たまりの面積になります。

上の図に対応する入力、出力は以下のようになります。 出力は総面積が35、水たまりの数が5、各水たまりの面積が4 2 1 19 9となっていることを示しています。

f:id:mtdtx9:20170424201033p:plain

考え方

最初自力で考えてたんですが、全くわからなかったのでALDS1_3_D: Areas on the Cross-Section Diagram - State-of-the-Arsのコードを参考にしながら考えていきました。

コードを読んで参考になった考え方は、

  • \の場所をスタックに保存することで、/を受け取った時にそれと対応する\を見つけることができる
  • 上記の方法で、対応する\/を用いて面積を計算すること = 横向きに面積を計算していくということ

アルゴリズムとしては、

  • 入力が\のときはそのインデックスをスタックに保存する
  • 入力が/の時はスタックからpopし、現在のインデックスと組み合わせて横向きに面積を計算する
  • 計算した面積の総和をとって総面積を計算する

といった感じです。

ただ、これだけでは各水たまりの面積を計算できないので、

  • /の時にpopしたインデックスと計算した面積のタプルを保存する
  • 必要に応じて上記のタプルを結合していく(水たまりを結合する操作に相当)

ということもします。

以上のために2つのスタックを用意します。

  1. \のインデックスを保存するスタック
  2. popしたインデックスと計算した面積のタプルを保存するスタック

これだけだと意味不明なので例を出しながら説明します。

具体例で説明

具体例として、先ほどの問題の水たまりが1, 19となっている箇所を用いて説明します。

ちなみに入力は\/\\\\/_/\\///となります。 今後はこの入力をインデックスと合わせて説明するので、簡単な表を書いておきます。

index 0 1 2 3 4 5 6 7 8 9 10 11 12 13
value \ / \ \ \ \ / _ / \ \ / / /

index = 0

\なのでスタック1にインデックスを保存します。

stack stack2
0

index = 1

/なのでスタック1からpopします。

面積 = (現在のindex) - (popしたindex) = 1 - 0 = 1となります。 popしたインデックスとこの計算結果をスタック2に保存します。

stack stack2
(0, 1)

index = 2 ~ 5

\らをスタック1に積んでいきます。

stack stack2
5
4
3
2 (0, 1)

index = 6

/なのでスタック1からpopします。

面積 = 6 - 5 = 1となります。

popしたindexの5は、スタック2に保存したタプルに入っているindexである0より大きいので、そのままスタック2に保存します。

stack stack2
4
3 (5, 1)
2 (0, 1)

スタック2が水たまりの様子を表しているので、これは面積1の水たまりが2つあることを示しています。 実際にここまで読み込んだ時の様子は以下のようになっています。

f:id:mtdtx9:20170424225147j:plain:w300

index = 7, 8

index = 7のとき_なので特に何もしません。 index = 8のとき/なので、スタック1からpopします。

面積 = 8 - 4 = 4となります。

popしたindexである4はスタック2に積まれているタプルに保存されたindexである5より小さいので、水たまりは結合されます。 したがって、popしたindexである4と面積 = (タプルに保存されていた面積である) + (先ほど計算した面積) = 1 + 4 = 5を合わせて保存します。 この時のスタックの状態は以下のようになります。

stack stack2
3 (4, 5)
2 (0, 1)

f:id:mtdtx9:20170424225138j:plain:w300

index = 9, 10

ちょっと面倒になってきたのでスタックの状態だけ、、

stack stack2
10
9
3 (4, 5)
2 (0, 1)

index = 11

stack stack2
9 (10, 1)
3 (4, 5)
2 (0, 1)

index = 12

stack stack2
(9, 4)
3 (4, 5)
2 (0, 1)

この時の状態はこんな感じ。

f:id:mtdtx9:20170424225915j:plain:w300

index = 13

/なのでスタック1から3をpopする。

面積 = 13 - 3 = 10となる。

popしたindexである3に対して、スタック2にある(4, 5), (9, 4)はindexの値が大きいのでこれらを結合する。

stack stack2
(3, 19)
2 (0, 1)

図的にはこんな感じ。

f:id:mtdtx9:20170424230620j:plain:w300

結果

スタックの状態は以下のとおり。

したがって、スタック2を見ると、面積1の水たまりと、面積19の水たまりがあることがわかる。

stack stack2
(3, 19)
2 (0, 1)

コード

rubyで書きました。

コードは以下の通り。まだ最適化できそうやけどとりあえずはこれで解けます。

sum = 0
stack = [] # \を受け取ったindexのstack
res = [] # /に対応する\のindexとその時に計算した面積のtupleのstack. 最後に各断面の面積として表示する
gets.split("").each_with_index { |v, i|
  if v == "\\"
    stack << i
  elsif v == "/"
    j = stack.pop
    if !j.nil? # \より先に/が来たときのため
      a = i - j # indexの引き算で横向きに計算する
      sum += a

      loop do
        k, b = res.pop
        if !k.nil?
          if j < k
            a += b
          else
            res << [k, b] # 一旦popしてるので特に何もなければ再度pushして戻す
            break
          end
        else
          break
        end
      end
      res << [j, a]
    end
  end
}
puts sum
if res.size() == 0
  puts "0"
else
  puts "#{res.size()} #{res.map{|n| n[1]}.join(" ")}" # size == 0の時にmapがうまくいかない??
end

githubにもあげてます。

github.com

最後に

今回は最初さっぱりわからず30分くらい問題とにらめっこしてたのですが、横向きに面積を計算する、その時面積はインデックスの引き算で求めることができる、ということに気づくと後はすぐに解けました。

見方を変えれば簡単に解けるけど、その見方に気付けないという典型的な問題でした。

こういう見方は普段から引き出しを増やすしかないのかなーと思うので今後も勉強を続けていきたいなーと思いました。

ruby+opencvで画像処理(2値化)

画像処理の授業取っててruby+opencvで実装したのでその時のことをメモメモφ(・

opencvといえばc++pythonってイメージがあるけど、最近勉強中のrubyで実装したいなーと思ったのでしてみた。

開発環境

rubyopencvを使うためのgemがopencv3系に対応していないのでこんな感じ。

インストール関係で叩いたコマンドは以下の通り。 地味にハマったのはopencv3も入っているからオプションでopencv2の方を見るようにしないといけなかったってところ。

$ brew install opencv
$ gem install ruby-opencv -- --with-opencv-dir=/usr/local/Cellar/opencv/2.4.13.2

2値化とは

画像を白(1)か黒(0)の2つの値のみにすること。 色の情報が必要では無く形に着目するときとかに使うと良い。 また、情報量を減らせるので計算の面でもシンプル&高速になるとかなんとか。

現実世界やと、駐車場でナンバープレート見て清算済みなら勝手に開けてくれるとかあるけど、ああいうときに使われているらしい。

(雑な理解やけど多分だいたいあってる)

2値化の仕方

さて、どうやって2値化するかって話やけど、中身はすごい簡単。 各ピクセルの濃度値が閾値より大きければ黒、小さければ白にするだけ。 自分で実装してもそんなに大変ではないけど、opencvには閾値を渡せば2値化してくれるメソッドがあるので凄い簡単。

2値化するところは以下の通り。 カラーの画像をグレースケールにしてから、threshold()を呼べば終わり。 正直引数については詳しく調べてなくて、255は8bitカラーの最大値からきててとりあえずこう書いとけばいいという雑な理解。

def binarize(file, t)
  image = CvMat.load(file)
  gray_img = image.BGR2GRAY
  bin_img = gray_img.threshold(t.to_i, 255, :binary)
end

2値化は簡単にできるけど、問題になるのはその閾値をどうやって決めるかという話になって、それはいくつかアルゴリズムがあるらしい。

授業で出てきたのは、

の4つ。

今回はこの中で微分ヒストグラム法と判別分析法を実装した。

微分ヒストグラム

微分という名前の通り、濃度値の変化が大きいところに着目して閾値を決める方法。 ヒストグラム法やからヒストグラムを作るんやけど、どういうものかというと横軸が濃度値、縦軸が微分値の和になるようなヒストグラム。 多分普通は縦軸が単に画素数になるから、ここでは微分値を重みとしてちょっと変化させてるという感じ。 微分値の定義としては、| (基準となる画素の濃度値) - (隣の画素の濃度値) |を周辺8マス分計算してその総和を取る。

ヒストグラムを作るところは以下のように実装した。

def create_diff_histogram(gray_img)
  hist = Array.new(256, 0)
  [*0...gray_img.rows].product([*0...gray_img.cols]).each{ |(y, x)|
    b = gray_img.at(y, x)
    diff = 0
    # 周辺8マスとの差分の絶対値の総和の出す.
    # 自分自身との差は0になって結果に影響ないので9マス分計算している.
    [*y-1..y+1].product([*x-1..x+1]).each{ |(y2, x2)|
      if y2.between?(0, gray_img.rows-1) && x2.between?(0, gray_img.cols-1)
        diff += (b[0] - gray_img.at(y2, x2)[0]).abs
      end
    }
    hist[b[0]] += diff
  }
  hist
end

全てのピクセルを網羅するためにx座標とy座標の直積を取る必要があって、それは[*0...gray_img.rows].product([*0...gray_img.cols]).eachと書いた。 product()を使うと直積を取ってくれるのだが、配列で渡す必要があるので[*0...gray_img.rows]としてrangeではなく配列にした。 個人的にはこの行がなんかもうちょっといい感じに書けないのかなーと思ってるけど、書き方がわからないのでこのまま。

各座標における色はat(y, x)で取れる。 このat(y, x)の返り値はCvScalar型になってて、カラーだとRGB値、グレースケールだと輝度値が入っている。 CvScalarは4つのdoubleを持つ配列になっているので、b[0]のような書き方になる。 ちなみに、カラーのときはBGRの順に値を持っているので注意が必要。

あと、個人的に引っかかった点は引数が(x, y)でなく(y, x)だったこと。 最初何も考えずに(x, y)で書いていたのでout of rangeでエラー吐きまくってた。

微分値を計算するところは、周辺8マスを計算するためにまた直積を書いて実装している。 この書き方やと縦横3×3の9マスを網羅してて基準になるマスも入るけど、計算結果は変わらないので9マス分計算している。 あとは、端っこのピクセルやと隣がいない場合があるのでそのためのチェックもしてる。

普通なら2重ループになる直積が一行で書けるのはいいなーと思うけど、なんとなく読みづらいのが直したいポイント.

判別分析法

判別分析法は別名大津の2値化ともいうらしい。

ある値を閾値にしたときの分離度なる値を算出してそれが最大になるような閾値を採用するというアルゴリズム。 分離度は、閾値を元にそれより暗い/明るいの2つのグループに分けて、それぞれのグループでの分散を求めて、クラス内分散やクラス間分散を定義して、って感じで定義される。 この分離度だが、今回はその最大値を求めるという点で大小関係の比較ができれば良いので、結局各グループ内の画素数と濃度値の平均があれば十分になる。

数式の詳しい説明はちょっと長くなるのでこちら

実装としては、閾値をある値にした時の分離度を求めて、それが最大になる閾値を返すというメソッドを作るだけなので簡単で、以下の通り。

def discriminant(file)
  image = CvMat.load(file)
  gray_img = image.BGR2GRAY
  hist = create_histogram(gray_img)
  eval_value, best_t = 0, 0
  (0...255).each{ |t|
    # t := 閾値
    # w1(w2) := 左側(右側)の画素数
    # m1(m2) := 左側(右側)の平均
    w1, w2 = 0, 0
    m1, m2 = 0, 0

    w1 = hist[0..t].reduce(:+)
    m1 = hist[0..t].map.with_index {|n, idx| n * idx}.reduce(:+)/w1 rescue 0

    w2 = hist[t+1..255].reduce(:+)
    m2 = hist[t+1..255].map.with_index(t+1) {|n, idx| n * idx}.reduce(:+)/w2 rescue 0

    e = w1 * w2 * (m1 - m2) ** 2
    if eval_value < e
      eval_value = e
      best_t = t
    end
  }
  best_t
end

create_histogram()は横軸が濃度値、縦軸が画素数のシンプルなヒストグラムを返すように実装したメソッド。 indexが濃度値、値が画素数の配列の形でデータを保持している。

素数は単に配列の値を足していけば良いだけなのでreduce(:+)するだけ。

平均値は、画素数×濃度値を計算するためにindexと値が両方なので、map.with_index{|n, idx| n * idx}のようにしてまず画素数×濃度値を計算した。 そのあとは同じくreduce(:+)で総和を求めて、画素数wで割って終わり。 画素数wは0になることがあるのでZeroDivisionErrorの時のためにrescue 0を書いている。 ただ、この書き方をすると他のエラーを握りつぶしてしまうのでもしかしたらよくないかも。

あと工夫しているところは閾値より大きいところを見るときにhist[t+1..255].map.with_index(t+1)という書き方をしているところ。 配列の後ろ側を切り取ってからmapするときに、もとの配列でのindexを使いたい場合はwith_index(t+1)とすることでindexを任意の値から数えることができる。

実行結果

画像処理定番のlenna使ってみました。 lennaだと2つの手法の差があまり出なくて向き不向きみたいなのが見えなくて残念やけど。

元画像

f:id:mtdtx9:20170414215613p:plain

グレースケールにした画像

f:id:mtdtx9:20170414215630p:plain

微分ヒストグラム法を使って2値化した画像(閾値=129)

f:id:mtdtx9:20170414215647p:plain

判別分析法を使って2値化した画像(閾値=122)

f:id:mtdtx9:20170414215656p:plain

最後に

一応プログラムはgithubにあげてます。

今後も授業でいろいろ実装していく予定なので適宜まとめていこうかなと思ってます。

github.com

2017年2月の振り返り

2月も終わりなので今月の振り返り。

研究

就活に時間割いたので基本的に何もしてない。
M1の進捗とM2の予定をプレゼンしなきゃいけなかったのでそれの作成と発表しかしてないですね。
3月もする予定は特に無いですw

技術

前半はVPS上でdockerいろいろ触ってました。
インフラエンジニアで就活してたのでさすがに知らなさすぎてやばいなと思って勉強してたって感じ。
その流れでgoに入門したりもしてました。

後半はrubyrailsの勉強をしてました。
これはインターン先がrailsだったから勉強してました。
js周りの勉強もその流れでしてました。

基本的には就活に向けてってのが多かったけど、インフラからフロントまで一通り触った1ヶ月だったなーという感想。
今年に入って広く浅くやってる感じになってるから、そろそろどれかに決めて深く勉強したいなーと思ってます。

技術アウトプット

前半はしっかりインプットもアウトプットもできたけど、後半はひたすらインプットしてました。
アウトプットの意識忘れないようにしていかないと。

就活

今月は選考が進んでて面接があったりインターンがあったりという感じ。
その中で人に会う度にそういう考え方もあるのかーと思ってました。
そのおかげで自分の強みや弱み、どういうことに興味があるのか、何をしたいのかとかを深掘りできたから良かったと思う。
院生の就活って推薦使ったり一般でも受ける企業が少なかったりするけど、自分が将来何をしたいのかが不明確なのであれば足を動かしていろんな人に会うと良いと感じました。
適当に選んで数年で転職とかはもったいないと思うし、楽しく仕事するためにしっかりこの機会に頭使わないとと思いました。

まとめ

就活、インターンでいろんなエンジニアの人に会った一ヶ月でした。
特にインターンは大変やったけど楽しい一週間やった。
面接や説明会と違ってランチやといろいろ聞けるのでインターンは良い体験でした。

技術的には様々学んだけど実際に何か作ったりしていないのでちゃんと身についてない感がある。
インターンも終わって自分で好きなものを勉強できる期間に入るので、来月は手も動かしながら深く学んでいきたいと思います。

A Tour of GoでGoに入門した

Goの勉強にはまずA Tour of Go読むと良いっぽかったので読みました。
途中途中に練習問題があって、それを解きながら進めると適度に手も動かせて良かったです。

以下は自分用のまとめです。
最後に練習問題の解答をまとめて載せています。
(合ってるかは保証できません)

Packages, variables, and functions

  • importはまとめて書くのがGo流
import (
	"fmt"
	"math"
)
  • 大文字から始めると他から参照可能。小文字からだと外からはアクセスできない。
  • 関数の宣言は"func 関数名 (変数名 型, 変数名 型) 返り値の型"。型が同じ時はまとめてok。返り値は複数でもok。
func add(x int, y int) int {
	return x + y
}
func add(x, y int) int {
	return x + y
}
func swap(x, y string) (string, string) {
	return y, x
}
  • 返り値にあらかじめ名前をつけておくこともできる。その場合returnだけでよし。
func split(sum int) (x, y int) {
	x = sum * 4 / 9
	y = sum - x
	return
}
  • "var 変数名 型"で変数宣言。初期値を与えないときはゼロ値が入る。
  • 初期化するときは"変数名 := 値"で宣言と初期化をまとめてできる。型は推論される。
var i, j int
k := 3
  • 型変換は"型名(値)"で可能。
  • constキーワードを用いると定数を宣言可能。定数の時は":="でなく"="。

Flow control statements: for, if, else, switch and defer

  • For文は括弧無しversion。式の省略も自由
for i := 0; i < 10; i++ {
    sum += i
}
for ; sum < 1000; {
    sum += sum
}
  • While文はないのでFor文で表現
// while文
for ; sum < 1000; {
    sum += sum
}

// 無限ループ
for {
    // do something
}
  • If文も括弧無しverison。
if x < 0 {
    // do something
}
  • 特殊なのは簡単な式をIf文の中で書ける。スコープはIf文内のみ。
if v := math.Pow(x, n); v < lim {
    return v
}
  • Switch文はcaseで強制break。続けるときは"fallthrough"をcaseの最後に書く。
  • Deferを使うと呼び出し元の関数がreturnする時まで評価を遅らせる。(引数は評価されるがその関数は評価されない)
  • 複数deferがあるときはLIFOの順で処理される。

More types: structs, slices, and maps.

  • ポインタが使える。&でポインタを取得、*でポインタが示す先の値を取得。
func main() {
	i, j := 42, 2701

	p := &i         // point to i
	fmt.Println(*p) // read i through the pointer
	*p = 21         // set i through the pointer
	fmt.Println(i)  // see the new value of i

	p = &j         // point to j
	*p = *p / 37   // divide j through the pointer
	fmt.Println(j) // see the new value of j
}
  • 構造体もある。"type 構造体名 struct"の形で宣言。
  • 構造体へはドットでアクセス。
type Vertex struct {
	X int
	Y int
}
func main() {
	v := Vertex{1, 2}
	v.X = 4
	fmt.Println(v.X)
}
  • ポインタを用いて構造体へアクセスもできる。このとき(*p).Xと書かなくても勝手に解釈してくれる。
func main() {
	v := Vertex{1, 2}
	p := &v
	p.X = 1e9
	fmt.Println(v)
}
  • 配列は"var 変数名 [サイズ]型"で宣言。配列の長さは後から変えれない。
var a [10]int
  • 配列を便利に扱うためにsliceがある。
primes := [6]int{2, 3, 5, 7, 11, 13}
var s []int = primes[1:4]
fmt.Println(s)
// [3 5 7]
  • sliceは元の配列の部分を参照しているだけ。したがって、sliceの値を変えると元の配列の値も変わる。
  • sliceを重ねて新たなsliceを作ることができる。
s := []int{2, 3, 5, 7, 11, 13}
s = s[1:4]
fmt.Println(s) // [3 5 7]
s = s[:2]
fmt.Println(s) // [3 5]
s = s[1:]
fmt.Println(s) // [5]
  • sliceはlengthをcapacityを持っている。lengthはsliceに含まれる要素数。capacityはsliceの最初の要素から数えて元の配列の最後の要素までの数。
  • lengthとcapacityはlen(s)とcap(s)の形で取得可能。
  • make関数を用いてsliceを作成。make関数はarrayを作成しそのsliceを返す。
a := make([]int, 5) // len(a)=5
b := make([]int, 0, 5) // len(b)=0, cap(b)=5
  • append関数を用いてsliceに要素を追加することができる。capacityを超えたとき、より大きなサイズの配列を割り当て直す。
var s []int
s = append(s, 0)
s = append(s, 1)
  • rangeを使えば反復処理ができる。rangeを使うと2つの値が返され、1つ目がindex、2つ目がその要素の値。
  • 使わない時は"_"で捨てることができる。
var pow = []int{1, 2, 4, 8, 16, 32, 64, 128}
for i, v := range pow {
    fmt.Printf("2**%d = %d\n", i, v)
}
for _, value := range pow {
    fmt.Printf("%d\n", value)
}
  • Mapを用いてキーと値を関連づけることができる。
  • make関数を用いてmapを作成することで要素の追加などが可能。
m = make(map[string]Vertex)
m["Bell Labs"] = Vertex{
	40.68433, -74.39967,
}
  • "elem, ok = m[key]"の形でキーに対する要素が存在するかを確認できる。キーがあれば"ok = true"、なければ"ok = false"になる。
m := make(map[string]int)

m["Answer"] = 42 // 初期化
fmt.Println("The value:", m["Answer"])

m["Answer"] = 48 // 更新
fmt.Println("The value:", m["Answer"])

delete(m, "Answer") // 削除
fmt.Println("The value:", m["Answer"])

v, ok := m["Answer"] // 取得
fmt.Println("The value:", v, "Present?", ok)
  • 無名関数を渡すことも可能。
hypot := func(x, y float64) float64 {
	return math.Sqrt(x*x + y*y)
}
fmt.Println(hypot(5, 12))

Methods and interfaces

  • Goにクラスはないが、レシーバ引数を用いてっぽいことができる。レシーバ引数を使う時は"func (変数名 型) 関数名 (引数名 型) 返り値の型 "の形で使う。
  • レシーバ引数を使うとドットを用いてアクセス可能。
  • レシーバを伴うメソッドは同じパッケージ内でする必要がある。
type Vertex struct {
	X, Y float64
}

func (v Vertex) Abs() float64 {
	return math.Sqrt(v.X*v.X + v.Y*v.Y)
}

func main() {
	v := Vertex{3, 4}
	fmt.Println(v.Abs())
}
  • ポインタレシーバを用いて関数を宣言することも可能。レシーバの値を更新する時はこちらで。
func (v *Vertex) Scale(f float64) {
	v.X = v.X * f
	v.Y = v.Y * f
}
  • ポインタレシーバの時は値でもポインタでもどちらを渡してもうまくやってくれる。
var v Vertex
v.Scale(5)  // OK
p := &v
p.Scale(10) // OK
  • インターフェースの宣言もできる。明示的に書かなくても実装すればok。
type I interface {
	M()
}
type T struct {
	S string
}
func (t T) M() {
	fmt.Println(t.S)
}
  • nilをレシーバーにして呼び出すときがあり得るのでnilチェックはするべき
func (t *T) M() {
	if t == nil {
		fmt.Println("<nil>")
		return
	}
	fmt.Println(t.S)
}
  • nilインターフェースの値は値も具体的な型ももたない。メソッドを呼び出すとランタイムエラーになる。
type I interface {
	M()
}

func main() {
	var i I
	describe(i)
	i.M() // ランタイムエラー
}
  • アサーションができる。"t, ok := i.(T)"の形で、iがTを保持してればtにその値が入り、okにtrueが入る。otherwise, t=ゼロ値でok=false。
var i interface{} = "hello"

s, ok := i.(string)
fmt.Println(s, ok)
switch v := i.(type) {
case int:
	fmt.Printf("Twice %v is %v\n", v, v*2)
case string:
	fmt.Printf("%q is %v bytes long\n", v, len(v))
default:
	fmt.Printf("I don't know about type %T!\n", v)
}
  • Goではエラーをerror変数を用いて表す。エラー型は以下のインターフェース。
type error interface {
    Error() string
}

Concurrency

  • goroutineという並列化機構がある。"go f(x, y, z)"と書けば別スレッドで動かせる。
  • チャネル型を用いて値のやりとりができる。
ch := make(chan int) // チャネルの作成
c <- sum // 値の送信
x := <-c // 値の受信
  • チャネルはバッファとして使える
ch := make(chan int, 100) // 2つ目の引数でバッファのサイズを指定
  • これ以上値を送信しないことを示すためにチャネルのcloseができる。受信側は2つ目の引数でcloseされているかを知ることができる。
close(ch) // チャネルを閉じる
v, ok := <-ch // チャネルが閉じていればok=false
  • selectを用いて複数のチャネルを待つことができる。defaultを用いれば待ち状態にはならずdefaultを実行する。
select {
case <-tick:
	fmt.Println("tick.")
case <-boom:
	fmt.Println("BOOM!")
	return
default:
	fmt.Println("    .")
        time.Sleep(50 * time.Millisecond)
}
  • syncパッケージを用いて排他制御などをおこなうことができる。
type SafeCounter struct {
	v   map[string]int
	mux sync.Mutex
}

func (c *SafeCounter) Inc(key string) {
	c.mux.Lock()
	c.v[key]++
	c.mux.Unlock()
}

Execises

  • Loops and Functions
package main

import (
	"fmt"
	"math"

)

func Sqrt(x float64) float64 {
	z := 1.0
	for i := 0; ; i++ {
		diff := ( z * z - x ) / ( 2 * z )
		if math.Abs(diff) < 1e-10 {
			fmt.Printf("loop count is %d\n", i)
			return z
		} 
		z -= diff
	}
}

func main() {
	fmt.Println(Sqrt(2))
}
  • Slices
package main

import "golang.org/x/tour/pic"

func Pic(dx, dy int) [][]uint8 {
	pic := make([][]uint8, dy)
	for i := range pic {
		pic[i] = make([]uint8, dx)
	}
	
	for x := 0; x < dx; x++ {
		for y := 0; y < dy; y++ {
			pic[x][y] = uint8(x^y)
		}
	}
	
	return pic
}

func main() {
	pic.Show(Pic)
}
  • Maps
package main

import (
	"golang.org/x/tour/wc"
	"strings"
)

func WordCount(s string) map[string]int {
	m := make(map[string]int)
	for i := range strings.Fields(s) {
		m[strings.Fields(s)[i]] += 1
	}
	return m
}

func main() {
	wc.Test(WordCount)
}
  • Fibonacci closure
package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func() int {
	n1, n2 := 0, 1
	return func() int {
		n1, n2 = n2, n1+n2
		return n1
	}
}

func main() {
	f := fibonacci()
	for i := 0; i < 10; i++ {
		fmt.Println(f())
	}
}
  • Stringers
package main

import "fmt"

type IPAddr [4]byte

// TODO: Add a "String() string" method to IPAddr.
func (ip IPAddr) String() string {
	return fmt.Sprintf("%v.%v.%v.%v", ip[0], ip[1], ip[2], ip[3])
}

func main() {
	hosts := map[string]IPAddr{
		"loopback":  {127, 0, 0, 1},
		"googleDNS": {8, 8, 8, 8},
	}
	for name, ip := range hosts {
		fmt.Printf("%v: %v\n", name, ip)
	}
}
  • Errors
package main

import (
	"fmt"
)

type ErrNegativeSqrt float64

func (e ErrNegativeSqrt) Error() string {
	return fmt.Sprintf("cannot Sqrt negative number: %f", float64(e))
}

func Sqrt(x float64) (float64, error) {
	if x < 0.0 {
		return 0.0, ErrNegativeSqrt(x)
	}
	z := 1.0
	for i := 0; ; i++ {
		if z2 := z - (z*z-x)/(2*z); z2 - z < 1e-10 {
			return z, nil
		} else {
			z = z2
		}
	}
}

func main() {
	fmt.Println(Sqrt(2))
	fmt.Println(Sqrt(-2))
}
  • Readers
package main

import "golang.org/x/tour/reader"

type MyReader struct{}

func (r MyReader) Read(b []byte) (int, error) {
	b[0] = 'A'
	return 1, nil
}


func main() {
	reader.Validate(MyReader{})
}
  • rot13Reader
package main

import (
	"io"
	"os"
	"strings"
)

type rot13Reader struct {
	r io.Reader
}

func (reader *rot13Reader) Read(b []byte) (n int, err error) {
    n, err = reader.r.Read(b) // bに文字を読み込む
	// 以下で文字を変換する
    for i := range b {
        if ('A' <= b[i] && b[i] <= 'M') || ('a' <= b[i] && b[i] <= 'm') {
            b[i] += 13
        } else if ('N' <= b[i] && b[i] <= 'Z') || ('n' <= b[i] && b[i] <= 'z') {
            b[i] -= 13
        }
    }
    return n, err
}

func main() {
	s := strings.NewReader("Lbh penpxrq gur pbqr!")
	r := rot13Reader{s}
	io.Copy(os.Stdout, &r)
}
  • Images
package main

import (
	"golang.org/x/tour/pic"
	"image"
	"image/color"
)

type Image struct{
	w, h int
}

func (i Image) ColorModel() color.Model {
	return color.RGBAModel 
}

func (i Image) Bounds() image.Rectangle {
	return image.Rect(0, 0, i.w, i.h)
}

func (i Image) At(x, y int) color.Color {
	return color.RGBA{uint8(x*y), uint8(x+y), 255, 255}
}

func main() {
	m := Image{100, 100}
	pic.ShowImage(m)
}
  • Equivalent Binary Trees
package main

import (
	"fmt"
	"golang.org/x/tour/tree"
)

// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
	if t == nil {
		return
	}
	Walk(t.Left, ch)
	ch <- t.Value
	Walk(t.Right, ch)
}

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
	c1, c2 := make(chan int), make(chan int)
    go func() {
        Walk(t1, c1)
        close(c1)
    }()
    go func() {
        Walk(t2, c2)
        close(c2)
    }()
	for {
        x, ok1 := <-c1
        y, ok2 := <-c2
		if !ok1 || !ok2 {
			return true
		}
        if x != y {
            return false
        }
    }
    return true
}

func main() {
	ch := make(chan int)
	t := tree.New(1)
	go func() {
		Walk(t, ch)
		close(ch)
	}()
	for v := range ch {
		fmt.Println(v)
	}
	
	if Same(tree.New(1), tree.New(1)) {
		fmt.Println("Same")
	}
	if !Same(tree.New(1), tree.New(2)) {
		fmt.Println("Not Same")
	}
}
  • Web Crawler
package main

import (
	"fmt"
	"sync"
)

type Fetcher interface {
	// Fetch returns the body of URL and
	// a slice of URLs found on that page.
	Fetch(url string) (body string, urls []string, err error)
}

func Crawl(url string, depth int, fetcher Fetcher) {
	m := make(map[string]bool)
	crawl(url, depth, fetcher, m)
}

// Crawl uses fetcher to recursively crawl
// pages starting with url, to a maximum of depth.
func crawl(url string, depth int, fetcher Fetcher, m map[string]bool) {
	if depth <= 0 {
		return
	}
	mux := &sync.Mutex{}
	mux.Lock()
	if v, ok := m[url]; v && ok {
		return
	}
	m[url] = true
	mux.Unlock()
	
	body, urls, err := fetcher.Fetch(url)
	if err != nil {
		fmt.Println(err)
		return
	}
	fmt.Printf("found: %s %q\n", url, body)
	
	wg := &sync.WaitGroup{}
	for _, u := range urls {
		wg.Add(1)
		go func (u string) {
			crawl(u, depth-1, fetcher, m)
			wg.Done()
		}(u)
	}
	wg.Wait() 
	return
}

func main() {
	Crawl("http://golang.org/", 4, fetcher)
}

// fakeFetcher is Fetcher that returns canned results.
type fakeFetcher map[string]*fakeResult

type fakeResult struct {
	body string
	urls []string
}

func (f fakeFetcher) Fetch(url string) (string, []string, error) {
	if res, ok := f[url]; ok {
		return res.body, res.urls, nil
	}
	return "", nil, fmt.Errorf("not found: %s", url)
}

// fetcher is a populated fakeFetcher.
var fetcher = fakeFetcher{
	"http://golang.org/": &fakeResult{
		"The Go Programming Language",
		[]string{
			"http://golang.org/pkg/",
			"http://golang.org/cmd/",
		},
	},
	"http://golang.org/pkg/": &fakeResult{
		"Packages",
		[]string{
			"http://golang.org/",
			"http://golang.org/cmd/",
			"http://golang.org/pkg/fmt/",
			"http://golang.org/pkg/os/",
		},
	},
	"http://golang.org/pkg/fmt/": &fakeResult{
		"Package fmt",
		[]string{
			"http://golang.org/",
			"http://golang.org/pkg/",
		},
	},
	"http://golang.org/pkg/os/": &fakeResult{
		"Package os",
		[]string{
			"http://golang.org/",
			"http://golang.org/pkg/",
		},
	},
}

docker、jenkinsの導入

今回やること

  • dockerの導入
  • jenkinsの導入

サーバ環境

手持ちのさくらVPS上で環境作ります。

$ cat /proc/version
Linux version 3.13.0-108-generic (buildd@lgw01-60) (gcc version 4.8.4 (Ubuntu 4.8.4-2ubuntu1~14.04.3) ) #155-Ubuntu SMP Wed Jan 11 16:58:52 UTC 2017
$ cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=14.04
DISTRIB_CODENAME=trusty
DISTRIB_DESCRIPTION="Ubuntu 14.04.5 LTS"

dockerの導入

公式サイト(Get Docker for Ubuntu - Docker)を参考に導入しました。
随時更新されていると思うので最新の情報を参照した方が良いと思います。

  • curlをいれておくことをオススメされたのでいれる
$ sudo apt-get update
$ sudo apt-get install curl \
    linux-image-extra-$(uname -r) \
    linux-image-extra-virtual
  • 公式サイト通りにインストールを進める
$ sudo apt-get install apt-transport-https \
                       ca-certificates
$ curl -fsSL https://yum.dockerproject.org/gpg | sudo apt-key add -
$ apt-key fingerprint 58118E89F3A912897C070ADBF76221572C52609D
$ sudo apt-get install software-properties-common
$ sudo add-apt-repository \
       "deb https://apt.dockerproject.org/repo/ \
       ubuntu-$(lsb_release -cs) \
       main"
$ sudo apt-get update
$ sudo apt-get -y install docker-engine
  • 動作確認
$ sudo docker run hello-world

表示を見た感じちゃんと動いていれば大丈夫だと思います。

  • バージョン確認
$ docker version
Client:
 Version:      1.13.0
 API version:  1.25
 Go version:   go1.7.3
 Git commit:   49bf474
 Built:        Tue Jan 17 09:50:17 2017
 OS/Arch:      linux/amd64

というわけで1.13.0が入ったみたいです。
ちなみにインストールする際にバージョンを指定することも可能です。
インストール可能なバージョンは以下のコマンドで確認できます。

$ apt-cache madison docker-engine
  • ユーザグループの作成

sudo無しで実行できるようにdockerグループを作成します。
僕の場合グループは既に存在していたので、ユーザを追加するだけでした。

$ sudo groupadd docker
groupadd: group 'docker' already exists
$ sudo usermod -aG docker $USER

1回ログインし直して設定を適用します。
sudo無しで実行できればokです。

$ docker run hello-world

jenkinsの導入

公式のイメージがあるのでそれを使います。
https://hub.docker.com/_/jenkins/

$ docker search jenkins
NAME                                  DESCRIPTION                                     STARS     OFFICIAL   AUTOMATED
jenkins                               Official Jenkins Docker image                   2475      [OK]
$ docker run -p 8080:8080 jenkins
  • コンテナの状態を確認します。
$ docker ps
CONTAINER ID        IMAGE               COMMAND                  CREATED             STATUS              PORTS                               NAMES
a15377c1714f        jenkins             "/bin/tini -- /usr..."   24 minutes ago      Up 24 minutes       0.0.0.0:8080->8080/tcp, 50000/tcp   pensive_brahmagupta
  • ブラウザからjenkinsをひらきます。(IP_ADDRESS:8080)

docker runコマンドの実行時にパスワードが表示されているのでそちらを入力します。
その後pluginはオススメを選び、ユーザの作成など順序通りに進みます。

f:id:mtdtx9:20170205054918p:plain

dockerの使い方

docker psコマンドを用いてidを取得します。
その後docker stop、docker startコマンドで停止、起動をおこないます。
コンテナの削除はdocker rmコマンドでできます。

$ docker ps -a
CONTAINER ID        IMAGE               COMMAND                  CREATED             STATUS                   PORTS                               NAMES
a15377c1714f        jenkins             "/bin/tini -- /usr..."   About an hour ago   Up 7 seconds             0.0.0.0:8080->8080/tcp, 50000/tcp   pensive_brahmagupta
$ docker stop pensive_brahmagupta
$ docker start pensive_brahmagupta
$ docker stop pensive_brahmagupta # rmの前はstopしなければならない
$ docker rm pensive_brahmagupta

さいごに

dockerとjenkinsの環境構築ができました。
次回はjenkinsの設定をしてテストの自動化などをしていきたいと思います。

2017年1月の振り返り

はやいもので1月ももう最後の日になりました。
今年は毎月振り返りをすることでその月に何を学んだのかを気にするようになりたいなーと思ってます。
というわけで1月の振り返りをしていきます〜。

研究

研究企画書の締め切りが20日にあったため、論文の執筆に主に時間を使っていました。
院に入って新しいテーマに変え、システム系の論文をしっかり書くのは初めてだったので結構時間を割いて書いていました。

技術

ScalaでWebアプリを作るのでその前段階の勉強をしていました。
一応Scalaは昔ちょっと触れたことがあったけど、今回は真面目に一から勉強しました。
dwangoさんの新卒向け資料がすごいわかりやすくて実践的だったのでオススメ。

一応基本的なところは勉強できたので2月以降はコツコツ作っていきます。
今年は絶対にサービス作る٩( 'ω' )و

読書

インフラエンジニア系の本は、インフラエンジニアの選考にエントリーしてるけど、インフラエンジニアって何してるのかとかどういう能力が必要とかがまだ曖昧なのでお勉強という感じです。
数学ガールは最近数学にあまり触れていなかったので楽しく数学したいなということで気晴らしに読んでます。

イベント参加

就活の一環ではあるけど、個人的に興味深い2社で俺得なイベントだったので普通に楽しんじゃいました。

就活

就活についてはこういう場で公にするのはどうかと思うので簡単に。
一応あとで振り返った時にこの頃こういう感じだったなと思い出せればいいかなとは思うので。

業界としてはWeb系の企業を見ています。
インフラに興味あってそっちでエントリーはしてるけど、将来的にはサービス側の開発もしたいし、いろいろできる企業であれば嬉しいなという感じです。
ただ広く浅い器用貧乏になるのも嫌なので自分の武器はしっかり作りたい。
いくつかの企業を見ていて技術に関する考え方に違いがあるなと感じているので、自分の考えに合うところ、自分が得たい経験を積ませてくれるような企業に採用してもらえるといいなと思ってます。
Web系は企業によって色が違うのと、その色は正直採用ページからは見えてこないので、実際に人に会っていかないとなと感じました。
大規模な合説みたいに1回のイベントで複数社と話せる機会がほぼ無いので、地道に足動かしていかないといけないのかなと思いました。

まとめ

主に時間を割いていたのは研究と就活だったけど、その中で技術の勉強ができたのは良かったです。
今年こそWebサービスをリリースするという具体的な目標があるからこそ勉強に身が入っている気がします。
また、こうやって振り返ってみると定量的に勉強量を把握できるので良いなーと。
勉強した気になっているだけでできていないときとかあると思うので今後も続けていきたいと思います。

2月は就活の時間がさらに増えると思うけど、しっかり技術のインプット・アウトプットをしていきたいと思います。
アウトプットについては1月はできなかったので特に。

Swiftで乱択クイックソートを実装してみた

はじめに

僕の好きな本の一つに「数学ガール」があります。 高校生のとき帰りに寄り道した本屋でたまたま出会って以来数学の楽しさを知り、 今情報系の道に進んでいる一つの理由だったりする思い出深い本です。

今回、勉強がてらアルゴリズムを実装したいなーと思ったので数学ガールの中からネタを探すことにしました。 そこで選ばれたのがこちら↓

数学ガール/乱択アルゴリズム (数学ガールシリーズ 4)

数学ガール/乱択アルゴリズム (数学ガールシリーズ 4)

この中から特にクイックソートに焦点をあて、最近勉強中のSwiftで実装してみました。

(ちなみにSwiftではary.sort { $0 < $1 }と書くことで簡単にソートできます。)

クイックソートとは

ソートとは、配列の要素をある規則にしたがって並べなおす操作です。

クイックソートはそのソートをおこなうアルゴリズムの一つなのですが、名前の通り比較的速い(少ないステップ数でソートできる)アルゴリズムです。 詳しくは述べませんが、計算量は平均で{ \displaystyle O(n \log n)}、最悪の場合は{ \displaystyle O(n^2)}になります(nはデータサイズ)。

クイックソートは分割統治法と呼ばれるアイデアを利用しています。 分割統治法とは、大きな問題を小さな問題に分けその小さな問題ごとに解くという手法のことです。 クイックソートでは、ある要素(ピボット)を基準とし、それより大きい数字のグループと小さな数字のグループに分け、それぞれのグループでソートをします(下図参照)。

クイックソートはピボットの選び方を変えることでソートの過程が変化します。 ピボットの選び方は単に配列の最初(最後)の要素を選ぶ方法や、数字からなる配列をソートする場合には平均値や中央値を用いることもあります。

今回は単に配列の最初の要素を選ぶ方法と、数学ガールの中で紹介されているピボットをランダムに選ぶ方法の2種類の方法で実装しました。 ランダムにピボットを選択する方法は乱択クイックソートと呼ばれ、最悪計算量を{ \displaystyle O(n \log n)}に抑えられる方法ということで本の中で紹介されていました。

(計算量の数学的な議論に興味のある方はぜひ数学ガールを読んでみてください!)

f:id:mtdtx9:20161219163820g:plain (引用: Wikipedia)

実装

クイックソートは大きく以下のステップに分かれます。

  1. pivotの選択。
  2. 配列を「pivotより小さい数字、pivot、pivotより大きな数字」の順に並び替える。
  3. pivotの左側(右側)で同様の操作を繰り返す。

クイックソートではSTEP3で再帰処理をするので、そのために関数を

func quicksort (ary: inout [Int], l: Int = 0, r: Int = ary.count - 1)

として実装を進めました。 aryはソートする配列、l, rはそれぞれソートする範囲を示す値(left, right)です。

僕が再帰処理をするときにいつも持っている悩みが、外部から呼び出す関数と内部で再帰的に呼び出す関数で引数を合わせることができず、それぞれ別の関数で実装しなければならないということです。 外部から呼び出すときはシンプルに保ちたいのですが、再帰的に呼び出す際には様々引数が必要になることが多く、一つの関数で実現できないという問題です。 Swiftではデフォルト引数を設定できるので、デフォルト引数を使うことで一つの関数として実現できました。

ここからはSwiftならではの引っかかった点を備忘録的に書いていきます。

関数内で配列を操作する(値渡しと参照渡し)

ソートでは配列の要素を入れ替える操作が必要になります。 しかし、Swiftの場合関数の引数は値渡しになります。 このままでは元の配列の要素を入れ替えることができないので、値渡しではなく参照渡しにする必要があります。

このためには関数定義の際にinoutを用います。 また関数を呼ぶ際にinoutで指定された引数は&argのように&マークを付けて渡します。

クイックソートの実装の際には具体的に以下のように書きました。

func quicksort (ary: inout [Int], l: Int = 0, r: Int = ary.count - 1) {
    // クイックソートの実装
}

// main function
var ary = [5, 6, 2, 3, 8, 1, 9, 7, 4]
quicksort(ary: &ary)

ちなみに、元の配列を維持したまま、ソートされた新しい配列が欲しい時もあると思います。 そのような場合、

func quicksort(ary: [Int]) -> [Int] {
    // ソートする
    return ary
}

のように書きたくなると思います。 しかし、Swiftでは引数はletで渡されるため配列を操作することができません。 このような場合には、

func quicksort(ary: [Int]) -> [Int] {
    var ary = ary
    // ソートする
    return ary
}

と書くことで実現可能になります。

(Swift 3から関数定義の際にvarをつけて変更可能にすることはできなくなりました。)

配列の要素の入れ替え (swap関数)

配列の要素を入れ替える際、Swiftで用意されているswap関数を利用すると簡単に実現できます。 前述の通りSwiftは値渡しなのでswap関数を呼ぶ際には&をつけて参照渡しにする必要があります。

swap関数での注意点は、同じ変数を渡すとエラーを吐き出すことです。 エラーはswapping a location with itself is not supportedと表示されていました。 今回の実装方法ではswapするときに用いる2変数が配列の同じindexを指す可能性があるので、swap関数を使うたびにif文でチェックしています。

(ここらへんをシンプルに書ける方法を模索中です。。)

乱数の生成

乱択クイックソートを実装する際に乱数を生成する必要があります。 乱数を生成する関数は何種類かあるのですが、arc4random_uniform()を用いると良いらしいです。 この関数は「0から引数で与えられた値の間から乱数を生成して返す」関数で、UInt32で値を与える必要があります。 また、戻り値もUInt32で返ってきます。 そのためにUInt32<->Intの型に注意して利用する必要がありました。

乱択クイックソートでピボットを選択する際には以下のように書きました。 arc4random_uniformに渡す際はUInt32にキャストし、戻ってきた値はIntにキャストして使っています。

let ran = Int(arc4random_uniform(UInt32(r - l))) + l

(ここの実装に関しては、配列のindexを示すl, r, ranなどをUInt32で実装すれば、いちいちキャストする必要が無くシンプルに書けたのかなと今思ってます。。)

コマンドラインからの実行

Playgroundを用いてもよかったのですが、興味があったこともありSwiftをコマンドラインから実行するようにして開発を進めました。 gccのようにswiftcを用いてコンパイル→実行というのも可能なのですが、正直面倒です。 そこで調べているとスクリプトのように実行できる方法を見つけたのでその方法を用いました。

そのために必要なことはファイルのはじめに#!/usr/bin/swiftと書くだけです。 これを書いておくとコマンドライン$ ./FILENAME.swiftと実行することができます。

コード

実際のコードを以下に貼っておきます。 一応動作確認しましたが、間違いなど見つけた際にはコメントしていただけると幸いです。

クイックソート

#!/usr/bin/swift

func quicksort (ary: inout [Int], l: Int = 0, r: Int = ary.count - 1)
{
    guard l < r else {
        return
    }
    
    // 配列の左端の値をピポットに選択
    let pivot = ary[l]
    var p = l
    for i in (l+1 ... r) {
        if(ary[i] < pivot) {
            p += 1
            // NOTE: swapping a location with itself is not supported
            if(p != i) {
                 swap(&ary[p], &ary[i])
            }
        }
    }
    // NOTE: swapping a location with itself is not supported
    if(p != l) {
        swap(&ary[l], &ary[p])
    }
    
    quicksort(ary: &ary, l: l, r: p-1)
    quicksort(ary: &ary, l: p+1, r: r)
}

var ary = [5, 6, 2, 3, 8, 1, 9, 7, 4]
quicksort(ary: &ary)
print(ary)

乱択クイックソート

#!/usr/bin/swift

// arc4random_uniform()を使うために必要
import Foundation

func random_quicksort (ary: inout [Int], l: Int = 0, r: Int = ary.count - 1)
{
    guard l < r else {
        return
    }
    
    // 乱数でピボットを選択->ピボットを左に持ってくる
    let ran = Int(arc4random_uniform(UInt32(r - l))) + l
    if(ran != l) {
        swap(&ary[l], &ary[ran])
    }
    
    // あとは通常のquicksortと同じ
    let pivot = ary[l]
    var p = l
    for i in (l+1 ... r) {
        if(ary[i] < pivot) {
            p += 1
            // NOTE: swapping a location with itself is not supported
            if(p != i) {
                swap(&ary[p], &ary[i])
            }
        }
    }
    // NOTE: swapping a location with itself is not supported
    if(p != l) {
        swap(&ary[l], &ary[p])
    }
    
    random_quicksort(ary: &ary, l: l, r: p-1)
    random_quicksort(ary: &ary, l: p+1, r: r)
}

var ary = [5, 6, 2, 3, 8, 1, 9, 7, 4]
random_quicksort(ary: &ary)
print(ary)