Green Software Engineer Blog

エンジニアブログです。技術情報(Go/Java/Docker)や趣味の話も書くかもです。

Go実装の最適化ゲームをしてみた

概要

同僚が「このコード書ける Java のライブラリない?」 と言ってきたので、
Go で実装し返しました。(遊び)
書いたコードがひどそうだったので、最適化をするゲームをしてみました。
結論、あまりいい感じではないですね。

お題

配列が与えられた際に、 指定した最小/最大サイズの文字列を前から順に結合して取得したい とのことでした。(何言ってるかわからない)

例を挙げるとわかりやすいかと思います。

input: [a, b, c, d, e]  
=> output: [ab, abc, abcd, abcde, bc, bcd, bcde, cd, cde, de]  

実装

パート1

まず、最初に思いついて書いたコードが下記になります。
なんかこう色々まずそうです。
Go Playground

func initialShingle(min, max int, arr []string) []string {
    res := []string{}
    if min > max {
        return res
    }

    for i := 0; i < len(arr); i++ {
        cmin := min
        for j := i; j+cmin < len(arr)+1; j++ {
            if len(arr[i:j+cmin]) > max {
                break
            }
            var s string
            for _, v := range arr[i : j+cmin] {
                s += v
            }
            res = append(res, s)
        }
    }
    return res
}

閑話休題

とりあえず、動作確認のためテストコードを書きます。
min/maxの値の境界値等を Table Drive Test で記載しました。 https://github.com/midorigreen/shingle/blob/master/main_test.go#L35

var cases = []struct {
    in  in
    out []string
}{
    {
        in:  in{min: 2, max: 1, arr: []string{"a", "b", "c", "d", "e"}},
        out: []string{},
    },
    {
        in:  in{min: 2, max: 2, arr: []string{"a", "b", "c", "d", "e"}},
        out: []string{"ab", "bc", "cd", "de"},
    },
    {
        in:  in{min: 2, max: 3, arr: []string{"a", "b", "c", "d", "e"}},
        out: []string{"ab", "abc", "bc", "bcd", "cd", "cde", "de"},
    },
    {
        in:  in{min: 2, max: 5, arr: []string{"a", "b", "c", "d", "e"}},
        out: []string{"ab", "abc", "abcd", "abcde", "bc", "bcd", "bcde", "cd", "cde", "de"},
    },
    {
        in:  in{min: 2, max: 100, arr: []string{"a", "b", "c", "d", "e"}},
        out: []string{"ab", "abc", "abcd", "abcde", "bc", "bcd", "bcde", "cd", "cde", "de"},
    },
}

func TestInitialShingle(t *testing.T) {
    for _, c := range cases {
        res := initialShingle(c.in.min, c.in.max, c.in.arr)
        equal(t, res, c.out)
    }
}

ベンチマークも書いたので、この結果が元になります。

% go test -benchmem -run=^$ github.com/midorigreen/shingle -bench ^BenchmarkInitialShingle$

goos: darwin
goarch: amd64
pkg: github.com/midorigreen/shingle
BenchmarkInitialShingle-4              3         388369200 ns/op        354791952 B/op   4621681 allocs/op
PASS
ok      github.com/midorigreen/shingle  1.513s

パート2

alloc回数を減らすために、返却値の初期化を1回にします。
Go Playground

func shingle2(min, max int, arr []string) []string {
    // 省略

    // for alloc array
    maxLen := len(arr)
    resLen := 0
    for maxLen > 0 {
        resLen += maxLen
        maxLen--
    }
    res := make([]string, resLen)

    // 省略
}

ベンチマーク結果

% go test -bench . -benchmem
goos: darwin
goarch: amd64
pkg: github.com/midorigreen/shingle
BenchmarkInitialShingle-4              3         364788315 ns/op        354790757 B/op   4621679 allocs/op
BenchmarkShingle2-4                    3         484458838 ns/op        355455082 B/op   4621651 allocs/op
PASS
ok      github.com/midorigreen/shingle  4.093s

悪くなってますね..

パート3

