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
200
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
非ブラウザランタイムとWeb標準 / Non-Browser Runtimes and Web Standards
petamoriken
0
410
return文におけるstd::moveについて
onihusube
1
1.4k
Monixと常駐プログラムの勘どころ / Scalaわいわい勉強会 #4
stoneream
0
320
Findy Team+ Awardを受賞したかった!ベストプラクティス応募内容をふりかえり、開発生産性向上もふりかえる / Findy Team Plus Award BestPractice and DPE Retrospective 2024
honyanya
0
130
PHPで作るWebSocketサーバー ~リアクティブなアプリケーションを知るために~ / WebSocket Server in PHP - To know reactive applications
seike460
PRO
2
720
命名をリントする
chiroruxx
1
570
Fibonacci Function Gallery - Part 1
philipschwarz
PRO
0
270
オニオンアーキテクチャを使って、 Unityと.NETでコードを共有する
soi013
0
350
103 Early Hints
sugi_0000
1
330
どうして手を動かすよりもチーム内のコードレビューを優先するべきなのか
okashoi
3
820
「とりあえず動く」コードはよい、「読みやすい」コードはもっとよい / Code that 'just works' is good, but code that is 'readable' is even better.
mkmk884
6
1.3k
良いユニットテストを書こう
mototakatsu
11
3.5k
Featured
See All Featured
10 Git Anti Patterns You Should be Aware of
lemiorhan
PRO
656
59k
Imperfection Machines: The Place of Print at Facebook
scottboms
266
13k
CSS Pre-Processors: Stylus, Less & Sass
bermonpainter
356
29k
Testing 201, or: Great Expectations
jmmastey
41
7.2k
Reflections from 52 weeks, 52 projects
jeffersonlam
348
20k
A Modern Web Designer's Workflow
chriscoyier
693
190k
BBQ
matthewcrist
85
9.4k
Distributed Sagas: A Protocol for Coordinating Microservices
caitiem20
330
21k
Building a Modern Day E-commerce SEO Strategy
aleyda
38
7k
GraphQLの誤解/rethinking-graphql
sonatard
68
10k
Keith and Marios Guide to Fast Websites
keithpitt
410
22k
Why You Should Never Use an ORM
jnunemaker
PRO
54
9.1k
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 ご清聴ありがとうございました