Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
range over funcで始めるグラフアルゴリズム
Search
やーびー
July 29, 2024
Programming
0
120
range over funcで始めるグラフアルゴリズム
DMM.go #8 ショートセッション登壇
イベントリンク
https://dmm.connpass.com/event/322113/
やーびー
July 29, 2024
Tweet
Share
Other Decks in Programming
See All in Programming
Modular Monolith Go Server with GraphQL Federation + gRPC
110y
1
570
開発を加速する共有Swift Package実践
elmetal
PRO
0
370
rails_girls_is_my_gate_to_join_the_ruby_commuinty
maimux2x
0
180
大公開!iOS開発の悩みトップ5 〜iOSDC Japan 2024〜
ryunakayama
0
190
The Future of Frontend i18n : Intl.MessageFormat
sajikix
1
2.5k
Regular Expressions, REXML, Automata Learning
makenowjust
0
190
LR で JSON パーサーを作る / Coding LR JSON Parser
junk0612
2
180
Ebitengineの1vs1ゲーム WebRTCの活用
ponyo877
0
360
Prompt Cachingは本当に効果的なのか検証してみた.pdf
ttnyt8701
0
510
[DroidKaigi 2024] Android ViewからJetpack Composeへ 〜Jetpack Compose移行のすゝめ〜 / From Android View to Jetpack Compose: A Guide to Migration
syarihu
1
200
Why Prism?
kddnewton
4
1.6k
Using Livebook to build and deploy internal tools @ ElixirConf 2024
hugobarauna
0
230
Featured
See All Featured
Happy Clients
brianwarren
96
6.6k
Designing for humans not robots
tammielis
248
25k
Typedesign – Prime Four
hannesfritz
39
2.3k
The Illustrated Children's Guide to Kubernetes
chrisshort
47
48k
The Brand Is Dead. Long Live the Brand.
mthomps
53
37k
Adopting Sorbet at Scale
ufuk
73
8.9k
Building a Scalable Design System with Sketch
lauravandoore
458
32k
Automating Front-end Workflow
addyosmani
1365
200k
A Philosophy of Restraint
colly
202
16k
How STYLIGHT went responsive
nonsquared
93
5.1k
GitHub's CSS Performance
jonrohan
1029
450k
Designing Experiences People Love
moore
138
23k
Transcript
© DMM 1 range over funcで始めるグラフアルゴリズム DMM.go #8
© DMM 自己紹介 名前: 屋比久 怜央(やびく れお) 配属予定:開発統括本部 マーケティングテクノロジー部 第一エンジニアチーム 趣味: ビリヤード・リアル脱出ゲーム
好きな標準ライブラリ:sync 2
© DMM 今回の発表の目的 • go1.23で導入されるrange over funcの使い方がわかる • range over
funcでパフォーマンスの改善が見込めるかを判断できるよ うになる 3
© DMM 4 1. range over funcの概要 2. 今回扱うグラフアルゴリズム 3.
range over funcによる実装
© DMM 5 1. range over funcの概要 2. 今回扱うグラフアルゴリズム 3.
range over funcによる実装
© DMM range over funcとは? • 関数の返り値として、for文に利用できるイテレータを返す 記法 • go1.23で提供予定
6
© 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
© DMM 基本的な使い方 • Go Wiki記載の実装例 • 初見だと複雑に見える、、、 8
© DMM 簡易な例 • 関数yieldに渡した値を、for文で受け取ることができる 9
© DMM 簡易な例 • 関数yieldはboolを返す • 後続のyieldが実行されるならtrue、そうでなければfalse • 関数yieldの返り値がfalseなら、処理を中断する必要がある 10
© DMM 基本的な使い方(再掲) • Go Wiki記載の実装例 • 初見だと複雑に見える、、、 11
© DMM 12 従来ならsliceを返す関数が イテレータ を返している
© DMM iterパッケージで提供されている型 • iterパッケージがSeq[V any]型を提供している • 関数の返り値がiter.Seqになる 13 type
Seq[V any] func(yield func(V) bool)
© DMM iterパッケージで提供されている型 • iter.Seq • iter.Seq2 14
© DMM 15 1. range over funcの概要 2. 今回扱うグラフアルゴリズム 3.
range over funcによる実装
© DMM グラフアルゴリズムとは • 辺と頂点からなるグラフから情報を抽出する操作のこと 16 G S 最短経路探索 二部グラフ判定
トポロジカルソート 3 1 2 4 5 6 2 3 3 5 3 7 1 1
© DMM トポロジカルソートをもっと詳しく • 順序を保ったままグラフを一列に並べる操作 • 正確には • 任意の有向辺に対して始点よりも終点が後に来るような、 全頂点の順列を見つける操作
17
© DMM トポロジカルソートをもっと詳しく 18 1 5 6 3 4 2
3 1 2 4 5 6
© DMM トポロジカルソートをもっと詳しく • 順序を保ったままグラフを一列に並べる操作 • 正確には • 任意の有向辺に対して始点よりも終点が後に来るような、 全頂点の順列を見つける操作
• 有向非巡回グラフに対する操作 • ループが存在すると一列に並べられない 19 入力に制限あり
© DMM トポロジカルソートをもっと詳しく 20 1 5 6 3 4 2
3 1 2 4 5 6
© DMM トポロジカルソートのアルゴリズム 1. 全頂点の入次数を保持する 2. 入次数が0の頂点を保持する 3. 以下を繰り返す a.
入次数が0の頂点を一つ選ぶ b. 選んだ頂点を出力する c. その頂点を始点とする有向辺を取り除く 21
© DMM トポロジカルソートのアルゴリズム 1. 全頂点の入次数を保持する 2. 入次数が0の頂点を保持する 3. 以下を繰り返す a.
入次数が0の頂点を一つ選ぶ b. 選んだ頂点を出力する c. その頂点を始点とする有向辺を取り除く 22
© DMM トポロジカルソートのアルゴリズム 1. 全頂点の入次数を保持する 2. 入次数が0の頂点を保持する 3. 以下を繰り返す a.
入次数が0の頂点を一つ選ぶ b. 選んだ頂点を出力する c. その頂点を始点とする有向辺を取り除く 23
© DMM トポロジカルソートのアルゴリズム 1. 全頂点の入次数を保持する 2. 入次数が0の頂点を保持する 3. 以下を繰り返す a.
入次数が0の頂点を一つ選ぶ b. 選んだ頂点を出力する c. その頂点を始点とする有向辺を取り除く 24
© DMM トポロジカルソートのアルゴリズム 1. 全頂点の入次数を保持する 2. 入次数が0の頂点を保持する 3. 以下を繰り返す a.
入次数が0の頂点を一つ選ぶ b. 選んだ頂点を出力する c. その頂点を始点とする有向辺を取り除く 25 どの頂点からも辺を向けられていない頂点を取 り除き続ければいい
© DMM 26 1. range over funcの概要 2. 今回扱うグラフアルゴリズム 3.
range over funcによる実装
© DMM 有向グラフの扱い方 隣接リストで有向グラフを表現する 27 1 5 6 3 4
2
© DMM 28 range over funcを使わない実装 お先に
© DMM まずは普通の実装 1 / 3 全頂点の入次数を保持する 29
© DMM まずは普通の実装 2 / 3 入次数が0の頂点を保持する 30
© DMM まずは普通の実装 3 / 3 以下を繰り返す 31 入次数が0の頂点を一つ選ぶ 選んだ頂点を出力する
その頂点を始点とする 有向辺を取り除く
© DMM 32 range over funcによる実装
© DMM range over funcによる実装 • 1, 2は全く同様 1. 全頂点の入次数を保持する
2. 入次数が0の頂点を保持する • 3の出力をsliceではなくyieldに渡す 33
© DMM range over funcによる実装 3 / 3 以下を繰り返す 34
入次数が0の頂点を一つ選ぶ 選んだ頂点を出力する その頂点を始点とする 有向辺を取り除く
© 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に減少
© DMM 36 2/3??
© DMM 37 トポロジカルソートって 3工程あったな…
© DMM トポロジカルソートのアルゴリズム(再掲) 1. 全頂点の入次数を保持する 2. 入次数が0の頂点を保持する 3. 以下を繰り返す a.
入次数が0の頂点を一つ選ぶ b. 選んだ頂点を出力する c. その頂点を始点とする有向辺を取り除く 38 どの頂点からも辺を向けられていない頂点を取り 除き続ければいい
© DMM トポロジカルソートのアルゴリズム(再掲) 1. 全頂点の入次数を保持する 2. 入次数が0の頂点を保持する 3. 以下を繰り返す a.
入次数が0の頂点を一つ選ぶ b. 選んだ頂点を出力する c. その頂点を始点とする有向辺を取り除く 39 どの頂点からも辺を向けられていない頂点を取り 除き続ければいい この二つは不変
© DMM トポロジカルソートのアルゴリズム(再掲) 1. 全頂点の入次数を保持する 2. 入次数が0の頂点を保持する 3. 以下を繰り返す a.
入次数が0の頂点を一つ選ぶ b. 選んだ頂点を出力する c. その頂点を始点とする有向辺を取り除く 40 どの頂点からも辺を向けられていない頂点を取り 除き続ければいい この二つは不変 slice or iter.Seq
© DMM メモリとアロケーションの差の考察 • 頂点の出力方法の違いが原因だと思われる 41
© 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
© 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を用意する分の負荷を削減できる
© DMM sliceを返す関数はアンチパターンなのか • そうではない • sliceを返す方が望ましいケースもある • sliceの長さを取得したい場合 •
sliceを使い回す場合 • トポロジカルソートにおいてはiter.Seqを利用するのが良い • sliceの長さは入力のグラフから取得できる • (sliceを使い回すかどうかはユースケースに依存するが、、、) 44
© DMM 45 まとめ
© DMM まとめ 46 • range over funcの利用方法の紹介
© DMM まとめ 47 • range over funcの利用方法の紹介 • sliceを返す実装とiter.Seqを返す実装のベンチマークを比較
© 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
© 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
© DMM 50 ご清聴ありがとうございました