sliceとmapのdelete(+make)はどちらが速いのか

Golangでmapとsliceどちらが速いのかに引き続いて、要素を削除する場合のベンチマークを取ってみる。

やり方

slice

メモリリークしないようにSliceTricksにある以下の方法で要素を削除する。

copy(a[i:], a[i+1:])
a[len(a)-1] = nil // or the zero value of T
a = a[:len(a)-1]

map

組み込みのdeleteで削除する

delete(map[typeA]typeB, typeA)

条件

  • sliceは[]int型とする
  • mapはmap[int]int型とする
  • sliceから削除したい要素のindexはn/2を使う
  • mapから削除したい要素をn/2とする

環境

macOS High Sierra version 10.13.4(17E202)
MacBook Pro (Retina, 13-inch, Early 2015)
2.7 GHz Intel Core i5
16 GB 1867 MHz DDR3
Intel Iris Graphics 6100 1536 MB
❯ go version
go version go1.10.1 darwin/amd64

実装

map, sliceどちらも削除前の状態を毎回使いまわす必要があるが、どちらも参照型で実装されるので、毎回makeで作り直すことにする。 make自体がmapとsliceで差がある(Appendix参照)ので、それぞれmakeするだけベンチマークも測定し、差分(make+delete-make)を結果とする。 makeに掛かる時間は要素数に単調増加するので、それぞれ差分の計算は、同じ要素数でmakeした結果から求める。

ベンチマークの実装は以下の通り。

slice

func benchmarkOfDeleteFromSlice(n int, b *testing.B) {
    idx := n / 2

    for i := 0; i < b.N; i++ {
        s := make([]int, n)
        copy(s[idx:], s[idx+1:])
        s[len(s)-1] = 0
        s = s[:len(s)-1]
    }
}

func benchmarkOfMakeSlice(n int, b *testing.B) {
    for i := 0; i < b.N; i++ {
        _ = make([]int, n)
    }
}

map

func benchmarkOfDeleteFromMap(n int, b *testing.B) {
    idx := n / 2

    for i := 0; i < b.N; i++ {
        m := make(map[int]int, n)
        delete(m, idx)
    }
}
func benchmarkOfMakeMap(n int, b *testing.B) {
    for i := 0; i < b.N; i++ {
        _ = make(map[int]int, n)
    }
}

結果

f:id:cipepser:20180508221142p:plain

素数が少ないとmakeに掛かる時間が測定によってばらつきがあり、差分がマイナスになったが、要素数が1000を超えたあたりからmapよりsliceが有利であることがわかる。またsliceは削除に要する時間が要素数に依らず、ある程度一定の値となっている。

Appendix

ベンチマーク結果の生データは以下の通り。

BenchmarkOfDeleteFromSlice10-4        30000000           40.0 ns/op
BenchmarkOfDeleteFromSlice30-4         20000000           66.5 ns/op
BenchmarkOfDeleteFromSlice70-4         10000000          134 ns/op
BenchmarkOfDeleteFromSlice100-4        10000000          229 ns/op
BenchmarkOfDeleteFromSlice300-4         3000000          554 ns/op
BenchmarkOfDeleteFromSlice700-4         1000000         1034 ns/op
BenchmarkOfDeleteFromSlice1000-4        1000000         1478 ns/op
BenchmarkOfDeleteFromSlice3000-4         300000         3903 ns/op

BenchmarkOfMakeSlice10-4               50000000           33.8 ns/op
BenchmarkOfMakeSlice30-4               20000000           59.6 ns/op
BenchmarkOfMakeSlice70-4               10000000          119 ns/op
BenchmarkOfMakeSlice100-4              10000000          173 ns/op
BenchmarkOfMakeSlice300-4               3000000          494 ns/op
BenchmarkOfMakeSlice700-4               2000000          938 ns/op
BenchmarkOfMakeSlice1000-4              1000000         1465 ns/op
BenchmarkOfMakeSlice3000-4               300000         3785 ns/op

BenchmarkOfDeleteFromMap10-4           20000000          102 ns/op
BenchmarkOfDeleteFromMap30-4            5000000          255 ns/op
BenchmarkOfDeleteFromMap70-4            3000000          604 ns/op
BenchmarkOfDeleteFromMap100-4           3000000          583 ns/op
BenchmarkOfDeleteFromMap300-4           1000000         1546 ns/op
BenchmarkOfDeleteFromMap700-4            500000         2992 ns/op
BenchmarkOfDeleteFromMap1000-4           200000         6079 ns/op
BenchmarkOfDeleteFromMap3000-4           100000        12120 ns/op

BenchmarkOfMakeMap10-4                 20000000           97.8 ns/op
BenchmarkOfMakeMap30-4                  5000000          251 ns/op
BenchmarkOfMakeMap70-4                  3000000          590 ns/op
BenchmarkOfMakeMap100-4                 2000000          580 ns/op
BenchmarkOfMakeMap300-4                 1000000         1563 ns/op
BenchmarkOfMakeMap700-4                  500000         3100 ns/op
BenchmarkOfMakeMap1000-4                 200000         5980 ns/op
BenchmarkOfMakeMap3000-4                 100000        11305 ns/op

すべてまとめてグラフにすると以下の通り。

f:id:cipepser:20180508221231p:plain

makeのみの所要時間は以下の通り。

f:id:cipepser:20180508221234p:plain

一貫して、sliceのほうがmakeに要する時間は少なかった。 sliceとmapの内部実装も以下の通りで、sliceのほうが初期化に掛かる時間が少ないと思われる。

sliceの内部実装

type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}

mapの内部実装

// A hash iteration structure.
// If you modify hiter, also change cmd/internal/gc/reflect.go to indicate
// the layout of this structure.
type hiter struct {
    key         unsafe.Pointer // Must be in first position.  Write nil to indicate iteration end (see cmd/internal/gc/range.go).
    value       unsafe.Pointer // Must be in second position (see cmd/internal/gc/range.go).
    t           *maptype
    h           *hmap
    buckets     unsafe.Pointer // bucket ptr at hash_iter initialization time
    bptr        *bmap          // current bucket
    overflow    *[]*bmap       // keeps overflow buckets of hmap.buckets alive
    oldoverflow *[]*bmap       // keeps overflow buckets of hmap.oldbuckets alive
    startBucket uintptr        // bucket iteration started at
    offset      uint8          // intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1)
    wrapped     bool           // already wrapped around from end of bucket array to beginning
    B           uint8
    i           uint8
    bucket      uintptr
    checkBucket uintptr
}

References

【nsdi'18論文】Stateless Datacenter Load-balancing with Beamerを読んだ

2018年4月9日〜11日に開催されていたnsdi'18で Community Awardに選ばれたStateless Datacenter Load-balancing with Beamerの論文を読んだのでメモ書きを残します。 こちらで発表も見れます。 自分の理解の範囲で記載しているので、詳細や正確性を求める方は本論文を読んだほうがいいです。

概要、背景

論文の内容は、タイトルそのままですが、データセンター向けのstatelessなLBを実装したという内容です。このLBの名前がBeamerです。 論文中では、TCPおよびMPTCP(multipath TCP)で実装したことが述べられています。

