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
Meet BrowserEngineKit
swiftty
0
330
Scala アプリケーションのビルドを改善してデプロイ時間を 1/4 にした話 | How I improved the build of my Scala application and reduced deployment time by 4x
nomadblacky
1
130
Go Code Generation at newmo / 2024-08-27 #newmo_layerx_go
genkey6
0
540
詳解UIWindow
natmark
3
2.2k
仮想ファイルシステムを導入して開発環境のストレージ課題を解消する
segadevtech
2
450
Rechartsで楽にゴリゴリにカスタマイズする!
10tera
1
140
プログラマのための音楽入門
cheebow
5
560
null or undefined
susisu
22
6k
ESLint Rule により事業, 技術ドメインに沿った制約と誓約を敷衍させるアプローチのすゝめ
shinyaigeek
1
2.9k
RAGの回答精度評価用のQAデータセットを生成AIに作らせた話
kurahara
0
230
New Order in Cascade Sorting Order
mugi_uno
3
2.5k
Desafios e Lições Aprendidas na Migração de Monólitos para Microsserviços em Java
jessilyneh
2
140
Featured
See All Featured
Navigating Team Friction
lara
183
13k
For a Future-Friendly Web
brad_frost
174
9.3k
Web development in the modern age
philhawksworth
204
10k
Mobile First: as difficult as doing things right
swwweet
220
8.8k
How GitHub (no longer) Works
holman
310
140k
Music & Morning Musume
bryan
46
6k
The Success of Rails: Ensuring Growth for the Next 100 Years
eileencodes
41
6.5k
In The Pink: A Labor of Love
frogandcode
139
22k
A Modern Web Designer's Workflow
chriscoyier
690
190k
Building Adaptive Systems
keathley
36
2.1k
Clear Off the Table
cherdarchuk
90
320k
Scaling GitHub
holman
458
140k
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 ご清聴ありがとうございました