【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からサーバへのパケット振り分けについて見ていきましょう。
(本論文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の整合性が取れなくなってしまいます。
(本論文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をまとめることができるようです。
(本論文Figure 5より引用)
このようにmappinされたBucketは、全MUXで共有されます。この方法では、サーバ台数が増減してもBが変わらず、実サーバとのmappingを調整するだけで対応できます。
(本論文Figure 4より引用)
Data planeとControl plane
MUXは、実際のパケットを処理するため、Date planeとして働きます。 注意事項としては、カプセル化で16Bのオーバーヘッドがあることでしょうか。カプセル化自体は、TRILLやVXLAN、VPNなどネットワークまわりでは広く顔を出すのでおかしなことではありませんが、LBの振り分けとなるサーバまでの経路上でMTUが制御される場合などは注意が必要なためオーバーヘッドがどの程度あるのか知っておくことは大切です。
また、Beamerでは、Bucketのmappingが変わることを適切に管理してあげる必要があります。
この役割は、ContollerがControl planeで実現しており、Beamerは、Apache ZooKeeperを使っているそうです。
(発表資料P.35より引用)
図のようにBucketが更新(v2)された場合、ZooKeeper経由で各MUXに通知され、各MUXが最新のBucketをダウンロードして、一貫性を保ちます。論文中では、2-phase commitで実現していると書かれていますが、このあたりはあまり詳しくないので詳細は本論文を読んでください。
Daisy chaining
Beamerでは、既存connectionを適切に扱うためDaisy chainingを使っています。
Bucketの再構成には、以下の課題の課題があります。
- 既存connectionが壊れる
- 一貫性が失われる（他が使ってるmappingをつかってしまう）
例えば、下記図の青いconnectionのように、もともとMUX2からサーバAにmappingされていた場合を考えます。
(本論文Figure 6より引用)
Bucketの再構成によってこのconnectionがサーバBにmappingされた場合、
すでにestablishedな青いconnectionは、サーバAに振り分けられる必要があります。
Beamerでは、PDIP(previous DIP)という一つ前にmappingされた実サーバを覚えておき、一定時間は前のサーバに転送することで既存が壊れることを防ぎます。
ベンチマーク
まず1コアでのベンチマークです。ここでは、性能をpps(packet per second)を、パケットサイズが変化させて比較しています。
(本論文Figure 13より引用)
StatefulなLBに対して、short packetである64Bでも2倍程度の性能が出ています。 また、コアを2つにすればline rateと同レベルの性能になっています。
論文中で最終的な性能は、以下の図で記載されています。
(本論文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
- Olteanu, Vladimir, et al. "Stateless Datacenter Load-balancing with Beamer." 15th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 18). USENIX} Association}, 2018.
- Stateless Datacenter Load-balancing with Beamer
- Stateless datacenter load-balancing with Beamer - the morning paper
- Beamer
- Stateless Datacenter Load Balancing with Beamer
- Eisenbud, Daniel E., et al. "Maglev: A Fast and Reliable Software Network Load Balancer." NSDI. 2016.
【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を行います。 アルゴリズムは以下になります。
- 入力となる始点(頂点)
sに対して、現在訪れている頂点cをsとする - 頂点
cが訪問済みか確認する（訪問済みならcycleありを返して終了。未訪問なら後続のステップへ） - 頂点
cを訪問済みにする - 頂点
cに接続する頂点を順に訪れる
以下、2.から繰り返し
※cはcurrentの意で命名
すべての頂点の探索が終了すればcycleなしとして探索終了です。
例：cycleあり
以下の例でイメージを掴んでみましょう。
まず始点sを頂点0とします。各頂点からの接続されている頂点への移動は、一つ前の頂点以外である必要があります。ここではわかりやすいように、一つ前の頂点以外で最も値が小さい頂点に移動するとしましょう。
移動を表にまとめると以下のとおりです。
| 頂点c | 訪問済みの頂点 |
|---|---|
| 0 | 0 |
| 1 | 0,1 |
| 3 | 0,1,3 |
| 0 | 0,1,3 |
頂点3から頂点0に移動した時点でステップ2.の確認で頂点0(太字)が訪問済みであるため、cycleあり となります
例：cycleなし
先程の例から辺1-3を削除したものを考えてみます。
先程と同様に始点sを頂点0とし、移動を表にまとめると以下のとおりです。
| 頂点c | 訪問済みの頂点 |
|---|---|
| 0 | 0 |
| 1 | 0,1 |
| 2 | 0,1,2 |
| 3 | 0,1,2,3 |
すべての頂点を探索しても訪問済みの頂点がなかったため、cycleなし となります
設計
データ構造をどうするか
グラフのデータ構造といえば、隣接リストと隣接行列ですが、上記の例で考えたように次に訪れる頂点さえわかればよいので隣接リストを採用します。 上記の例では以下の表のようにグラフを保持します。
例：cycleあり
| 頂点 | 隣接する頂点 |
|---|---|
| 0 | 1,2,3 |
| 1 | 0,3 |
| 2 | 0 |
| 3 | 0,1 |
例：cycleなし
| 頂点 | 隣接する頂点 |
|---|---|
| 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 }
辺の追加
GraphにAddEdgeを生やします。
// 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) }
今回は省略しますが、できれば以下をエラーチェックしたほうがよいでしょう。
uとvが同一頂点でないこと- 初期化の頂点に含まれていないこと
DFSによるcycle detectの実装
DFSの実装には、スタックを用いた実装と再帰を用いた実装がありますが、再帰のほうがコードがシンプルになることが多いので、再帰で実装することにします。 アルゴリズム自体は冒頭に書いた通りですが、実装のポイントを以下です。
- 訪問済みの頂点を
visitedとし、mapで持つ
→ Golangのmapとsliceはどちらが速いのか - 逆さまにしたでベンチマークを取った通り、探索まで含めるとsliceだと遅くなってしまいます。今回は、訪れた頂点が 既に訪問済みか を確認したいのでmapにします。set型がないGoでは、mapを用いてset型の代わりのデータ構造を実装することがありますが、この時、strct{}がGo上ではサイズ0となることからmap[int]strct{}として実装するのがよいです。
- 一つ前の頂点には戻らない
→ 直前にいた頂点に戻るようなDFSの実装にしてしまうと、visitedがtrueを返すので、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 }
dfsをGraph型の変数からメソッドとして呼び出せるように以下のように実装します。
func (g *Graph) ExistsCycle() bool { return dfs(-1, 0, g.edges, map[int]struct{}{}) }
ここで、pは直前に訪れた頂点がないためdfs()中のv == pがfalseになるようにp = -1としています。さらに探索を開始する頂点(冒頭のアルゴリズムにあるs)は、どこでもいいので、s = 0から始めています。
テスト
上記の例で正しく動作することを試してみます。
例：cycleあり
| 頂点 | 隣接する頂点 |
|---|---|
| 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なし
| 頂点 | 隣接する頂点 |
|---|---|
| 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のアクセス速度一定の恩恵が発揮される。
実際にベンチマークを取ってみる。
測定したいこと
条件
- 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 |
単純なインデックスアクセスであれば、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 |
mapは要素数に依存しない定数時間になっている。sliceのほうは、Binary SearchがO(logN)で、探索に大部分の時間を費やしてしまっていることがわかる。sort済みのsliceですらこの結果になってしまうので、Existsメソッドを生やしたいような場合では、mapを使ったほうがよいと思われる。
結論
要素数の増加に従って、sliceとmapでインデックスアクセス速度がどのように変わるか
→ 単純なインデックスアクセスであれば、sliceのほうが8.5倍程度速いsliceから特定の要素を探すとき、mapと性能分岐点になる要素数はいくつか
→ searchも含めて行う場合は、mapのほうが速い
同内容をGithubにも上げている。
References
ビットコインとブロックチェーン:暗号通貨を支える技術を読んだ
Mastering Bitcoinの邦訳であるビットコインとブロックチェーン:暗号通貨を支える技術/アンドレアス・M・アントノプロス (著), 今井 崇也 (翻訳), 鳩貝 淳一郎 (翻訳)を読みました。
Blockchainのバイブルと名高い本書ですが、その評判に違わない内容でした。 2009年にナカモトサトシが論文を発表して以来、数多くの記事がネット上に存在し、十分な情報がある現在ですが、どうしても今一歩疑問が解決できない事柄が多々ありました。個人的には以下の2つが、なんとなくはわかるけど、どうもしっくりこない事柄でした。
- UTXO
- マークル木
具体的にはそれぞれ、以下のような疑問がずっとありましたが、本書を読んで解決することができました。
UTXOの疑問点
UTXOがアカウントベースではないというのは、理解できるものの以下がよくわかりませんでした。
- 特定のアドレスの残高はどうやってわかるのか
この疑問は、以下の記載で氷解しました。
ウォレットは、ブロックチェーンをスキャンしてユーザに属しているすべてのUTXOを掻き集め、残高を計算しているのです。
Blockchainの機能として残高がわかるわけではなく、ウォレットの機能なのですね。 その他にも以下のような疑問がありました。
- コインをロックするとは、どういうことなのか
- 任意の精度でアウトプットがロックされてしまうと、ゴミのようなコインばかりになってしまうのではないか
これらの疑問は以下の文章で理解できました。
・ビットコインの最小単位であるsatoshi単位で表されたビットコイン金額 ・アウトプットを使用するにあたって満たさなければいけない「解除条件(encumbrance)」として知られているlocking script
コインのロックとは、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 coreやlibbitcoin/bitcoin explorerや EthereumのVitalikが作成したpythonライブラリpybitcointoolsなどを使って、上記のxから始めるアドレスというようなアドレスを実際に生成してみたり、bitcoinコアのコマンドからblockやtx、utxoの情報を取得したりします。
コードは多いですが、自分で実装を考える部分はほぼなく、写経する形になると思います。
むしろ大変なのは、150GB(2018/04/13時点)を超えるフルノードの同期と、バージョンが違うことによる./configureとmakeのエラー解消だと思います。実際、読書時点の2018/04/13時点で安定バージョンだったv0.16.0では、本書の内容から変更されている部分もありました。第3章から第6章を自分でやってみた際の結果と変更に応じて対処した点は、こちらにログを残しているのでご参考にどうぞ。
その他収穫だったところ
今までわからなかったscript言語もスタックマシンであるという説明があり、実際にscriptSigとscriptPubKeyが組み合わされることでUTXOのロックを解除する流れや簡単な例が記載されており、マルチシグのような条件付きスクリプトも読めるようになったのは大きな収穫です。 その他にも階層的決定性ウォレットやトランザクションプール、extra nonceなど興味深いトピックが多数含まれており、とても勉強になりました。
こういう人におすすめ
上述の通り、コマンドライン上でbxを実行したり、C++、pythonのコードもありますが、そこまで難しくはないです。
とはいえ、どの言語も触ったことがないという方だと少し難しい部分もあるかと思うので、技術的な観点からBlockchainを理解したいエンジニアの方には自信をもってオススメできます。
- 作者: アンドレアス・M・アントノプロス,今井崇也,鳩貝淳一郎
- 出版社/メーカー: エヌティティ出版
- 発売日: 2016/07/14
- メディア: 大型本
- この商品を含むブログ (7件) を見る
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
結果です。
本文で実装した内容でパッケージ化したので、以下に使い方を含めてまとめています。 【Golang】Ward法で階層的クラスタリングするパッケージを書いた - 逆さまにした
99. t-SNEによる可視化
96の単語ベクトルに対して，ベクトル空間をt-SNEで可視化せよ．
Q98と同様に可視化部分は自分で実装する必要があったのでgonum/plotで以下のように実装しました。
gist63aad7d67083a70dc8230315588ae407
本題はこちら。
gistab950a1bd807782eab10859a55633e56
結果です。
t-SNEの計算は、tsne4goを使いました。 最初可視化した際には黒一色で表示していましたが、意味が理解できなかったので、Q97のk-meansで色分けしています。 そもそもt-SNEとk-meansの相性がいいのか知りませんが、気持ち分類できているかなというところでしょうか。
感想
以上で言語処理処理100本ノックの全100問完走です。 途中で半年くらい間開けてしまったりしたので結構長く掛かりましたが完走できてよかったです。 ただ、前章のQ85が微妙な結果だったので、Q85が実装できたら本章も再チャレンジしたいです。
もともとGoを触り始めて慣れるために始めたのですが、いろいろ実装できて自然言語処理の勉強に加えて、Goの勉強にもなりました。 特にGoで100本ノックやっている方をほかに見かけないので自力で頑張る必要があったのも結果的にはよかったのかと思います。 お付き合いありがとうございました。
コードはすべてまとめてGithubにも置いてあります。
Reference
- 言語処理100本ノック 2015
- Lev Finkelstein, Evgeniy Gabrilovich, Yossi Matias, Ehud Rivlin, Zach Solan, Gadi Wolfman, and Eytan Ruppin, "Placing Search in Context: The Concept Revisited", ACM Transactions on Information Systems, 20(1):116-131, January 2002.
- スピアマンの順位相関係数 - Wikipedia
- dgryski/go-onlinestats
- List of countries of the world in alphabetical order
- k平均法 - Wikipedia
- linkage - MathWorks
- ウォード法によるクラスタリングのやり方
- 【Golang】Ward法で階層的クラスタリングするパッケージを書いた - 逆さまにした
- t-SNEによるイケてる次元圧縮&可視化
- t-SNE を用いた次元圧縮方法のご紹介
- CSS Colors - w3schools.com
- tsne4go
【Golang】Ward法で階層的クラスタリングするパッケージを書いた
背景
言語処理100本ノックのQ98を解くにあたって、Go実装がなかったので実装し、goClusteringというパッケージにしました。k-meansもQ97で実装したので、将来的には他のクラスタリングアルゴリズムも統合するかもしれません。
概要
内部的には、階層構造を二分木で表現し、距離尺度に分散を用いて2つのグループを一つにまとめる操作を再帰で実装しています。 実装はこちら。
可視化には、gonum/plotを用いています。 こちらも樹形図は自前で実装しています。 以下のように可視化できます。
使い方
READMEにも記載していますが、こちらでも紹介します。
How to Install
go getでインストールします。
go get github.com/cipepser/goClustering/...
可視化でgonum/plotを使うのでこちらもgo getします。
go get gonum.org/v1/plot/...
How to Use
入力はn * dの行列Xです。ここでnは観測データ数、dは特徴ベクトルの次元です。
以下を実行することで、ward.Tree型の結果を得られます。
T := ward.Ward(X)
次にこれを可視化します。
d, _ := plotter.NewDendrogram(T) p, err := plot.New() p.Add(d)
図のタイトルや軸名を設定します。
p.Title.Text = "Dendrogram" p.X.Label.Text = "data" p.Y.Label.Text = "distance"
葉ノードを設定します。要素が多くなった場合には回転することもできます。
p.NominalX("aaa", "bbb", "ccc", "ddd", "eee", "fff") p.X.Tick.Label.Rotation = math.Pi / 3 p.X.Tick.Label.YAlign = draw.YCenter p.X.Tick.Label.XAlign = draw.XRight
Example
package main import ( "math" "github.com/cipepser/goClustering/ward" "github.com/cipepser/goClustering/vis" "gonum.org/v1/plot" "gonum.org/v1/plot/vg" "gonum.org/v1/plot/vg/draw" ) func main() { // input data set X := [][]float64{ {0, 0}, {2, 2}, {1, 1}, {2, -1.2}, {3, 2.2}, {3.5, 0.5}, } // Ward's method T := ward.Ward(X) // draw the dendrogram d, err := plotter.NewDendrogram(T) if err != nil { panic(err) } p, err := plot.New() if err != nil { panic(err) } p.Add(d) p.Title.Text = "Dendrogram" p.X.Label.Text = "data" p.NominalX("aaa", "bbb", "ccc", "ddd", "eee", "fff") p.X.Tick.Label.Rotation = math.Pi / 3 p.X.Tick.Label.YAlign = draw.YCenter p.X.Tick.Label.XAlign = draw.XRight p.Y.Label.Text = "distance" // save as a png file file := "img.png" if err = p.Save(10*vg.Inch, 6*vg.Inch, file); err != nil { panic(err) } }