まずは、LBからサーバへのパケット振り分けについて見ていきましょう。

f:id:cipepser:20180513130438p:plain
(本論文Figure 1より引用)

インターネットや外部からBorder routerにやってきたパケットに対して、Border routeはMUXのVIP向けにパケットを投げます。 MUXがLBだと思ってもらうとわかりやすいと思います。 DIP(direct IP)は、サーバの実IPを指しており、MUXの役割は、VIPに着信したパケットをサーバに振り分ける(Load-Balanceする)ことです。 従来のLBは、どのDIPに対して振り分けを行うかを、以下のような計算で決定します。

hash(srcIP, dstIP, srcPort, dstPort, protocol) % N
N: DIPの数

論文中では、5つの引数をfive-tupleと呼んでおり、flow単位の振り分けとしています。TCPでは、sequence numberが前後して届くと再送要求されるので、余計な再送要求が起こらないようflow単位の振り分けがよく行われます。物理的に同じスイッチ(QoSなどの優先制御がなければ、Queueで処理されるので順番が変わらない)、ケーブルを通れば、パケットの追い越しは起こらず、dropしていないのに再送要求されるということもないです。

しかし、flow単位の振り分けでは、以下のような要望があったときに問題が発生します。

  • メンテナンスのため、サーバへの振り分けを止めたい
  • 新しくサーバ追加したい
  • サーバに障害が発生した

先程のhash(srcIP, dstIP, srcPort, dstPort, protocol) % Nから明らかなようにサーバ台数Nが変化すると振り分け先のサーバが変わってしまいます。サーバでTCP connectionのstateを持っているので、下記図のように途中でサーバBを追加した場合、青色の既存connectionの整合性が取れなくなってしまいます。

f:id:cipepser:20180513132238p:plain
(本論文Figure 3より引用)

一般的なLBでは、サーバ台数が増減してもTCP connectionを維持したいので、flow単位のconnectionをすべて保持しています。ただし、そのコストも馬鹿にならず、40%くらいスループット落ちると述べられています。また、一般的なLBはSYN flood攻撃にも弱い点も指摘されています。

Beamerでの解決方法

上記を解決するため、Beamerでは、Bucketと呼ばれる中間層を設け、stable hashingを実現します。 Bucketは、サーバ台数Nに対して十分大きなサイズBを持ち(論文中だとB=100N)、b = hash(5tuple)%Bなどで実サーバとmappingします。

※ 論文中では、mapping方法に依存しない手法であり、rendezvous hashingやMaglevでも応用できると書かれています。だからこそハードウェアにも応用できるそうです。なお、本論文では貪欲法で、muxにアサインされる隣接バケットのサイズを最大にするようmappingしており、TCAMが節約できると主張しています。実際、以下のようにmappingをまとめることができるようです。

f:id:cipepser:20180513135246p:plain
(本論文Figure 5より引用)

このようにmappinされたBucketは、全MUXで共有されます。この方法では、サーバ台数が増減してもBが変わらず、実サーバとのmappingを調整するだけで対応できます。

f:id:cipepser:20180513151329p:plain
(本論文Figure 4より引用)

Data planeとControl plane

MUXは、実際のパケットを処理するため、Date planeとして働きます。 注意事項としては、カプセル化で16Bのオーバーヘッドがあることでしょうか。カプセル化自体は、TRILLやVXLAN、VPNなどネットワークまわりでは広く顔を出すのでおかしなことではありませんが、LBの振り分けとなるサーバまでの経路上でMTUが制御される場合などは注意が必要なためオーバーヘッドがどの程度あるのか知っておくことは大切です。

また、Beamerでは、Bucketのmappingが変わることを適切に管理してあげる必要があります。 この役割は、ContollerがControl planeで実現しており、Beamerは、Apache ZooKeeperを使っているそうです。

f:id:cipepser:20180513140228p:plain
(発表資料P.35より引用)

図のようにBucketが更新(v2)された場合、ZooKeeper経由で各MUXに通知され、各MUXが最新のBucketをダウンロードして、一貫性を保ちます。論文中では、2-phase commitで実現していると書かれていますが、このあたりはあまり詳しくないので詳細は本論文を読んでください。

Daisy chaining

Beamerでは、既存connectionを適切に扱うためDaisy chainingを使っています。 Bucketの再構成には、以下の課題の課題があります。

  • 既存connectionが壊れる
  • 一貫性が失われる(他が使ってるmappingをつかってしまう)

例えば、下記図の青いconnectionのように、もともとMUX2からサーバAにmappingされていた場合を考えます。

f:id:cipepser:20180513135553p:plain
(本論文Figure 6より引用)

Bucketの再構成によってこのconnectionがサーバBにmappingされた場合、 すでにestablishedな青いconnectionは、サーバAに振り分けられる必要があります。 Beamerでは、PDIP(previous DIP)という一つ前にmappingされた実サーバを覚えておき、一定時間は前のサーバに転送することで既存が壊れることを防ぎます。

ベンチマーク

まず1コアでのベンチマークです。ここでは、性能をpps(packet per second)を、パケットサイズが変化させて比較しています。

f:id:cipepser:20180513143745p:plain
(本論文Figure 13より引用)

StatefulなLBに対して、short packetである64Bでも2倍程度の性能が出ています。 また、コアを2つにすればline rateと同レベルの性能になっています。

論文中で最終的な性能は、以下の図で記載されています。

f:id:cipepser:20180513145002p:plain
(本論文Figure 14より引用)

128B packetに対して、8コア1サーバあたり23-33Mpps(bps単位で20-30Gbps)を処理できる結果です。 これは現状最速であるGoogleのMaglevの2倍の性能だそうです。

最後に

というわけで、Beamerの論文を読んだまとめでした。サーバ台数の増減があった場合、当然振り直しが起こるものの仕方ないと思っていたので、解決できるのかと驚きました。ベンチマークに用いた実装もGithubで公開されてます。
またGoogleのMaglevを知らなかったので関連研究を知る意味でも勉強になりました。Maglevは本論文の2年前に同じくnsdi'16で発表されたようなので、この辺も読まないとですね。Maglevの2倍というのは、この論文のFigure 10あたりっぽいです。

References

【Golang】DFS(深さ優先探索)による無向グラフのcycle detectを実装する

前回のDisjoint-set algorithmに引き続き、Cycle in Undirected Graph Graph AlgorithmのDFSによるcycle detect実装してみます。

前回は、自作のgraphパッケージを使いましたが、グラフの持ち方(データ構造)も検討しながらまとめたいと思います。

DFSによるcycle detectのアルゴリズム

まずDFSによるcycle detectを行うアルゴリズムの概要についてです。 DFSは、Depth-First Searchの略で、その名の通り深さ優先探索によってcycle detectを行います。 アルゴリズムは以下になります。

  1. 入力となる始点(頂点)sに対して、現在訪れている頂点csとする
  2. 頂点cが訪問済みか確認する(訪問済みならcycleありを返して終了。未訪問なら後続のステップへ)
  3. 頂点cを訪問済みにする
  4. 頂点cに接続する頂点を順に訪れる
    以下、2.から繰り返し

