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

【Golang】DFS(深さ優先探索)による無向グラフのcycle detectを実装する - 逆さまにしたの続きで、今度は有向グラフのcycle detectです。 Detect Cycle in Directed Graph Algorithmを視聴したので、実装してみることにします。

有向グラフにおけるDFSによるcycle detectのアルゴリズム

有向グラフでは、同じDFSによるcycle detectでも、無向グラフのときと異なり、White Set、Grey Set、Black Setという3つの集合を利用します。特にGrey Setは、無向グラフにおけるVisited Setの役割を果たします。 これらの集合を使い、以下のアルゴリズムでDFSによるcycle detectを行います。

1. すべての頂点をWhite Setに追加する
2. White Setから頂点sを取り出す
3. 頂点sをGrey Setに加える
4. 頂点sの接続先である頂点cを順番に訪問する。未訪問の接続先がなくなった(葉のように元々接続先がない場合も含む)場合、頂点sをBlack Setに加え、一つ前に訪問した頂点を頂点sとして、4.を繰り返す
5. 頂点cがBlack Setに含まれていれば、4.における次の頂点へ
6. 頂点cがGrey Setに含まれていれば、cycleありとして探索終了
7. 5.,6.のいずれでもない(=頂点cがWhite Setに含まれる)場合は、3.から繰り返し
8. White Setが空になったら、cycleなしとして探索終了

※sはstartの意で命名(White Setから取り出す度に設定されるので厳密には始点ではないですが) ※cはcurrentの意で命名

例：cycleあり

2→4→5→2のcycleがある例です。

頂点0から上記のアルゴリズムを適用した場合のWhite Set、Grey Set、Black Setの変化を表にまとめると以下の通りです。

頂点	White Set	Grey Set	Black Set
-	0,1,2,3,4,5	-	-
0	1,2,3,4,5	0	-
1	2,3,4,5	0,1	-
3	2,4,5	0,1,3	-
1	2,4,5	0,1	3
4	2,5	0,1,4	3
5	2	0,1,4,5	3
2	-	0,1,2,4,5	3

最終行の時点で、頂点2がGrey Setに含まれるため、cycleありとなります。

例：cycleなし

上記の例から2→4の辺を除き、cycleをなくした例です。

こちらも先程と同様に、White Set、Grey Set、Black Setの変化を表にまとめます。途中までは一緒ですね。

頂点	White Set	Grey Set	Black Set
-	0,1,2,3,4,5	-	-
0	1,2,3,4,5	0	-
1	2,3,4,5	0,1	-
3	2,4,5	0,1,3	-
3	2,4,5	0,1	3
1	2,4,5	0,1	3
4	2,5	0,1,4	3
5	2	0,1,4,5	3
2	-	0,1,2,4,5	3
5	-	0,1,4,5	2,3
4	-	0,1,4	2,3,5
1	-	0,1	2,3,4,5
0	-	0	1,2,3,4,5
-	-	-	0,1,2,3,4,5

White Setを探索し終わったので、cycleなしとなります。

設計

隣接リスト

【Golang】DFS(深さ優先探索)による無向グラフのcycle detectを実装する - 逆さまにした同様に隣接リストで実装します。上記の例はそれぞれ以下のようにリストを持つことになります。

例：cycleあり

頂点	隣接リスト
0	1,2
1	3,4
2	4
3	-
4	5
5	2

例：cycleなし

頂点	隣接リスト
0	1,2
1	3,4
2	-
3	-
4	5
5	2

各Setをどうするか

White Set、Grey Set、Black Setをcolorという[]int型で実装することも考えましたが、有向グラフでは強連結でないグラフに対して扱いが難しくなりそうだったのでmapで実装します。 sliceとmapのdelete(+make)はどちらが速いのか - 逆さまにしたの結果が、無駄になってしまったのは残念ですが、Setと言っているのでmapのほうがわかりやすく実装できると考えて前に進むことにします。

実装

