Golangでpanicを含んだ関数のテストの書き方

package main

import "fmt"

func main() {
    fmt.Println(a(2))
    fmt.Println(a(0.2))
}

func a(number float64) float64 {
    if number < 1 {
        panic("must be number >= 1")
    }
    return number * number
}
package main

import (
    "fmt"
    "testing"
)

func TestA(t *testing.T) {
    tests := []struct {
        Number float64
        Panic  bool
        Want   float64
    }{
        {
            Number: 1,
            Panic:  false,
            Want:   1,
        }, {
            Number: 2,
            Panic:  false,
            Want:   4,
        }, {
            Number: -1,
            Panic:  true,
            Want:   0,
        },
    }
    for i, test := range tests {
        if test.Panic {
            f := func() { a(test.Number) }
            s := fmt.Sprint("case ", i)
            testpanics(f, s, t)
            continue
        }
        if a(test.Number) != test.Want {
            t.Errorf("mismatch case %v: expected %v,  foud %v", i, test.Number, test.Want)
        }
    }
}

func panics(f func()) (b bool) {
    defer func() {
        err := recover()
        if err != nil {
            b = true
        }
    }()
    f()
    return
}

func testpanics(f func(), name string, t *testing.T) {
    b := panics(f)
    if !b {
        t.Errorf("%s shoud panic and does not", name)
    }
}

参考

https://github.com/gonum/blas/blob/447542bc23b84f8daa64470951a57bb6713d15a1/testblas/level1double.go

https://github.com/gonum/blas/blob/447542bc23b84f8daa64470951a57bb6713d15a1/testblas/common.go

github.com

from twitter❤

twitterの❤を本来の使いみち以外に「リンク先をあとでよむ」と「有意義なメモ」の使い方をしてるけど、最近消化不良気味だったのでこっちに振り返りながらメモ。

最近、将棋AIー>碁AIと流行ってるけど、オセロAIが研究されてたのはそのちょっと前? 自分ではじめてゲーム探索を書いた時にも「リバーシアルゴリズム」という本を参考にした。このときはCODEVSだったのでオセロAIも一度やってみたい。

最近、全探索を見逃しがち

自分のやりたいことは機械学習、深層学習よりも強化学習よりなのかなと思い始めた

大学で助教と一緒に検討した時はmoodleでできるようしたいと話をしたことがある、その後進展はない。

じつはc++のnext_permutationが未だに理解できない

第一志望だった研究室もcookpadからデータを提供されてなにかしたっぽい

やるやる詐欺をしてしまった人狼知能。標準入出力形式にならないかなあ・・・

はまった

組み合わせ・順列の実装は未だに苦手

わかる

ただのリンク集の記事になってしまった。

Linux Mint デスクトップ環境 2017

k0kubun.hatenablog.com

インスパイアです。

そもそもなぜLinuxデスクトップをつかているのか

自作PCでLinuxMintを使っているので環境を揃えたかった。 あとはインスパイア元とほぼ一緒。 環境は自作機PCとMacBookPro(late2013) どちらも英語キーボードを使用

現在のLinuxデスクトップ環境

ディストリビューション: Linux Mint Cinnamon 18.1

UbuntuがUnityを使い始めてからは、Linux Mintに移行しました。 Cinnamonは3Dアクセラレータ推奨ですが、自分の環境では困らない。 MATE(またはUbuntu MATE)と比較すると、好みの問題だと思います。

キーリマッパー:xmodmap+xcape

SandS用に使ってます。

windymelt.hatenablog.com

ターミナル: terminator

F12キーで表示の切り替えができるように、キーの割り当て -> hide_window をF12にしてます。 “~"がでてきて、うまく動かないときは別にGuake Terminalをインストールしておくと治ったりします。

日本語入力: Fcitx+mozc

fcitxの設定->全体の設定(タブ)->拡張オプションの表示☑->

“入力メソッドをオンに" Ralt