※cはcurrentの意で命名

すべての頂点の探索が終了すればcycleなしとして探索終了です。

例:cycleあり

以下の例でイメージを掴んでみましょう。

f:id:cipepser:20180415104034p:plain

まず始点sを頂点0とします。各頂点からの接続されている頂点への移動は、一つ前の頂点以外である必要があります。ここではわかりやすいように、一つ前の頂点以外で最も値が小さい頂点に移動するとしましょう。 移動を表にまとめると以下のとおりです。

頂点c 訪問済みの頂点
0 0
1 0,1
3 0,1,3
0 0,1,3

頂点3から頂点0に移動した時点でステップ2.の確認で頂点0(太字)が訪問済みであるため、cycleあり となります

例:cycleなし

先程の例から辺1-3を削除したものを考えてみます。

f:id:cipepser:20180415104040p:plain

先程と同様に始点sを頂点0とし、移動を表にまとめると以下のとおりです。

頂点c 訪問済みの頂点
0 0
1 0,1
2 0,1,2
3 0,1,2,3

すべての頂点を探索しても訪問済みの頂点がなかったため、cycleなし となります

設計

データ構造をどうするか

グラフのデータ構造といえば、隣接リストと隣接行列ですが、上記の例で考えたように次に訪れる頂点さえわかればよいので隣接リストを採用します。 上記の例では以下の表のようにグラフを保持します。

例:cycleあり

f:id:cipepser:20180415104034p:plain

頂点 隣接する頂点
0 1,2,3
1 0,3
2 0
3 0,1

例:cycleなし

f:id:cipepser:20180415104040p:plain

頂点 隣接する頂点
0 1,2,3
1 0
2 0
3 0

sliceかmapか

Goには、リストを扱うパッケージcontainer/listがありますが、Golangのcontainer/listでスタックとキューによるとsliceのほうが速いようです(自分でベンチマークは取っていないですが)。 sliceとmapのどちらで隣接リストを持つか決めるために、Golangのmapとsliceはどちらが速いのか - 逆さまにしたベンチマークを測定した結果、要素の探索を行わないのであれば、sliceが有利でした。 また、グラフ探索アルゴリズムとその応用にも以下のように書かれていますが、隣接行列ではなく、隣接リストを採用する場合、対象とするグラフのEdgeが少ないことを期待します。

疎グラフに対して、高速・省メモリ

Golangのmapとsliceはどちらが速いのか - 逆さまにしたベンチマークでは、要素数による違いを実感することはできませんでしたが、GoのパフォーマンスTipsメモに以下のように書かれており、上述の通り、グラフのEdge数(=要素数)は、少ないことを期待し、sliceを採用することにします。

100要素超えくらいからmapのアクセス速度一定の恩恵が発揮される。

頂点の数は予め与えられることとして、以下のようにGraph型を定義します。

// Graph is a graph with n vertices and edges.
type Graph struct {
    n     int
    edges [][]int
}

コンストラクタは以下。

// NewGraph creates a new graph with n vertices.
func NewGraph(n int) *Graph {
    g := &Graph{
        n:     n,
        edges: make([][]int, n),
    }
    return g
}

辺の追加

GraphAddEdgeを生やします。

// AddEdge adds a edge connects vertex u to v and v to u.
func (g *Graph) AddEdge(u, v int) {
    g.edges[v] = append(g.edges[v], u)
    g.edges[u] = append(g.edges[u], v)
}

今回は省略しますが、できれば以下をエラーチェックしたほうがよいでしょう。

  • uvが同一頂点でないこと
  • 初期化の頂点に含まれていないこと

DFSによるcycle detectの実装

DFSの実装には、スタックを用いた実装と再帰を用いた実装がありますが、再帰のほうがコードがシンプルになることが多いので、再帰で実装することにします。 アルゴリズム自体は冒頭に書いた通りですが、実装のポイントを以下です。

  • 訪問済みの頂点をvisitedとし、mapで持つ

Golangのmapとsliceはどちらが速いのか - 逆さまにしたベンチマークを取った通り、探索まで含めるとsliceだと遅くなってしまいます。今回は、訪れた頂点が 既に訪問済みか を確認したいのでmapにします。set型がないGoでは、mapを用いてset型の代わりのデータ構造を実装することがありますが、この時、strct{}がGo上ではサイズ0となることからmap[int]strct{}として実装するのがよいです。

  • 一つ前の頂点には戻らない

→ 直前にいた頂点に戻るようなDFSの実装にしてしまうと、visitedtrueを返すので、2頂点目を訪れた時点で(falseを返すべきなのに)trueを返して終了です。直前の頂点をp(parentを意識した命名)として実装します。

上記2点を踏まえた実装は以下です。

func dfs(p, c int, edges [][]int, visited map[int]struct{}) bool {
    _, ok := visited[c]
    if ok {
        return true
    }
    visited[c] = struct{}{}

    for _, v := range edges[c] {
        if v == p {
            continue
        }
        return dfs(c, v, edges, visited)
    }
    return false
}

dfsGraph型の変数からメソッドとして呼び出せるように以下のように実装します。

func (g *Graph) ExistsCycle() bool {
    return dfs(-1, 0, g.edges, map[int]struct{}{})
}

ここで、pは直前に訪れた頂点がないためdfs()中のv == pfalseになるようにp = -1としています。さらに探索を開始する頂点(冒頭のアルゴリズムにあるs)は、どこでもいいので、s = 0から始めています。

テスト

上記の例で正しく動作することを試してみます。

例:cycleあり

f:id:cipepser:20180415104034p:plain

頂点 隣接する頂点
0 1,2,3
1 0,3
2 0
3 0,1
g := undirected.NewGraph(4)
g.AddEdge(0, 1)
g.AddEdge(0, 2)
g.AddEdge(0, 3)
g.AddEdge(1, 3)

fmt.Println(g.ExistsCycle()) // true

例:cycleなし

f:id:cipepser:20180415104040p:plain

頂点 隣接する頂点
0 1,2,3
1 0
2 0
3 0
g := undirected.NewGraph(4)
g.AddEdge(0, 1)
g.AddEdge(0, 2)
g.AddEdge(0, 3)

fmt.Println(g.ExistsCycle()) // false

References

Golangのmapとsliceはどちらが速いのか

GoのパフォーマンスTipsメモにインデックスアクセスについて、以下のように述べられている。

mapのインデックスアクセスはsliceの数十倍遅い。 100件以下の場合バイナリサーチでsliceから目的の値を探すほうが早い。 100要素超えくらいからmapのアクセス速度一定の恩恵が発揮される。

実際にベンチマークを取ってみる。

測定したいこと

  1. 素数の増加に従って、sliceとmapでインデックスアクセス速度がどのように変わるか
  2. sliceから特定の要素を探すとき、mapと性能分岐点になる要素数はいくつか

条件

  • sliceは[]int型とする
  • sliceの中身はsort済みとする(indexをそのまま要素の値とする)
  • mapはmap[int]int型とする

環境

macOS High Sierra version 10.13.4(17E202)
MacBook Pro (Retina, 13-inch, Early 2015)
2.7 GHz Intel Core i5
16 GB 1867 MHz DDR3
Intel Iris Graphics 6100 1536 MB
❯ go version
go version go1.10.1 darwin/amd64

固定indexへアクセス

素数nに対して、中間のn/2のインデックスにアクセスする時間を測定する。

実装

func benchmarkOfIndexAccessToMap(n int, b *testing.B) {
    m := make(map[int]int, n)
    idx := n / 2

    for i := 0; i < b.N; i++ {
        _ = m[idx]
    }
}
func BenchmarkOfIndexAccessToMap10(b *testing.B)   { benchmarkOfIndexAccessToMap(10, b) }
func BenchmarkOfIndexAccessToMap30(b *testing.B)   { benchmarkOfIndexAccessToMap(30, b) }
func BenchmarkOfIndexAccessToMap70(b *testing.B)   { benchmarkOfIndexAccessToMap(70, b) }
func BenchmarkOfIndexAccessToMap100(b *testing.B)  { benchmarkOfIndexAccessToMap(100, b) }
func BenchmarkOfIndexAccessToMap300(b *testing.B)  { benchmarkOfIndexAccessToMap(300, b) }
func BenchmarkOfIndexAccessToMap700(b *testing.B)  { benchmarkOfIndexAccessToMap(700, b) }
func BenchmarkOfIndexAccessToMap1000(b *testing.B) { benchmarkOfIndexAccessToMap(1000, b) }
func BenchmarkOfIndexAccessToMap3000(b *testing.B) { benchmarkOfIndexAccessToMap(3000, b) }

func benchmarkOfIndexAccessToSlice(n int, b *testing.B) {
    s := make([]int, n)
    idx := n / 2

    for i := 0; i < b.N; i++ {
        _ = s[idx]
    }
}
func BenchmarkOfIndexAccessToSlice10(b *testing.B)   { benchmarkOfIndexAccessToSlice(10, b) }
func BenchmarkOfIndexAccessToSlice30(b *testing.B)   { benchmarkOfIndexAccessToSlice(30, b) }
func BenchmarkOfIndexAccessToSlice70(b *testing.B)   { benchmarkOfIndexAccessToSlice(70, b) }
func BenchmarkOfIndexAccessToSlice100(b *testing.B)  { benchmarkOfIndexAccessToSlice(100, b) }
func BenchmarkOfIndexAccessToSlice300(b *testing.B)  { benchmarkOfIndexAccessToSlice(300, b) }
func BenchmarkOfIndexAccessToSlice700(b *testing.B)  { benchmarkOfIndexAccessToSlice(700, b) }
func BenchmarkOfIndexAccessToSlice1000(b *testing.B) { benchmarkOfIndexAccessToSlice(1000, b) }
func BenchmarkOfIndexAccessToSlice3000(b *testing.B) { benchmarkOfIndexAccessToSlice(3000, b) }

結果

BenchmarkOfIndexAccessToMap10-4           1000000000          2.81 ns/op
BenchmarkOfIndexAccessToMap30-4            1000000000          2.81 ns/op
BenchmarkOfIndexAccessToMap70-4            1000000000          2.81 ns/op
BenchmarkOfIndexAccessToMap100-4           1000000000          2.83 ns/op
BenchmarkOfIndexAccessToMap300-4           1000000000          2.81 ns/op
BenchmarkOfIndexAccessToMap700-4           1000000000          2.81 ns/op
BenchmarkOfIndexAccessToMap1000-4          1000000000          2.81 ns/op
BenchmarkOfIndexAccessToMap3000-4          1000000000          2.81 ns/op

BenchmarkOfIndexAccessToSlice10-4          2000000000          0.33 ns/op
BenchmarkOfIndexAccessToSlice30-4          2000000000          0.33 ns/op
BenchmarkOfIndexAccessToSlice70-4          2000000000          0.33 ns/op
BenchmarkOfIndexAccessToSlice100-4         2000000000          0.33 ns/op
BenchmarkOfIndexAccessToSlice300-4         2000000000          0.33 ns/op
BenchmarkOfIndexAccessToSlice700-4         2000000000          0.33 ns/op
BenchmarkOfIndexAccessToSlice1000-4        2000000000          0.33 ns/op
BenchmarkOfIndexAccessToSlice3000-4        2000000000          0.33 ns/op

表とグラフにまとめると以下の通り。

素数 map slice
10 2.81 0.33
30 2.81 0.33
70 2.81 0.33
100 2.83 0.33
300 2.81 0.33
700 2.81 0.33
1000 2.81 0.33
3000 2.81 0.33

f:id:cipepser:20180505152007p:plain

単純なインデックスアクセスであれば、sliceとmapどちらも固定の時間しか掛からない(sliceでも探索するわけではないので当然といえば当然)。アクセス速度はsliceのほうが約8.5倍速い。 アクセスしたい要素のインデックスが予めわかっているようなケースや、各要素をloopで順番に処理していくような操作では、sliceを使ったほうがいいと考えられる。

異なるindexへアクセス

アクセスしたい要素のインデックスがわからないケースも想定してベンチマークを取ってみる。乱数でインデックスを決定することも考えたが、nに対して、b.Nが十分大きいことが前測定でわかったので、i%nがアクセスしたい要素とする。sliceの場合は、要素をBinary Searchで探索する必要があるので、実装し、同時に測定した。Binary Search単体でどれくらい時間を要するのかも確認したかったので、sliceへのインデックスアクセスをしない測定も同時に行っている。

実装

func benchmarkOfMap(n int, b *testing.B) {
    m := make(map[int]int, n)

    for i := 0; i < b.N; i++ {
        _ = m[i%n]
    }
}
func BenchmarkOfMap10(b *testing.B)   { benchmarkOfMap(10, b) }
func BenchmarkOfMap30(b *testing.B)   { benchmarkOfMap(30, b) }
func BenchmarkOfMap70(b *testing.B)   { benchmarkOfMap(70, b) }
func BenchmarkOfMap100(b *testing.B)  { benchmarkOfMap(100, b) }
func BenchmarkOfMap300(b *testing.B)  { benchmarkOfMap(300, b) }
func BenchmarkOfMap700(b *testing.B)  { benchmarkOfMap(700, b) }
func BenchmarkOfMap1000(b *testing.B) { benchmarkOfMap(1000, b) }
func BenchmarkOfMap3000(b *testing.B) { benchmarkOfMap(3000, b) }

func benchmarkOfSearchElementOfSlice(n int, b *testing.B) {
    s := make([]int, n)
    for i := range s {
        s[i] = i
    }

    for i := 0; i < b.N; i++ {
        _ = s[search(i%n, s)]
    }
}
func BenchmarkOfSearchElementOfSlice10(b *testing.B)   { benchmarkOfSearchElementOfSlice(10, b) }
func BenchmarkOfSearchElementOfSlice30(b *testing.B)   { benchmarkOfSearchElementOfSlice(30, b) }
func BenchmarkOfSearchElementOfSlice70(b *testing.B)   { benchmarkOfSearchElementOfSlice(70, b) }
func BenchmarkOfSearchElementOfSlice100(b *testing.B)  { benchmarkOfSearchElementOfSlice(100, b) }
func BenchmarkOfSearchElementOfSlice300(b *testing.B)  { benchmarkOfSearchElementOfSlice(300, b) }
func BenchmarkOfSearchElementOfSlice700(b *testing.B)  { benchmarkOfSearchElementOfSlice(700, b) }
func BenchmarkOfSearchElementOfSlice1000(b *testing.B) { benchmarkOfSearchElementOfSlice(1000, b) }
func BenchmarkOfSearchElementOfSlice3000(b *testing.B) { benchmarkOfSearchElementOfSlice(3000, b) }

func benchmarkOfSearch(n int, b *testing.B) {
    s := make([]int, n)
    for i := range s {
        s[i] = i
    }

    for i := 0; i < b.N; i++ {
        _ = search(i%n, s)
    }
}
func BenchmarkOfSearch10(b *testing.B)   { benchmarkOfSearch(10, b) }
func BenchmarkOfSearch30(b *testing.B)   { benchmarkOfSearch(30, b) }
func BenchmarkOfSearch70(b *testing.B)   { benchmarkOfSearch(70, b) }
func BenchmarkOfSearch100(b *testing.B)  { benchmarkOfSearch(100, b) }
func BenchmarkOfSearch300(b *testing.B)  { benchmarkOfSearch(300, b) }
func BenchmarkOfSearch700(b *testing.B)  { benchmarkOfSearch(700, b) }
func BenchmarkOfSearch1000(b *testing.B) { benchmarkOfSearch(1000, b) }
func BenchmarkOfSearch3000(b *testing.B) { benchmarkOfSearch(3000, b) }

Binary Searchは以下で実装。

package slicevsmap

// search returns an index of element `e` in slice `s`.
// s must be sorted slice to execute binary search.
func search(e int, s []int) int {
    idx := binarySearch(e, 0, len(s)-1, s)
    if idx < 0 {
        panic("not found")
    }
    return idx
}

func binarySearch(e, l, r int, s []int) int {
    i := (l + r) / 2

    if i == l {
        switch {
        case s[l] == e:
            return l
        case s[r] == e:
            return r
        default:
            return -1
        }
    }

    switch {
    case s[i] < e:
        return binarySearch(e, i+1, r, s)
    case s[i] > e:
        return binarySearch(e, l, i-1, s)
    case s[i] == i:
        return i
    }

    return -1
}

結果

BenchmarkOfMap10-4                        100000000          14.9 ns/op
BenchmarkOfMap30-4                         100000000          14.8 ns/op
BenchmarkOfMap70-4                         100000000          14.7 ns/op
BenchmarkOfMap100-4                        100000000          14.8 ns/op
BenchmarkOfMap300-4                        100000000          14.6 ns/op
BenchmarkOfMap700-4                        100000000          14.7 ns/op
BenchmarkOfMap1000-4                       100000000          14.6 ns/op
BenchmarkOfMap3000-4                       100000000          14.6 ns/op

BenchmarkOfSearchElementOfSlice10-4        100000000          23.8 ns/op
BenchmarkOfSearchElementOfSlice30-4        50000000           29.2 ns/op
BenchmarkOfSearchElementOfSlice70-4        50000000           33.4 ns/op
BenchmarkOfSearchElementOfSlice100-4       50000000           34.9 ns/op
BenchmarkOfSearchElementOfSlice300-4       30000000           48.7 ns/op
BenchmarkOfSearchElementOfSlice700-4       20000000           70.6 ns/op
BenchmarkOfSearchElementOfSlice1000-4      20000000           77.6 ns/op
BenchmarkOfSearchElementOfSlice3000-4      20000000           89.5 ns/op

BenchmarkOfSearch10-4                      100000000          23.1 ns/op
BenchmarkOfSearch30-4                      50000000           29.0 ns/op
BenchmarkOfSearch70-4                      50000000           32.9 ns/op
BenchmarkOfSearch100-4                     50000000           34.9 ns/op
BenchmarkOfSearch300-4                     30000000           48.2 ns/op
BenchmarkOfSearch700-4                     20000000           69.7 ns/op
BenchmarkOfSearch1000-4                    20000000           77.1 ns/op
BenchmarkOfSearch3000-4                    20000000           88.8 ns/op

こちらも表とグラフにまとめると以下の通り。

素数 slice + search searchのみ map
10 23.8 23.1 14.9
30 29.2 29 14.8
70 33.4 32.9 14.7
100 34.9 34.9 14.8
300 48.7 48.2 14.6
700 70.6 69.7 14.7
1000 77.6 77.1 14.6
3000 89.5 88.8 14.6

f:id:cipepser:20180505152011p:plain

mapは要素数に依存しない定数時間になっている。sliceのほうは、Binary SearchがO(logN)で、探索に大部分の時間を費やしてしまっていることがわかる。sort済みのsliceですらこの結果になってしまうので、Existsメソッドを生やしたいような場合では、mapを使ったほうがよいと思われる。

結論

  1. 素数の増加に従って、sliceとmapでインデックスアクセス速度がどのように変わるか
    → 単純なインデックスアクセスであれば、sliceのほうが8.5倍程度速い

  2. sliceから特定の要素を探すとき、mapと性能分岐点になる要素数はいくつか
    → searchも含めて行う場合は、mapのほうが速い

同内容をGithubにも上げている。

References

ビットコインとブロックチェーン:暗号通貨を支える技術を読んだ

Mastering Bitcoinの邦訳であるビットコインとブロックチェーン:暗号通貨を支える技術/アンドレアス・M・アントノプロス (著), 今井 崇也 (翻訳), 鳩貝 淳一郎 (翻訳)を読みました。

Blockchainのバイブルと名高い本書ですが、その評判に違わない内容でした。 2009年にナカモトサトシが論文を発表して以来、数多くの記事がネット上に存在し、十分な情報がある現在ですが、どうしても今一歩疑問が解決できない事柄が多々ありました。個人的には以下の2つが、なんとなくはわかるけど、どうもしっくりこない事柄でした。

  • UTXO
  • マークル木

具体的にはそれぞれ、以下のような疑問がずっとありましたが、本書を読んで解決することができました。

UTXOの疑問点

UTXOがアカウントベースではないというのは、理解できるものの以下がよくわかりませんでした。

  • 特定のアドレスの残高はどうやってわかるのか

この疑問は、以下の記載で氷解しました。

ウォレットは、ブロックチェーンをスキャンしてユーザに属しているすべてのUTXOを掻き集め、残高を計算しているのです。

(P.120 第5章 トランザクション / トランザクションアウトプットより引用)

Blockchainの機能として残高がわかるわけではなく、ウォレットの機能なのですね。 その他にも以下のような疑問がありました。

  • コインをロックするとは、どういうことなのか
  • 任意の精度でアウトプットがロックされてしまうと、ゴミのようなコインばかりになってしまうのではないか

これらの疑問は以下の文章で理解できました。

ビットコインの最小単位であるsatoshi単位で表されたビットコイン金額 ・アウトプットを使用するにあたって満たさなければいけない「解除条件(encumbrance)」として知られているlocking script

(P.122 第5章 トランザクション / トランザクションアウトプットより引用)

コインのロックとは、locking scriptのことであり、これを解除する条件を満たせるのが、そのアドレスの秘密鍵を持っている人です。具体的には、秘密鍵で作成したunlock scriptを作成すること、というのもscript言語の節で理解できました。 また、任意の精度ではなく、satoshi単位で量子化されているのも、考えてみれば当たり前ですが、本書を読まなければずっとモヤモヤしたままでした。

マークル木の疑問点

マークル木では、ブロックに含まれるトランザクションをマークルルートで代表するのは理解できるものの以下の疑問がありました。

  • client-sideで検証する際にマークルルートだけでは不足するのではないのか

再び本書から引用すると、以下の通りでした。

特定のトランザクションがブロックに格納されていることを証明するために、ビットコインノードはlog2(N)個の32バイトのハッシュ値を作るだけでよく、(中略) 千個以上のトランザクションから、1個のトランザクションを特定するためのマークルパスを10〜12個のハッシュ値(320〜384バイト)で効率的に作り出すことができるのです。

(P.178 第7章 ブロックチェーン / マークルツリーより引用)

疑問は正しく、マークルルートだけでは、特定のトランザクションが格納されている検証はできないものの、すべてのトランザクションを持つ必要はなく、log2(N)で検証に必要なトランザクション数を減らせるというのが肝のようでした。

網羅性が高い

本書はBlockchain、とりわけBitcoinについて非常に網羅的です。目次を引用しますが、第3章〜第8章のBlockchainの基盤的な仕組みがとても勉強になりました。逆に第9章は少し古いので、読み飛ばすのもありだと思います。

第1章 イントロダクション 第2章 ビットコインの仕組み 第3章 ビットコインクライアント 第4章 キー、アドレス、ウォレット 第5章 トランザクション(取引) 第6章 ビットコイン・ネットワーク 第7章 ブロックチェーン 第8章 マイニングとコンセンサス(合意形成) 第9章 代替的なチェーン、通貨、アプリケーション 第10章 ビットコインの安全性

また、インターネット上の記事を見ていると「ビットコインアドレスは1から始まる」という説明をよく見ると思いますが、 本書では、Version prefixがどのように付けられるから、それをbase58エンコーディングをした結果、先頭が1になるというような説明が、P2SHやWIF形式といった種類ごとにまとめられています。本書中でも「xから始めるアドレス」という表現は何度も登場し、ネット上でこれだけみんなが言っていたのも本書がバイブルであることを裏付けているようでした。

自分で手を動かせる

本書にはコードが多数含まれています。 コマンドライン上で動かすbitcoin corelibbitcoin/bitcoin explorerや EthereumのVitalikが作成したpythonライブラリpybitcointoolsなどを使って、上記のxから始めるアドレスというようなアドレスを実際に生成してみたり、bitcoinコアのコマンドからblockやtx、utxoの情報を取得したりします。

コードは多いですが、自分で実装を考える部分はほぼなく、写経する形になると思います。 むしろ大変なのは、150GB(2018/04/13時点)を超えるフルノードの同期と、バージョンが違うことによる./configuremakeのエラー解消だと思います。実際、読書時点の2018/04/13時点で安定バージョンだったv0.16.0では、本書の内容から変更されている部分もありました。第3章から第6章を自分でやってみた際の結果と変更に応じて対処した点は、こちらにログを残しているのでご参考にどうぞ。

その他収穫だったところ

今までわからなかったscript言語もスタックマシンであるという説明があり、実際にscriptSigとscriptPubKeyが組み合わされることでUTXOのロックを解除する流れや簡単な例が記載されており、マルチシグのような条件付きスクリプトも読めるようになったのは大きな収穫です。 その他にも階層的決定性ウォレットやトランザクションプール、extra nonceなど興味深いトピックが多数含まれており、とても勉強になりました。

こういう人におすすめ

上述の通り、コマンドライン上でbxを実行したり、C++pythonのコードもありますが、そこまで難しくはないです。 とはいえ、どの言語も触ったことがないという方だと少し難しい部分もあるかと思うので、技術的な観点からBlockchainを理解したいエンジニアの方には自信をもってオススメできます。

ビットコインとブロックチェーン:暗号通貨を支える技術

ビットコインとブロックチェーン:暗号通貨を支える技術

References

Golangで言語処理100本ノック2015 目次

言語処理100本ノック 2015を完走したので、目次として各記事へのリンクをまとめました。

Golangで言語処理100本ノック2015 第1章: 準備運動
Golangで言語処理100本ノック2015 第2章: UNIXコマンドの基礎
Golangで言語処理100本ノック2015 第3章: 正規表現
Golangで言語処理100本ノック2015 第4章: 形態素解析
Golangで言語処理100本ノック2015 第5章: 係り受け解析
Golangで言語処理100本ノック2015 第6章: 英語テキストの処理
Golangで言語処理100本ノック2015 第7章: データベース
Golangで言語処理100本ノック2015 第8章: 機械学習
Golangで言語処理100本ノック2015 第9章: ベクトル空間法 (I)
Golangで言語処理100本ノック2015 第10章: ベクトル空間法 (II)

Golangで言語処理100本ノック2015 第10章: ベクトル空間法 (II)

言語処理100本ノック 2015の第10章: ベクトル空間法 (II)の10問です。

第10章では,前章に引き続き単語ベクトルの学習に取り組む.

90. word2vecによる学習

81で作成したコーパスに対してword2vecを適用し,単語ベクトルを学習せよ.さらに,学習した単語ベクトルの形式を変換し,86-89のプログラムを動かせ.

まずは、word2vecで単語ベクトルを学習します。問題文のリンクはシェルスクリプトなのとSVNがリンク切れしているようなので、Githubのコピー版を使いました。 第9章に合わせて引数を指定しています(default値と同じものもありますが、合わせてる意図を込めて明示的に記載しています)。

❯ ./word2vec -train <PATH_TO>/q81.out.txt -output ./trained_model.txt -size 300 -window 5 -negative 5

gist3119b38c63d0bd410eda14984c5d84f7

❯ go run q90.go
------------------------------
86. 単語ベクトルの表示
United_States
[1.823542 0.998212 0.151048 -0.756645 1.062619 1.191252 -1.759574 0.093121 -0.225518 -0.293923 -0.021835 -0.36047 0.672428 -0.316323 0.304076 0.622363 -0.327869 0.557787 0.303997 -0.940469 -0.303781 0.679504 -0.780764 0.235443 0.232059 0.787089 -0.503982 -0.413358 -0.577007 -1.864737 0.285715 0.063075 -0.653608 -0.666802 -0.401068 -0.225341 -0.076025 0.597728 -0.323169 1.686404 0.298269 0.329775 -1.483898 -0.060094 0.38326 -1.090787 -0.401468 0.584051 0.483002 0.289693 -1.364987 1.05808 1.084504 0.758496 -0.700064 0.921075 -0.389838 0.557126 -0.623444 0.545065 -1.866777 -1.540459 1.311491 1.252319 0.584708 -0.154731 1.178817 0.145006 -1.706097 -1.087952 -0.094799 -0.308998 -0.412141 0.747653 2.131562 0.277976 0.198845 1.520575 -0.453697 -0.340365 0.949026 -0.940041 0.362253 0.049247 0.16048 -0.014336 -1.221997 -0.341103 -1.099968 -0.17678 -1.028104 1.222829 -0.116968 -0.874536 -1.352752 -0.337586 0.153726 0.579554 1.410893 0.468515 -1.762948 0.614649 -0.508029 1.843732 2.288618 0.165021 -0.006009 -1.207882 -1.004512 0.660928 0.515029 0.591341 0.323199 1.665782 -1.4572 0.073172 -0.635124 -1.256417 1.200009 0.773504 0.258664 0.897132 -0.431907 0.014102 -0.112152 -0.070823 0.695606 -1.465958 -0.108996 -0.74142 0.804069 0.519639 0.821394 -1.453141 0.468004 1.578241 -0.163182 0.910499 0.310518 0.19384 -1.736236 -0.587345 0.305146 -0.955576 -1.035768 0.599607 -0.326483 -0.009862 -1.529698 -0.566457 0.233704 0.179851 -0.4688 -0.276734 0.579735 0.494316 -1.086717 -0.186733 -0.430683 0.061927 0.117999 -0.238442 1.233732 -0.431326 0.158956 1.685206 0.689615 1.619143 -0.512952 -1.22104 0.772325 -0.222188 -1.231234 0.127665 0.533659 2.21996 -0.220213 1.019247 -0.677278 -0.2214 -0.357192 1.181603 -1.539749 0.452797 1.653844 0.00879 0.271083 0.091245 -0.554843 -0.198385 -0.695354 -0.549476 -0.176233 0.779347 0.180929 0.028113 -0.33744 -1.248068 -1.201352 1.12126 0.239276 -0.086537 -0.847377 1.124556 -0.540444 1.216385 0.264993 -1.182609 -0.306502 0.783623 0.056023 -0.558314 0.707812 -0.169515 0.096631 0.444101 1.047364 -0.872509 -0.020277 1.113677 -1.054098 -2.080168 -2.928403 0.592833 -0.539894 0.34649 -2.267012 -0.184786 -0.975977 -0.045709 -0.022163 -0.288505 1.045948 -0.659885 -0.128221 -1.098224 -1.027867 0.375439 -0.435416 -1.238411 2.494976 0.797522 -0.704402 0.91279 -1.0877 -0.417203 -1.122003 0.06181 -1.862646 0.039802 0.147812 0.598384 0.06901 0.504204 0.778565 1.255542 -0.272787 1.952137 0.68609 1.174417 -0.386691 -0.239997 -0.05854 0.032976 -1.42854 0.638762 0.967045 0.75671 -0.599432 0.962889 -1.163935 0.57435 -1.434526 -0.838759 -0.423522 1.184661 0.49942 0.541755 -0.663361 -0.103821 0.315 0.847865 0.156598 1.353468 -0.383525 0.892902 0.247807 0.091043 0.789759 0.365569 -0.163217 1.9303 -1.300313 -1.616886 -1.752266 0.6924 -0.864655 -2.085828 1.231503 -0.501419]
------------------------------
87. 単語の類似度
United_Stetes v.s. U.S.
0.7745992551063425
------------------------------
88. 類似度の高い単語10件
1   England : 1
2   Wales : 0.6799484101924722
3   Scotland : 0.6601875749325679
4   Ireland : 0.576445075380364
5   Britain : 0.5294550459380852
6   Hampshire : 0.5080241507481739
7   Somerset : 0.5048523334327183
8   Lancashire : 0.4975930638881287
9   London : 0.49608850575325425
10   Glasgow : 0.490454852366284
------------------------------
89. 加法構成性によるアナロジー
1   Spain : 0.6948565586316053
2   Athens : 0.681273120661114
3   Greece : 0.564727893639371
4   Denmark : 0.5412544877031749
5   Romania : 0.5190412855968768
6   Armenia : 0.5134651735824168
7   Egypt : 0.5112680989598707
8   Argentina : 0.5040413172446792
9   Portugal : 0.5017621437939799
10   Austria : 0.4927839578682253

8章で苦労したものと違って学習にかかる時間も短く、結果も直感どおりでGoogleすごいなと実感させられますね。。。

91. アナロジーデータの準備

単語アナロジーの評価データをダウンロードせよ.このデータ中で": "で始まる行はセクション名を表す.例えば,": capital-common-countries"という行は,"capital-common-countries"というセクションの開始を表している.ダウンロードした評価データの中で,"family"というセクションに含まれる評価事例を抜き出してファイルに保存せよ.

gist82757c3b8676b53ccfd7cdcde06b2349

❯ go run q91.go
❯ head -10 ../data/q91.out.txt
: family
boy girl brother sister
boy girl brothers sisters
boy girl dad mom
boy girl father mother
boy girl grandfather grandmother
boy girl grandpa grandma
boy girl grandson granddaughter
boy girl groom bride
boy girl he she

こちらも評価データがリンク切れしているので、こちらを使いました。

92. アナロジーデータへの適用

91で作成した評価データの各事例に対して,vec(2列目の単語) - vec(1列目の単語) + vec(3列目の単語)を計算し,そのベクトルと類似度が最も高い単語と,その類似度を求めよ.求めた単語と類似度は,各事例の末尾に追記せよ.このプログラムを85で作成した単語ベクトル,90で作成した単語ベクトルに対して適用せよ.

前処理

Q85のモデルのフォーマットをQ90と同一にするため以下前処理を行います。

gist0bb71f60790e48b728636e259707691f

❯ go run q92pre.go
❯ head -2 ../data/q85_model.txt
23699 300
Tibet 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000

本題

gist33df6b590a9ea39ddb3735bb0926537a

❯ go run q92.go
// 題意に従い、modelを変えて二度実行しています。

❯ head -20 ../data/q92_model_q85.out.txt
: family
boy girl brother sister brother 1.000000
boy girl brothers sisters Undifined -1.100000
boy girl dad mom Undifined NaN
boy girl father mother Undifined -1.100000
boy girl grandfather grandmother Undifined -1.100000
boy girl grandpa grandma Undifined NaN
boy girl grandson granddaughter Undifined -1.100000
boy girl groom bride Undifined NaN
boy girl he she he 1.000000
boy girl his her his 1.000000
boy girl husband wife Undifined -1.100000
boy girl king queen king 1.000000
boy girl man woman Undifined -1.100000
boy girl nephew niece Undifined -1.100000
boy girl policeman policewoman Undifined NaN
boy girl prince princess Undifined -1.100000
boy girl son daughter son 1.000000
boy girl sons daughters Undifined -1.100000
boy girl stepbrother stepsister Undifined NaN