【Golang】DFS(深さ優先探索)による無向グラフのcycle detectを実装する - 逆さまにしたと同様に以下のように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
}

辺の追加

AddEdgeは、無向グラフと異なり、片方向にだけ辺を追加する点に注意です。

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

DFSによるcycle detectの実装

基本的には、記事の先頭で述べたアルゴリズムを実装していくだけですが、White Setから頂点を選ぶ操作は以下のように実装しました。

c := -1
for c = range wSet {
  break
}

mapにはpopがないので、rangeでランダムに(mapに対するrangeは順序を保ちません)1つ取得し、breakしています。 これを踏まえた実装は以下です。

func dfs(c int, wSet, gSet, bSet map[int]struct{}, edges [][]int) bool {
    delete(wSet, c)
    gSet[c] = struct{}{}

    for _, n := range edges[c] {
        _, ok := bSet[n]
        if ok {
            continue
        }
        _, ok = gSet[n]
        if ok {
            return true
        }
        if dfs(n, wSet, gSet, bSet, edges) {
            return true
        }
    }

    delete(gSet, c)
    bSet[c] = struct{}{}
    return false
}

呼び出し側では、初期化も含めて行っています。

func (g *Graph) ExistsCycle() bool {
    wSet := make(map[int]struct{}, g.n)
    gSet := make(map[int]struct{}, g.n)
    bSet := make(map[int]struct{}, g.n)

    for i := 0; i < g.n; i++ {
        wSet[i] = struct{}{}
    }

    for len(wSet) != 0 {
        c := -1
        for c = range wSet {
            break
        }
        if dfs(c, wSet, gSet, bSet, g.edges) {
            return true
        }
    }
    return false
}

テスト

最後に上述の例で正しく動作することを試してみます。

例：cycleあり

頂点	隣接リスト
0	1,2
1	3,4
2	4
3	-
4	5
5	2

g := directed.NewGraph(6)
g.AddEdge(0, 1)
g.AddEdge(0, 2)
g.AddEdge(1, 3)
g.AddEdge(1, 4)
g.AddEdge(2, 4)
g.AddEdge(4, 5)
g.AddEdge(5, 2)

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

例：cycleなし

頂点	隣接リスト
0	1,2
1	3,4
2	-
3	-
4	5
5	2

g := directed.NewGraph(6)
g.AddEdge(0, 1)
g.AddEdge(0, 2)
g.AddEdge(1, 3)
g.AddEdge(1, 4)
g.AddEdge(4, 5)
g.AddEdge(5, 2)

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

References

• Detect Cycle in Directed Graph Algorithm
• Go言語 - enumを定義する
• 強連結成分分解の意味とアルゴリズム

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)
    }
}

結果

要素数が少ないと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

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

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

一貫して、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

• Golangでmapとsliceどちらが速いのか
• SliceTricks
• Source file src/runtime/hashmap.go - The Go Programming Language
• Source file src/runtime/slice.go - The Go Programming Language

【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を行います。 アルゴリズムは以下になります。

1. 入力となる始点(頂点)sに対して、現在訪れている頂点cをsとする
2. 頂点cが訪問済みか確認する（訪問済みならcycleありを返して終了。未訪問なら後続のステップへ）
3. 頂点cを訪問済みにする
4. 頂点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

• Cycle in Undirected Graph Graph Algorithm
• graph
• グラフ探索アルゴリズムとその応用
• 深さ優先探索 - Wikipedia
• container/list
• Golangのcontainer/listでスタックとキュー
• Golangのmapとsliceはどちらが速いのか - 逆さまにした
• GoのパフォーマンスTipsメモ

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

単純なインデックスアクセスであれば、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を使ったほうがよいと思われる。

結論

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

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

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

References

• GoのパフォーマンスTipsメモ

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

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 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を理解したいエンジニアの方には自信をもってオススメできます。

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

References

• Nakamoto, Satoshi. "Bitcoin: A peer-to-peer electronic cash system." 2009.
• Bitcoin Core integration/staging tree
• Libbitcoin
• pybitcointools

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)