“入力メソッドをオフに" Lalt

で, 元karabiner風の切り替えにします。

フォント: デフォルト

ブラウザ:Google Chrome

ツイッター:Google Chrome

パスワードマネージャー: 1Password(iPhone)

これはこれからどうしようか迷い中 とりあえず,よく使うパスワードはGoogleChromeに覚えさせてはいる

音楽プレイヤー: 作業用BGMを検索

最近はアベマTVがつけっぱなしです。。。

MacBookProでのインストール

自作PC(LinuxMint)の"USBイメージライタ"を使って、ダウンロードしたLinux Mintのisoを焼きます。 (MacBookProの)ディスクユーティリティでLinux用のパーテーションを作り電源を切る。 Linux Mintの入ったUSBをMacBookProに挿してoptionキーを押しながら起動させればUSBの"EFI boot"がでてくるので選択してGRUBの画面に進みます、そこでLinux Mintを選択して起動させます。 文字が小さいので Menu->General->Desktop Scaling でDouble(Hi-DPI)を選択します。(これはインストール後にもやります) デスクトップのInstall Linux Mintを選択して、進んでいきます。 Installation type では一番下のSomething elseを選択して、あとはいい感じに進んでください(自己責任で)

このやり方でインストールすると、MacBookProを起動した時はLinux Mintが立ち上がります。macOSを起動させたいときはoptionキーを押しながら起動してHDDを選択します。

起動時に毎回選択したいときにはrEFIndを使うか、GRUBmacOS(/System/Library/CoreServices/boot.efi)を追加する等があるようですがやってません(後者を試したが失敗)。

キーボード

MacBookProのUSキーボードはスペースキーの左右にcommandキーがありますが、自作PCはaltなので後者に合わせます。 menu -> Keyboard -> Options… -> Alt/Win key behavior で Alt is swapped with Win を☑します。 お好みで Ctrl key posotionで Swap Ctrl and Caps Lock を ☑

Function Key

ファンクションキーをデフォルトで使用したいので以下の設定を使う。 AppleKeyboard - Community Help Wiki With .conf file (Recommended)

$ echo options hid_apple fnmode=2 | sudo tee -a /etc/modprobe.d/hid_apple.conf
$ sudo update-initramfs -u -k all
$ sudo reboot

自作PCとMBPではMintの設定言語が違う(日本語と英語)ので記事内ではちょっと混じっちゃいました。

おしまい。

Go言語のpprofとFlameGraph

Go pprof 入門編 (CPU Profile とコマンドラインツール) : KLabGames Tech Blog

Go で利用できるプロファイリングツール pprof の読み方 - Qiita

GolangでFlame Graphを描く | SOTA

GitHub - pkg/profile: Simple profiling for Go

GitHub - uber/go-torch: Stochastic flame graph profiler for Go programs

GitHub - brendangregg/FlameGraph: stack trace visualizer

上記のリンクを参考に先日行われたCODEVSforSTUDENTのプログラムのFlameGraphをだします

予選落ち(全体25位学生18位)しましたが、決勝進出者のプログラム提出日はまだ先なので、細かいことは書きません。

CODE VS for STUDENT 予選7位! - ぴろずメモ

www.youtube.com

pkg/profile

Go言語には標準にプロファイル用のruntime/pprofnet/http/pprofがありますが、runtime/pprofを使いやすくした、Dave Cheney氏のpkg/profileを使います。(元runtime/pprof)

go get github.com/pkg/profile

インストールしてmain関数に1行加えるだけです。

import "github.com/pkg/profile"

func main() {
    defer profile.Start().Stop()
    ...
}

テストには実際の試合の入力ログを使いますが、試合終了のフラグがないのでログの最後にENDを加えて、ソースコードも正常終了させるように変更しておきます。

実際にビルドして、実行します。