❯ head -20 ../data/q92_model_q90.out.txt
: family
boy girl brother sister brother 0.877781
boy girl brothers sisters brothers 0.824237
boy girl dad mom girl 0.698522
boy girl father mother father 0.870984
boy girl grandfather grandmother grandfather 0.759021
boy girl grandpa grandma Undifined NaN
boy girl grandson granddaughter grandson 0.724518
boy girl groom bride girl 0.670416
boy girl he she he 0.881071
boy girl his her his 0.865413
boy girl husband wife husband 0.893910
boy girl king queen king 0.857420
boy girl man woman man 0.870114
boy girl nephew niece nephew 0.743345
boy girl policeman policewoman girl 0.700381
boy girl prince princess prince 0.755579
boy girl son daughter son 0.879387
boy girl sons daughters sons 0.880932
boy girl stepbrother stepsister Undifined NaN

Q85のほうはダメダメですね。Q90も正解率は高くなさそうです。

93. アナロジータスクの正解率の計算

92で作ったデータを用い,各モデルのアナロジータスクの正解率を求めよ.

gist68faf311e8fe37dacde2b1fd69682492

// Q85
❯ go run q93.go
0
// Q90
❯ go run q93.go
0.043478260869565216

Q85のmodelではひとつも正解できませんでした。Q90でも4%と精度はあまりよくないですね。 Q92で見たように零ベクトルが多くUndifinedになってしまいました。

94. WordSimilarity-353での類似度計算

The WordSimilarity-353 Test Collectionの評価データを入力とし,1列目と2列目の単語の類似度を計算し,各行の末尾に類似度の値を追加するプログラムを作成せよ.このプログラムを85で作成した単語ベクトル,90で作成した単語ベクトルに対して適用せよ.

gist79cb64278142bed6d7ca1b58c5529ec8

// Q85
❯ go run q93.go
❯ head -10 ../data/q94_model_q85.out.txt
Word 1,Word 2,Human (mean)
love,sex,6.77,NaN
tiger,cat,7.35,NaN
tiger,tiger,10.00,NaN
book,paper,7.46,NaN
computer,keyboard,7.62,NaN
computer,internet,7.58,NaN
plane,car,5.77,NaN
train,car,6.31,NaN
telephone,communication,7.50,NaN
// Q90
❯ go run q93.go
Word 1,Word 2,Human (mean)
love,sex,6.77,0.344764
tiger,cat,7.35,0.650308
tiger,tiger,10.00,1.000000
book,paper,7.46,0.457775
computer,keyboard,7.62,0.448387
computer,internet,7.58,0.518989
plane,car,5.77,0.397299
train,car,6.31,0.460842
telephone,communication,7.50,0.441498

人力で評価した関連する単語とこれまで学習してきたモデルの比較をしていきます。 Q85はすべてがNaNになっているわけではないのですが、大部分がNaNですね。 一方でQ90はなかなか良さそうです。集計は次の問題です。

95. WordSimilarity-353での評価

94で作ったデータを用い,各モデルが出力する類似度のランキングと,人間の類似度判定のランキングの間のスピアマン相関係数を計算せよ.

gist7d5274b15f7a20948013658fd297bbfa

// Q85
❯ go run q95.go
-0.010072800290837701

// Q90
❯ go run q95.go
0.5951617769609865

今回はQ85で同順位が多いので、スピアマンの順位相関係数 - Wikipediaにも載っている同順位の場合で実装しようと思いましたが、dgryski/go-onlinestatsを拝借しました。

96. 国名に関するベクトルの抽出

word2vecの学習結果から,国名に関するベクトルのみを抜き出せ.

gist448273c49432eb5c3e7b5fa0d0051fb5

❯ go run q96.go
// 出力はgobでバイナリフォーマットのため省略

Q81でも用いたList of countries of the world in alphabetical orderの国名を抽出しました。 前処理として複合語から成る国名は_で結合しています。

97. k-meansクラスタリング

96の単語ベクトルに対して,k-meansクラスタリングクラスタ数k=5として実行せよ.

gisteeeff6fc40045a328486829456ddb759

❯ go run q97.go
4 : Sierra_Leone
3 : Wake_Island
2 : Virgin_Islands
3 : El_Salvador
1 : Costa_Rica
3 : Marshall_Islands
2 : American_Samoa
3 : Northern_Mariana_Islands
1 : Saudi_Arabia
4 : Cape_Verde
3 : Wallis_and_Futuna
3 : Central_African_Republic
3 : San_Marino
4 : Isle_of_Man
5 : United_Kingdom
3 : Bosnia_and_Herzegovina
4 : Puerto_Rico
3 : Cayman_Islands
5 : New_Zealand
3 : West_Bank
3 : Faroe_Islands
1 : Solomon_Islands
3 : Norfolk_Island
3 : United_Arab_Emirates
3 : Saint_Lucia
1 : Sri_Lanka
3 : Trinidad_and_Tobago
3 : Western_Sahara
2 : Hong_Kong
2 : United_States
1 : Dominican_Republic
3 : Cook_Islands
3 : Serbia_and_Montenegro
3 : French_Polynesia
3 : Saint_Helena
3 : Gaza_Strip
3 : French_Guiana
3 : Equatorial_Guinea
1 : Papua_New_Guinea
3 : Christmas_Island
3 : British_Virgin_Islands
1 : Czech_Republic
1 : New_Caledonia
1 : South_Africa
3 : Burkina_Faso
3 : Antigua_and_Barbuda

Q96で学習モデルに含まれていない(零ベクトルになる)国名は弾いてしまっているので46カ国での結果になりました。 k-meansの実体はkMeansに実装し、各国が割り当てられたlabelが変化しなくなるまでループを回しています。

98. Ward法によるクラスタリング

96の単語ベクトルに対して,Ward法による階層型クラスタリングを実行せよ.さらに,クラスタリング結果をデンドログラムとして可視化せよ.

gistb57d94e6ad48f7909011a28f0c1a0c3c

結果です。

f:id:cipepser:20180407153927p:plain

本文で実装した内容でパッケージ化したので、以下に使い方を含めてまとめています。 【Golang】Ward法で階層的クラスタリングするパッケージを書いた - 逆さまにした

99. t-SNEによる可視化

96の単語ベクトルに対して,ベクトル空間をt-SNEで可視化せよ.

Q98と同様に可視化部分は自分で実装する必要があったのでgonum/plotで以下のように実装しました。

gist63aad7d67083a70dc8230315588ae407

本題はこちら。

gistab950a1bd807782eab10859a55633e56

結果です。

f:id:cipepser:20180408130612p:plain

t-SNEの計算は、tsne4goを使いました。 最初可視化した際には黒一色で表示していましたが、意味が理解できなかったので、Q97のk-meansで色分けしています。 そもそもt-SNEとk-meansの相性がいいのか知りませんが、気持ち分類できているかなというところでしょうか。

感想

以上で言語処理処理100本ノックの全100問完走です。 途中で半年くらい間開けてしまったりしたので結構長く掛かりましたが完走できてよかったです。 ただ、前章のQ85が微妙な結果だったので、Q85が実装できたら本章も再チャレンジしたいです。

もともとGoを触り始めて慣れるために始めたのですが、いろいろ実装できて自然言語処理の勉強に加えて、Goの勉強にもなりました。 特にGoで100本ノックやっている方をほかに見かけないので自力で頑張る必要があったのも結果的にはよかったのかと思います。 お付き合いありがとうございました。

コードはすべてまとめてGithubにも置いてあります。

Reference