slice->stringの処理で文字列結合をしている部分を修正しました。
strings.Join([]string, string) を使ってます。
Go Playground

func shingle3(min, max int, arr []string) []string {
    // 省略

            res = append(res, strings.Join(arr[i:j+cmin], ""))

    // 省略
}

ベンチマーク

% go test -bench . -benchmem
goos: darwin
goarch: amd64
pkg: github.com/midorigreen/shingle
BenchmarkInitialShingle-4              5         330830989 ns/op        354791379 B/op   4621680 allocs/op
BenchmarkShingle2-4                    5         332415947 ns/op        355455014 B/op   4621651 allocs/op
BenchmarkShingle3-4                   20          59744819 ns/op        27479328 B/op     186132 allocs/op
PASS
ok      github.com/midorigreen/shingle  7.958s

速度もalloc回数も改善されました。

(補足) strings.Join()関数

実際の実装を見ると、以下の形になってます。

  • len(array)<=3 までは+で結合している
  • それ以降は、まずスライス長を確保している
    • 結合するのではなくstringをbyte配列にcopyしている
  • copyはstring->[]byteへコピーできる模様 doc
(As a special case, it also will copy bytes from a string to a slice of bytes.) 
// Join concatenates the elements of a to create a single string. The separator string
// sep is placed between elements in the resulting string.
func Join(a []string, sep string) string {
    switch len(a) {
    case 0:
        return ""
    case 1:
        return a[0]
    case 2:
        // Special case for common small values.
        // Remove if golang.org/issue/6714 is fixed
        return a[0] + sep + a[1]
    case 3:
        // Special case for common small values.
        // Remove if golang.org/issue/6714 is fixed
        return a[0] + sep + a[1] + sep + a[2]
    }
    n := len(sep) * (len(a) - 1)
    for i := 0; i < len(a); i++ {
        n += len(a[i])
    }

    b := make([]byte, n)
    bp := copy(b, a[0])
    for _, s := range a[1:] {
        bp += copy(b[bp:], sep)
        bp += copy(b[bp:], s)
    }
    return string(b)
}

感想

あまりいい感じの改善にはならなかったですね。
結局、string結合がボトルネックになっていたのでそこを改善すれば、
速度的にはマシになりました。
strings.Join()の挙動とcopyの挙動を知れたのが収穫です。
(よく考えると、どこがネックになっているかの計測を第一にしないといけなかったですね)

書いたコード

github.com

Write Code Every Day (1年目)

概要

Write Code Every Dayを1年間達成しましたので、感想云々を記載します。
一応、日付ずらし等はやらずにいけました。
(ユーザーミスが1日だけあったくらいですかね..)

Write Code Every Dayとは?

毎日コード書いて commit して、GitHubに芝を生やすことです。
昨年のこの時期に、 @t_wada さんのスライドを見てはじめてみました。

(元ネタはこれかな) John Resig - Write Code Every Day

@t_wada さんのスライド Write Code Every Day // Speaker Deck

結果

f:id:midori5:20171203175733p:plain

(色薄..)

作ったもの

主にGolangの勉強系で作ったものが多いです。 (90%くらい..)

gosns

github.com

  • Messaging Sever です
  • Amazon SNSを初めて触れて、書いてみたかったのでGoで書いてみました
  • Pub/Sub Modelをイメージして作成してます
  • mercari/go-httpdoc を使ってテストコードから、API Docを生成したことをよく覚えてます

gtrello

github.com

f:id:midori5:20171203175808p:plain

  • 日報作成ツールです
  • 毎日簡単に書きたくて作りました (まだ使ってます)
  • Trelloの情報をSlackへ送信する流れです
    • $ gtrello → editor open(所感記入) → #times_midori へ配信
  • Trello用のClient ( BurntSushi/toml) をガッツリ使ってます
    • こういうClient利用をきれいにテスト書かねばというのが課題です
  • Go標準のtemplateを利用して、Markdown生成とかしてました
    • (Slack投稿にしたので、最終的にはあんまり残ってないです..)

gmd

github.com

  • コマンド保存ツールです
  • 同じコマンド打つの辛いなぁと思って作りました
  • コマンド自体をまるっと保存します
  • できること
    • 保存
    • 実行
    • 一覧

gchat

github.com

  • チャットサーバーです
  • websocket ってどんな感じなんだろうと思って作りました
    • (まだよくわかってないですね..)
  • gorilla/websocket をwrapしているだけって感じでサクッと作れました

その他

  • 作りかけ放置多数

原則の達成度

  • 毎日コード書くこと
    • 達成度 70%
      • NG Point
        • README.md 更新
        • メモ等のcommit
  • 意味のあるコードを書くこと
    • 達成度 70%
  • 深夜24時前に終わらせること
    • 達成度 80%
      • NG Point
        • 24時超えのcommitは少しはあった
  • 書いたコードをGitHubOSS化すること
    • 達成度 100%

やってみての感想

  • 毎日続けることが大事
    • 毎日やるという制約がちょうどいい
  • 続けたことが見える化できることが大事
    • やったことが見える化できていないと達成度が味わいづらい

メリット

  • 毎日コード書く(commitする) 習慣 は完全に身についた
    • ほぼストレスなくできるようになった
    • 頭の片隅にいつも、今日のcommitはちらつく
    • (勉強する習慣を社会人1年目から作れたのは良かった)
  • Goがとても好きにになった
  • 新しいものに触れるととりあえず手を動かすようになった
    • 芝生えるしちょうどいいと思って、コード書いてみる
      • gRpc
      • GraphQL
      • Eclipse Collection
      • ML
      • etc..

デメリット

  • インプットが少なくなりがち
    • 本読んだり等が二の次になってしまう
  • つなげるための苦肉の策
    • REAMD.md 更新
      • (正直結構やりましたね、 README.md だけの更新..)
    • 家に帰るのが間に合わずスマホからcommit
      • 飲み会で遅くなり、commit → pushできるツールを探しました..
      • source (https://source.ianmcdowell.net/)
        • これでできましたが、pushするためには課金(500円?)が必要で..
        • 泣く泣く課金しました…
        • (後日、一緒に飲み会に行っていた同期が謎に500円くれました)
    • 24時超えcommit
      • 次の日できなさそうな時、やってました

今後

習慣化しているので、続けていこうかと思います。
エンジニアである以上、日々手を動かしていけるようにしていきたいです。

2年目

  • README.md 更新頻度の削減
    • ちゃんとコード書く
    • コード書くための時間づくりも大事にする
  • インプット → アウトプットの習慣化
    • 本をもっと読みたい
      • 基礎知識が低すぎる課題
    • 本を読んだことを活かしてコードを書く
  • 続けること
    • 2年目もがむしゃらにとにかく続ける
  • OSSへcommitする
  • Libraryもしくは有用なツールを公開する
    • ちゃんと使えるものを作りたい
    • 設計からしっかり実施したもの
  • テストコードを書く

まとめ

1年続けてみて、個人的には良い習慣かなと思いました。
基本サボり症である程度の強制力があるものがないと続かない人には、
向いているかと思います。(自分はこれです)
作ったもの等は、稚拙なものが多いですがこれも実力の内なので、
2年目はまた違った結果がみせれると良いかなと思います。

ijaas導入時に詰まった点

概要

ijaasを導入に当たって、変なところで詰まったので残しておきます。

ijaasとは

github.com

Make IntelliJ as a Java server that does autocompletion for Vim.

IntelliJをサーバーとして立てて、Vim からAPI経由で各種機能を
利用できるようにしている模様です。
導入の基本は、 README.md に記載の通りの手順で問題ないはずです。

詰まった点

1. PluginがInstallできない

Setting > Plugins > install plugin from disk 実行時に、下記エラーが発生

f:id:midori5:20171119143922p:plain
incompatible

解消

IntelliJのバージョンが合ってなかったため、発生していた模様です。
build.gradle

def intellijVersion = 'IC-2017.1.5'
if (project.hasProperty('intellij.version')) {
  intellijVersion = getProperty('intellij.version')
}

intellij.version で切り替えができる模様のため、
build.properties を追加して上げれば良いです。

intellij.version=IC-2017.2.6

2. IntelliJ上からbuildPluginするとIdea取得で失敗

S3より、Ideaを取得する部分で失敗していました。

解消

コンソールより実行で解消できました。

% gradle buildPlugin

3. NeoVimから実行できない

ch_open がNeoVimに実装されていない(?) 関係上、利用できませんでした。
(IntelliJへの接続に利用しているため、全般の機能が利用不可かと..)

if exists("$IJAAS_PORT")
  let s:ch = ch_open('localhost:' . $IJAAS_PORT)
else
  let s:ch = ch_open('localhost:5800')
endif

解消

Vim を使う。

4. 保存時の ijaas#buf_write_post() でTimeout

一旦コメントアウトしております。
( complete()organize_import() は利用できました。)

5. IntelliJで該当Projectを起動していないと動作しない

該当ProjectをIntelliJで開いた状態で、利用する必要があるみたいです。

所感

まだ、実用的なコードで試せてないですが、
オートコンプリートはきれいに動作してました。
その他の機能に関しては、上手く動かせない部分もありました。
(機能を理解できていないからかと..)
あと、 メソッドジャンプ機能 が欲しいです。

vim-goの便利コマンド一覧

概要

Goを開発している際に、vim-goを利用しています。

github.com

最低限のコマンドしか利用できていなかったため、
便利なコマンドを再洗い出ししてみます。
(個人的なまとめの意味合いが強いです。)

Commands

下記を参照しております。

vim-go/vim-go.txt at master · fatih/vim-go · GitHub

:GoRun

go run コマンドに相当します。
vim上から実行できるところが便利です。

:GoBuild

go build コマンドに相当します。build後のバイナリは排出しないです。
buildが成功するかどうかを確認する際に利用すると便利です。
成功すると、下記のように出力されます。

vim-go: SUCCESS

失敗すると、quickfix windowに一覧が出力されます。

1 main.go|16| syntax error: unexpected semicolon or newline, expecting comma or }
Quickfix  go build -i . errors
vim-go: FAILED

:GoDef

カーソル以下の、宣言元にjumpできます。
実際の実装がどうなっているか確認したりする際に利用します。
gd で同等の動作をします。
(基本的には、 gd で移動することが多い印象です。)

:GoCallers

カーソル以下のfuncの、呼び出し元を一括検索できます。
(ファイル全検索していたのが、馬鹿らしく思えます..)
注意点 として、複数packageで検索したい場合は、 :GoGuruScope でスコープを設定します。
(どのディレクトリ以下で検索をかけたいかを設定するイメージです。)

:GoGuruScope github.com/midorigreen/gprof

selectPeco()のカーソル上で

:GoCallers

quickfix window

1 main.go|93 col 6| github.com/midorigreen/gmd.selectPeco is called from these 3 sites:
2 /Users/midori/src/golang/src/github.com/midorigreen/gmd/exec.go|28 col 28| static function call from github.com/midorigreen/gmd.cmdExec
3 /Users/midori/src/golang/src/github.com/midorigreen/gmd/hist.go|38 col 28| static function call from github.com/midorigreen/gmd.cmdHist
4 /Users/midori/src/golang/src/github.com/midorigreen/gmd/del.go|29 col 25| static function call from github.com/midorigreen/gmd.cmdDel

:GoCallstack

カーソル以下のfuncのcallstackがquickfix windowで見れます。
(こちらも :GoGuruScope の指定が必要です。)

1 main.go|120 col 7| Found a call path from root to github.com/midorigreen/gmd.run
2 main.go|120 col 6| github.com/midorigreen/gmd.run
3 main.go|138 col 13| static function call from github.com/midorigreen/gmd.main

:GoTest

テストを実行します。

:GoTestFunc

カーソル以下のtest funcのみテストを実行します。

:GoDoc

カーソル以下のGoDocを別windowで参照することができます。 (Shift+k と同等の認識です。)

:GoDocBrowser

カーソル以下のGoDocをブラウザ上で参照することができます。
わざわざGoDocを検索する手間が省けます。

[range]:GoAddTags

range指定した、structにタグを自動で追加してくれます。 Before

type Prof struct {
    Cores     []Core
    Model     string
    ModelName string
    CacheSize int32 
}

After (defaultはjsonタグ)

type Prof struct {
    Cores     []Core `json:"cores"`
    Model     string `json:"model"`
    ModelName string `json:"model_name"`
    CacheSize int32  `json:"cache_size"`
}
  • dbタグ = [range]:GoAddTags db
  • omitempty = [range]:GoAddTags json,omitempty

:GoFillStruct

structの宣言時に、literalをdefault値で埋めてくれます。
初期化時に、各literalを打たなくて良いのが楽です。
Before

prof := Prof{}

After

prof := Prof{
    Cores:     nil,
    Model:     "",
    ModelName: "",
    CacheSize: 0,
}

:GoRename [to]

カーソル以下の文字を、一括でrenameしてくれます。
呼び出し元も、合わせて修正してくれろところが便利です。
func, struct, 変数名 のそれぞれ動作可能です。

:GoPlay

開いているファイルをGo Playgroundで見ることができます。
サンプルコード書いて、展開する場合とかに便利そうです。

所感

他にもまだまだ眠ってそうですが、追加され次第、追記していく形を取ろうかと思います。
ここまで揃っていると、vimで十分な効率で開発できそうです。

技術書展3に行ってきた

概要

技術書展3に行ってきたので、戦利品(2点)をさらします。
まだ、中身は読めていないです。 (あまり買えなかったですね..)

techbookfest.org

戦利品

  1. こうしてぼくらは、書籍を売るアプリを作った
  2. Gopher Walker

こうしてぼくらは、書籍を売るアプリを作った

メルカリカウル を作った話ですね。

f:id:midori5:20171022204626j:plain

気になる内容

  • ChatOpsの勘どころ
  • Goのinterface設計

Gopher Walker

golang.tokyo が出版した本(PDF)です。
Gopherとして読んでみたい本でした。
(無料配布でしたが、少額の寄付をさせていただきました!)

f:id:midori5:20171022210656j:plain

f:id:midori5:20171022205318p:plain

気になる内容

感想

この台風前の雨の中、大勢の方が来られていました。 よくみられた出版物は下記の形の印象でした

  • 機械学習
    • やっぱり多かったですね
  • Swift
    • Swift系の出版物がちらほらみられました

Go系のものがまだまだ少なかったので、増えてくれるとうれしいですね。
次回も覗きに行けたらいいかなぁと思います。

補足

「Goならわかるシステムプログラミング」が買えなかったのが残念です。

Serverless App作成ツール Up を利用してみた

概要

up と呼ばれるツールを利用してみました。
(Introductionをそのまま試してみただけです。)

github.com

upとは?

Serverless Applicationを簡単に作成、デブロイできるツールです。
現状の構築環境と方式は、下記のとおりです。

対応言語

個人的にはGolangに対応しているのが良いですね。
(Lambda自体はまだ、Golang対応していないので)

手順

こちらのサイト に記載のまんまです。

1. Install

curl直接 or npm

# curl版
% curl -sfL https://raw.githubusercontent.com/apex/up/master/install.sh | sh

# npm版 (内部で上記curlを叩いているだけです)
% npm i -g up

2. AWS Credenstialsの設定

~/.aws/credentials に追記が楽かと思います。

[go-up-test]
aws_access_key_id = xxxxxxxx
aws_secret_access_key = xxxxxxxxxxxxxxxxxxxxxxxx

3. up.json(設定ファイル)作成

必須の項目は、profileのみです。
~/.aws/credentials で設定したprofile名と合わせてください。

{
    "profile": "go-up-test",
    "regions": ["ap-northeast-1"]
}

4. 好きな言語でサーバー側の処理を記載

package main

import (
        "fmt"
        "log"
        "net/http"
        "os"
)

func main() {
        addr := ":" + os.Getenv("PORT")
        http.HandleFunc("/", hello)
        log.Fatal(http.ListenAndServe(addr, nil))
}

func hello(w http.ResponseWriter, r *http.Request) {
        fmt.Fprint(w, "Hello go-up-test")
}

5. Deploy

# develop環境へのDeploy
% up

# production環境へのDeploy
% up deploy production

6. 確認

# ブラウザでOpen
% up url --open

# ClipbordにCopy
% up url --copy
% curl "https://xxxxxxx.execute-api.ap-northeast-1.amazonaws.com/development/"
Hello go-up-test

補足

  • up.json に諸々の設定を加えることができそうです
  • up logs コマンドでログが見れます
# past 5 minutes
% up logs

# real time log
% up logs -f
  • up stack delete で作成したresourcesを全て削除できます

サンプルコード

github.com

所感

AWSの設定さえ終わっていれば、非常に簡単にServerless Appを作成できると感じました。Slack Commandが簡単に作れるようなので、試してみたいです。 (元々、SlackのSlash Commandを簡単に作れるという記事を見かけて、興味を持ちました。)

参考

Machine Learning事始め (TensorFlow)

概要

お盆休みを利用して、Machine LearningをTensorFlowのTutorialを通して触れてみました。
解いた問題は、手書き数値の認識です。

Machine Learning

おこなっていることは、任意のグラフに対して近似する関数(=Model)を見つけること

用語

  • データ
    • (Training用) データとそのラベルのセットを持つ必要がある
      • ex) 手書き文字 <-> 書いてある文字
    • (Test用) accuracyを計測するためのデータ
      • 同様にデータと正解ラベルを持つ必要がある
  • weight
  • bias
    • weightと入力値の積をずらす
  • x
    • 入力値
  • y
    • 出力
  • activation function
evidence = W * x + b

-------------------
Tensor
W = weight
x = input
b = bias
-------------------
  • softmax function
    • evidence(活性化関数=activation functionの結果)を確率へと変換する
    • 確率より 0 <= y <= 1
  • loss function
    • 期待値と実際の結果の差分を計測する関数
    • ※ loss functionの結果を0に近づけることが目標
      (=期待値と実際の値が一致する)

Machine Learningの流れ

  1. Trainingデータセットを用意する
  2. activation function(W * x + b)を定義
  3. loss functionを定義
  4. TrainingするOptimizerを決めて、loss functionをセットする
    ex) Gradient Decent (最小勾配法)
  5. Trainingを実施
    テストデータを利用して、関数を何度も実行する。
    実行するたびに、WbをOptimizeする。(TensorFlow利用時は勝手にOptimizeしてくれる)
  6. Modelのaccuracyを測定する

サンプルコード

github.com

手書き数値の認識

CNNを利用せずにの実装もできましたが、accuracyを上げるためにも、CNNを利用したほうが良いみたいです。

Convolutional Neural Network

  • 畳み込みニューラルネットワーク
  • 面を一定の大きさのフィルタで覆い、領域で特徴量を抽出する方法
    • ex) 32x32の画像を5x5のフィルタでスライド1の場合 => 28x28の画像となる
    • pixel単位でないため画像が全体的に類似しているかを判断できる
  • Filter
    • パラメータ
      • filterの数
      • filterの大きさ
      • filterの移動幅
      • padding
        • 画像の端の領域を0で埋める
  • Layer
    • Convolutional Layer
    • Pooling Layer
      • サイズを圧縮する層
      • max poolingが利用される
        • 領域内の最大値を取る手法
    • Fully Connected Layer

肝となると感じた部分

  • 大量のTrainingデータを用意すること
  • accuracyを向上させるためのチューニング

まとめ

基本的に、TensorFlowのTutorialを上からなぞってコード書いてみただけですが、
Machine Learningで何やってるかを少しだけ知ることができました。
絶賛、下記を読み込み中なので読めたらneural networksdeep learningについて
正確に理解できるかなと思います。

Neural networks and deep learning

ひとまずPythonでやってみてますが、GolangでもTensorFlow自体は使えるので、
書き直したいところです。

参考