range over funcで始めるグラフアルゴリズム

DMM.go #8 ショートセッション登壇

イベントリンク
https://dmm.connpass.com/event/322113/

Transcript

1. © DMM 1 range over funcで始めるグラフアルゴリズム DMM.go #8
2. © DMM 自己紹介 名前：　　屋比久 怜央（やびく れお） 配属予定：開発統括本部 　　　　　マーケティングテクノロジー部 　　　　　第一エンジニアチーム 趣味：　　ビリヤード・リアル脱出ゲーム 好きな標準ライブラリ：sync 2
3. © DMM 今回の発表の目的 • go1.23で導入されるrange over funcの使い方がわかる • range over funcでパフォーマンスの改善が見込めるかを判断できるよ うになる 3
4. © DMM 4 1. range over funcの概要 2. 今回扱うグラフアルゴリズム 3. range over funcによる実装
5. © DMM 5 1. range over funcの概要 2. 今回扱うグラフアルゴリズム 3. range over funcによる実装
6. © DMM range over funcとは？ • 関数の返り値として、for文に利用できるイテレータを返す 記法 • go1.23で提供予定 6
7. © DMM 実行環境の用意 • go1.23は今年8月リリース予定 • 実行環境を用意する方法は現在二つ • go1.22のGOEXPERIMENT • 1.23rc1 7 $ GOEXPERIMENT=rangefunc go run main.go $ go install golang.org/dl/go1.23rc1/@latest $ go1.23rc1 download $ go1.23rc1 run main.go
8. © DMM 基本的な使い方 • Go Wiki記載の実装例 • 初見だと複雑に見える、、、 8
9. © DMM 簡易な例 • 関数yieldに渡した値を、for文で受け取ることができる 9
10. © DMM 簡易な例 • 関数yieldはboolを返す • 後続のyieldが実行されるならtrue、そうでなければfalse • 関数yieldの返り値がfalseなら、処理を中断する必要がある 10
11. © DMM 基本的な使い方（再掲） • Go Wiki記載の実装例 • 初見だと複雑に見える、、、 11
12. © DMM 12 従来ならsliceを返す関数が イテレータ を返している
13. © DMM iterパッケージで提供されている型 • iterパッケージがSeq[V any]型を提供している • 関数の返り値がiter.Seqになる 13 type Seq[V any] func(yield func(V) bool)
14. © DMM iterパッケージで提供されている型 • iter.Seq • iter.Seq2 14
15. © DMM 15 1. range over funcの概要 2. 今回扱うグラフアルゴリズム 3. range over funcによる実装
16. © DMM グラフアルゴリズムとは • 辺と頂点からなるグラフから情報を抽出する操作のこと 16 G S 最短経路探索 二部グラフ判定 トポロジカルソート 3 1 2 4 5 6 2 3 3 5 3 7 1 1
17. © DMM トポロジカルソートをもっと詳しく • 順序を保ったままグラフを一列に並べる操作 • 正確には • 任意の有向辺に対して始点よりも終点が後に来るような、 全頂点の順列を見つける操作 17
18. © DMM トポロジカルソートをもっと詳しく 18 １ ５ ６ ３ ４ ２ ３ １ ２ ４ ５ ６
19. © DMM トポロジカルソートをもっと詳しく • 順序を保ったままグラフを一列に並べる操作 • 正確には • 任意の有向辺に対して始点よりも終点が後に来るような、 全頂点の順列を見つける操作 • 有向非巡回グラフに対する操作 • ループが存在すると一列に並べられない 19 入力に制限あり
20. © DMM トポロジカルソートをもっと詳しく 20 １ ５ ６ ３ ４ ２ ３ １ ２ ４ ５ ６
21. © DMM トポロジカルソートのアルゴリズム 1. 全頂点の入次数を保持する 2. 入次数が0の頂点を保持する 3. 以下を繰り返す a. 入次数が0の頂点を一つ選ぶ b. 選んだ頂点を出力する c. その頂点を始点とする有向辺を取り除く 21
22. © DMM トポロジカルソートのアルゴリズム 1. 全頂点の入次数を保持する 2. 入次数が0の頂点を保持する 3. 以下を繰り返す a. 入次数が0の頂点を一つ選ぶ b. 選んだ頂点を出力する c. その頂点を始点とする有向辺を取り除く 22
23. © DMM トポロジカルソートのアルゴリズム 1. 全頂点の入次数を保持する 2. 入次数が0の頂点を保持する 3. 以下を繰り返す a. 入次数が0の頂点を一つ選ぶ b. 選んだ頂点を出力する c. その頂点を始点とする有向辺を取り除く 23
24. © DMM トポロジカルソートのアルゴリズム 1. 全頂点の入次数を保持する 2. 入次数が0の頂点を保持する 3. 以下を繰り返す a. 入次数が0の頂点を一つ選ぶ b. 選んだ頂点を出力する c. その頂点を始点とする有向辺を取り除く 24
25. © DMM トポロジカルソートのアルゴリズム 1. 全頂点の入次数を保持する 2. 入次数が0の頂点を保持する 3. 以下を繰り返す a. 入次数が0の頂点を一つ選ぶ b. 選んだ頂点を出力する c. その頂点を始点とする有向辺を取り除く 25 どの頂点からも辺を向けられていない頂点を取 り除き続ければいい
26. © DMM 26 1. range over funcの概要 2. 今回扱うグラフアルゴリズム 3. range over funcによる実装
27. © DMM 有向グラフの扱い方 隣接リストで有向グラフを表現する 27 １ ５ ６ ３ ４ ２
28. © DMM 28 range over funcを使わない実装 お先に
29. © DMM まずは普通の実装 1 / 3 全頂点の入次数を保持する 29
30. © DMM まずは普通の実装 2 / 3 入次数が0の頂点を保持する 30
31. © DMM まずは普通の実装 3 / 3 以下を繰り返す 31 入次数が0の頂点を一つ選ぶ 選んだ頂点を出力する その頂点を始点とする 有向辺を取り除く
32. © DMM 32 range over funcによる実装
33. © DMM range over funcによる実装 • 1, 2は全く同様 1. 全頂点の入次数を保持する 2. 入次数が0の頂点を保持する • 3の出力をsliceではなくyieldに渡す 33
34. © DMM range over funcによる実装 3 / 3 以下を繰り返す 34 入次数が0の頂点を一つ選ぶ 選んだ頂点を出力する その頂点を始点とする 有向辺を取り除く
35. © DMM ベンチマーク • sliceを返却する実装とiter.Seqを返却する実装の比較 35 実行速度 メモリ使用量 アロケーション slice 293.8 ns/op 1248 B/op 3 allocs/op iter.Seq 258.0 ns/op 832 B/op 2 allocs/op メモリ使用量 アロケーション 2/3に減少 2/3に減少
36. © DMM 36 2/3？？
37. © DMM 37 トポロジカルソートって 3工程あったな…
38. © DMM トポロジカルソートのアルゴリズム（再掲） 1. 全頂点の入次数を保持する 2. 入次数が0の頂点を保持する 3. 以下を繰り返す a. 入次数が0の頂点を一つ選ぶ b. 選んだ頂点を出力する c. その頂点を始点とする有向辺を取り除く 38 どの頂点からも辺を向けられていない頂点を取り 除き続ければいい
39. © DMM トポロジカルソートのアルゴリズム（再掲） 1. 全頂点の入次数を保持する 2. 入次数が0の頂点を保持する 3. 以下を繰り返す a. 入次数が0の頂点を一つ選ぶ b. 選んだ頂点を出力する c. その頂点を始点とする有向辺を取り除く 39 どの頂点からも辺を向けられていない頂点を取り 除き続ければいい この二つは不変
40. © DMM トポロジカルソートのアルゴリズム（再掲） 1. 全頂点の入次数を保持する 2. 入次数が0の頂点を保持する 3. 以下を繰り返す a. 入次数が0の頂点を一つ選ぶ b. 選んだ頂点を出力する c. その頂点を始点とする有向辺を取り除く 40 どの頂点からも辺を向けられていない頂点を取り 除き続ければいい この二つは不変 slice or iter.Seq
41. © DMM メモリとアロケーションの差の考察 • 頂点の出力方法の違いが原因だと思われる 41
42. © DMM ベンチマークで確認 • sliceのappendをコメントアウトしてベンチマークを実行 42 実行速度 メモリ使用量 アロケーション slice(出力なし) 200.2 ns/op 832 B/op 2 allocs/op iter.Seq 257.0 ns/op 832 B/op 2 allocs/op
43. © DMM ベンチマークで確認 • sliceのappendをコメントアウトしてベンチマークを実行 43 実行速度 メモリ使用量 アロケーション slice(出力なし) 200.2 ns/op 832 B/op 2 allocs/op iter.Seq 257.0 ns/op 832 B/op 2 allocs/op メモリ使用量とアロケーションが一致 iter.Seqにすることで、sliceを用意する分の負荷を削減できる
44. © DMM sliceを返す関数はアンチパターンなのか • そうではない • sliceを返す方が望ましいケースもある • sliceの長さを取得したい場合 • sliceを使い回す場合 • トポロジカルソートにおいてはiter.Seqを利用するのが良い • sliceの長さは入力のグラフから取得できる • （sliceを使い回すかどうかはユースケースに依存するが、、、） 44
45. © DMM 45 まとめ
46. © DMM まとめ 46 • range over funcの利用方法の紹介
47. © DMM まとめ 47 • range over funcの利用方法の紹介 • sliceを返す実装とiter.Seqを返す実装のベンチマークを比較
48. © DMM まとめ 48 • range over funcの利用方法の紹介 • sliceを返す実装とiter.Seqを返す実装のベンチマークを比較 実行速度 メモリ使用量 アロケーション slice 293.8 ns/op 1248 B/op 3 allocs/op iter.Seq 258.0 ns/op 832 B/op 2 allocs/op
49. © DMM まとめ 49 • range over funcの利用方法の紹介 • sliceを返す実装とiter.Seqを返す実装のベンチマークを比較 返り値のsliceに相当するメモリとアロケーションの削減 実行速度 メモリ使用量 アロケーション slice 293.8 ns/op 1248 B/op 3 allocs/op iter.Seq 258.0 ns/op 832 B/op 2 allocs/op
50. © DMM 50 ご清聴ありがとうございました