[fmhr@Sarah] ~/Dropbox/projects/CODEVS/CODEVSforSTUDENT/go
% go build -o tmp/outprofile src/*.go                                       
[fmhr@Sarah] ~/Dropbox/projects/CODEVS/CODEVSforSTUDENT/go
% tmp/outprofile < sampleInput/1P_20161111_135322_00000000000000000000_00003_stdin.txt
2016/11/21 14:30:43 profile: cpu profiling enabled, /tmp/profile918389017/cpu.pprof
fmhr
W: 4000 H: 5 s: 2000
[1 1 8 8 11]
0(0)0 / 0(0)0
0 0
0 turn: -180 / 180
[1 6 7 11 20]
3(0)0 / 3(0)0
5 0
1 turn: 1.64 / 178.36
[4 4 8 20 16]
6(0)0 / 6(0)0
6 1
()
40 turn: 0.014 / 102.107
GAMEOVER
0 0
41 turn: 0.006 / 102.101
SetTurnSet失敗
2016/11/21 14:32:16 profile: cpu profiling disabled, /tmp/profile918389017/cpu.pprof

デバッグ用のエラー出力と試合用の出力も入ってます(この試合は40ターン目で負けたみたいです)SetTurnSet失敗が追加したENDを読み込んでループから抜けています。

とりあえず、/tmp/profile918389017/cpu.pprofができてることが1行目でわかる。 これを見てみます。

% go tool pprof /tmp/profile918389017/cpu.pprof    
Entering interactive mode (type "help" for commands)
(pprof) top5
79.84s of 98.22s total (81.29%)
Dropped 130 nodes (cum <= 0.49s)
Showing top 5 nodes out of 58 (cum >= 2.62s)
      flat  flat%   sum%        cum   cum%
    56.09s 57.11% 57.11%     66.24s 67.44%  main.deleteLoop
     9.67s  9.85% 66.95%      9.67s  9.85%  runtime.duffcopy
     7.25s  7.38% 74.33%      7.45s  7.59%  main.moveBlock
     4.21s  4.29% 78.62%      6.93s  7.06%  runtime.scanobject
     2.62s  2.67% 81.29%      2.62s  2.67%  math/rand.(*rngSource).Seed
(pprof) 

main.deleteLoop関数が実行時間の6割を占めてるのがわかります。 この関数はゲーム内のフィールドを縦横斜め(2回)を走査して、消えるブロックがなくなるまでループする、ゲームのシミュレータの主要部分です。 (pprof) web をするとグラフにしてくれるのですが見え過ぎるで今回はお預けします。

この結果を使って、FlameGraphをみてみます。

Go言語のpprofからflame graphを見るためには、uber/go-torchを使います。

GitHub - uber/go-torch: Stochastic flame graph profiler for Go programs

go get github.com/uber/go-torch
[fmhr@Sarah] ~/Dropbox/projects/CODEVS/CODEVSforSTUDENT/go
% cd /tmp/profile918389017        
[fmhr@Sarah] /tmp/profile918389017
% ls
cpu.pprof
[fmhr@Sarah] /tmp/profile918389017
% go-torch cpu.pprof 
INFO[15:09:41] Run pprof command: go tool pprof -raw -seconds 30 cpu.pprof
FATA[15:09:41] Failed: could not generate flame graph: Cannot find flamegraph scripts in the PATH or current directory. You can download the script at https://github.com/brendangregg/FlameGraph. These scripts should be added to your PATH or in the directory where go-torch is executed. Alternatively, you can run go-torch with the --raw flag.

肝心のflame graphがはいってませんでした。 PATHかディレクトリにスクリプトを入れろと言われてます。今回は必要なスクリプトだけつっこんでおきます。

[fmhr@Sarah] /tmp/profile918389017
% wget https://raw.githubusercontent.com/brendangregg/FlameGraph/master/stackcollapse-perf.pl
% wget https://raw.githubusercontent.com/brendangregg/FlameGraph/master/flamegraph.pl

パーミションを変更して実行可能にします

% chmod 777 flamegraph.pl stackcollapse-perf.pl 

これで準備完了です。

flame graph

[fmhr@Sarah] /tmp/profile918389017
% go-torch cpu.pprof                           
INFO[15:18:02] Run pprof command: go tool pprof -raw -seconds 30 cpu.pprof
INFO[15:18:02] Writing svg to torch.svg

目的のtorch.svgがでてきました。 (hatenablogにsvgファイルが出せないようなので、jpegに変換してます) f:id:fmhr29:20161121153128j:plain おしまい

Go言語によるWebアプリケーション開発

ソースコードの写生をまるまる1冊したのははじめてだった。テストを先に書く部分(TDD)があるのだけど、エディタ(Intellij)で真っ赤にエラーだしながら進めるのはとても気持ち悪かった。筆者の頭の中に設計があるからできることだと思うんだけど、本に書いてあってほしかった。

p.106 12行目

[誤] log.Faralf("%qに類語はありませんでした\n")
[正] log.Faralf("%qに類語はありませんでした\n", word)

yukicoder No.416 旅行会社

問題

No.416 旅行会社 - yukicoder

1~N個の島とM本の橋がある。Q個の橋が順に破壊されていく。島1から到達できなくなるタイミングはいつか。

解法1 union-find木

最後まで壊れなかった橋を初期状態として、逆順に橋を継ぎ足していく。集合データを持たせたunion-find木を使い、結合する集合の片方に島1があるときに、ない方の集合に含まれる島の値を更新していく。集合データの管理には"データ構造をマージする一般的なテク"を使う。

解法2 ダイクストラ法(改変)

解説放送で紹介されたやつ。 順に壊れていく橋のコストを1~Qにしてこれを生存時間と考える。最後まで壊れない橋と島1をinf, その他の島nを-1としておく。行き先の島の生存時間は通る橋と出発点の島の生存時間の短い方をとる。

解法1 コード

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

func main() {
    sc.Split(bufio.ScanWords)
    n := nextInt()
    m := nextInt()
    q := nextInt()
    bridge := make([]nodes, m)
    for i := 0; i < m; i++ {
        bridge[i].a = nextInt()
        bridge[i].b = nextInt()
    }
    crashed := make(map[int]bool)
    crash := make([]nodes, q)

    for i := 0; i < q; i++ {
        crash[i].a = nextInt()
        crash[i].b = nextInt()
        crashed[crash[i].a*1000000+crash[i].b] = true
    }

    uf := makeUnionFind(n + 1)
    // 壊れない橋を追加する
    for i := 0; i < m; i++ {
        if !crashed[bridge[i].a*1000000+bridge[i].b] {
            //fmt.Println("追加1: ", bridge[i].a, bridge[i].b)
            uf.Set(bridge[i].a, bridge[i].b)
        }
    }
    ans := make([]int, n+1)
    // 1とつながっている島
    for _, i := range uf.link[uf.Root(1)] {
        ans[i] = -1
    }
    //fmt.Println("-1ケース, ", ans)

    // 壊れる橋を逆順に追加しながら、つながっているかチェックする
    for i := q - 1; i >= 0; i-- {
        //fmt.Println("追加逆順1:",i,crash[i].a, crash[i].b)

        x := crash[i].a
        y := crash[i].b
        if uf.Same(x, y) {
            continue
        }
        if uf.Same(1, uf.Root(y)) {
            x, y = y, x
        }
        if uf.Same(1, x) {
            for _, h := range uf.link[uf.Root(y)] {
                if ans[h] == 0 {
                    ans[h] = i + 1
                }
            }
        }
        uf.Set(x, y)
    }
    for i := 2; i <= n; i++ {
        fmt.Println(ans[i])
    }
}

type nodes struct {
    a, b int
}

type UnionFind struct {
    par  []int   // 親
    size []int   // 重み
    link [][]int // グループ
}

func makeUnionFind(count int) *UnionFind {
    par := make([]int, count)
    size := make([]int, count)
    link := makeDoubleSliceInt(count, 1)
    for i := 0; i < count; i++ {
        par[i] = i
        size[i] = 1
        link[i][0] = i
    }
    return &UnionFind{par: par, size: size, link: link}
}

func (uf *UnionFind) Root(a int) int {
    for uf.par[a] != a {
        uf.par[a] = uf.par[uf.par[a]]
        a = uf.par[a]
    }
    return a
}

func (uf *UnionFind) Set(a, b int) {
    a = uf.Root(a)
    b = uf.Root(b)
    if a != b {
        if uf.size[a] > uf.size[b] {
            a, b = b, a
        }
        uf.par[a] = b
        uf.size[b] += uf.size[a]
        uf.link[b] = append(uf.link[b], uf.link[a]...)
    }
}

func (uf *UnionFind) Same(a, b int) bool {
    return uf.Root(a) == uf.Root(b)
}

func makeDoubleSliceInt(y, x int) (r [][]int) {
    r = make([][]int, y)
    for i := range r {
        r[i] = make([]int, x)
    }
    return
}

var sc = bufio.NewScanner(os.Stdin)

func nextLine() string {
    sc.Scan()
    return sc.Text()
}

func nextInt() int {
    i, _ := strconv.Atoi(nextLine())
    return i
}

解法2 コード

package main

import (
    "bufio"
    "container/heap"
    "fmt"
    "os"
    "strconv"
)

const inf int = 1 << 25

func main() {
    sc.Split(bufio.ScanWords)
    // indexと島を合わせるために孤立した島0を加えておく
    n := nextInt() + 1
    m := nextInt()
    q := nextInt()
    bridge := make([]nodes, m)
    crashed := make(map[int]int)
    for i := 0; i < m; i++ {
        bridge[i].a = nextInt()
        bridge[i].b = nextInt()
        crashed[bridge[i].a*1000000+bridge[i].b] = inf
    }
    crash := make([]nodes, q)
    for i := 0; i < q; i++ {
        crash[i].a = nextInt()
        crash[i].b = nextInt()
        crashed[crash[i].a*1000000+crash[i].b] = i + 1
    }

    // グラフ
    g := newGraph(n)
    for i := 0; i < m; i++ {
        a := bridge[i].a
        b := bridge[i].b
        cost := crashed[a*1000000+b]
        g[a] = append(g[a], Edge{to: b, time: cost})
        g[b] = append(g[b], Edge{to: a, time: cost})
    }
    // 改変ダイクストラ
    d := g.dijkstar(n, 1)

    // 最後までつながっている島: -1
    // 最初からつながっている島: 0
    for i := 2; i < n; i++ {
        switch d[i] {
        case inf:
            fmt.Println("-1")
        case -1:
            fmt.Println("0")
        default:
            fmt.Println(d[i])
        }
    }
}

type nodes struct {
    a, b int
}

type Edge struct {
    to   int
    time int
}
type Graph [][]Edge

func newGraph(n int) Graph {
    g := make(Graph, n)
    for i := range g {
        g[i] = make([]Edge, 0)
    }
    return g
}

func (g *Graph) dijkstra(n, s int) []int {
    d := make([]int, n) 
    for i := range d {
        d[i] = -1
    }
    que := make(PriorityQueue, 0)
    heap.Init(&que)
    d[s] = inf
    heap.Push(&que, &Item{node: s, time: inf})
    for que.Len() > 0 {
        p := heap.Pop(&que).(*Item)
        v := p.node
        // 生存時間が島より短い橋は無視する
        if d[v] > p.time {
            continue
        }
        for i := 0; i < len((*g)[v]); i++ {
            e := (*g)[v][i]
            t := min(d[v], e.time) 
            if d[e.to] < t {
                d[e.to] = t
                heap.Push(&que, &Item{time: d[e.to], node: e.to})
            }
        }
    }
    return d
}

// https://golang.org/pkg/container/heap/
// An Item is something we manage in a priority queue.
type Item struct {
    node int // The value of the item; arbitrary.
    time int // The priority of the item in the queue.
    // The index is needed by update and is maintained by the heap.Interface methods.
    index int // The index of the item in the heap.
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    // We want Pop to give us the highest, not lowest, priority so we use greater than here.
    return pq[i].time > pq[j].time
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i
    pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    item.index = -1 // for safety
    *pq = old[0 : n-1]
    return item
}

func (pq *PriorityQueue) update(item *Item, value int, priority int) {
    item.node = value
    item.time = priority
    heap.Fix(pq, item.index)
}

var sc = bufio.NewScanner(os.Stdin)

func nextLine() string {
    sc.Scan()
    return sc.Text()
}

func nextInt() int {
    i, _ := strconv.Atoi(nextLine())
    return i
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

yukicoder No.94 圏外です。(EASY) Union-Find

No.94 圏外です。(EASY) - yukicoder

問題

二人は無線機をもっている。 N個の中継局(Xi,Yi)があり、二人が自由に移動できるとき、 二人が通信できる直線距離(ユークリッド距離)の最大値を求めよ。

無線機<->無線機 1km

中継局<->中継局 10km

無線機<->中継局 1km

N(0<=N<=1000)

解法

通信できる最も遠い2つの中継局を使うとき、二人の距離は最大になる。 中継局Aと中継局Bが通信できるかどうかをUnion Findで判定する。

package main

import (
    "fmt"
    "math"
)

type xy struct {
    x int
    y int
}

func isLink(a, b, c, d int) bool {
    return 100 >= (c-a)*(c-a)+(d-b)*(d-b)
}

func distance(a, b, c, d int) float64 {
    x := math.Sqrt(float64((c-a)*(c-a) + (b-d)*(b-d)))
    return x
}

func main() {
    var N int
    fmt.Scan(&N)
    repeater := make([]xy, N)
    for i := 0; i < N; i++ {
        fmt.Scan(&repeater[i].x, &repeater[i].y)
    }
    uf := NewUnionFind(N)
    for i := 0; i < N; i++ {
        for j := i; j < N; j++ {
            if isLink(repeater[i].x, repeater[i].y, repeater[j].x, repeater[j].y) {
                uf.Unit(i, j)
            }
        }
    }
    ans := 1.0
    for i := 0; i < N; i++ {
        for j := 0; j < N; j++ {
            if uf.Same(i, j) {
                ans = max(ans, 2+distance(repeater[i].x, repeater[i].y, repeater[j].x, repeater[j].y))
            }
        }
    }
    fmt.Println(ans)
}

func max(a, b float64) float64 {
    if a > b {
        return a
    } else {
        return b
    }
}

type UnionFind struct {
    par    []int // 親
    weight []int // 重み
}

func NewUnionFind(count int) *UnionFind {
    par := make([]int, count)
    weight := make([]int, count)
    for i := 0; i < count; i++ {
        par[i] = i
        weight[i] = 1
    }
    return &UnionFind{par: par, weight: weight}
}

func (uf *UnionFind) Find(x int) int {
    for uf.par[x] != x {
        uf.par[x] = uf.par[uf.par[x]]
        x = uf.par[x]
    }
    return x
}

func (uf *UnionFind) Unit(x, y int) {
    x = uf.Find(x)
    y = uf.Find(y)
    if x == y {
        return
    }
    if uf.weight[x] > uf.weight[y] {
        x, y = y, x
    }
    uf.par[x] = y
    uf.weight[y] += uf.weight[x]
}

func (uf *UnionFind) Same(x, y int) bool {
    return uf.Find(x) == uf.Find(y)
}

重み付きUnion-Findは以下を参照

https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf