Diff algorithm abstraction in Go

Transcript

1. Diff algorithm abstraction in Go さくらインターネット株式会社 SRE本部技術支援室 久保達彦
2. Me • 久保達彦（くぼたつひこ） • @cubicdaiya (X, GitHub) • さくらインターネット株式会社 SRE本部技術支援室 • ピクシブ、メルカリ等を経て2023年から現職 • 「nginx実践入門」書きました(共著) • https://gihyo.jp/book/2016/978-4-7741-7866-0 • 2016年1月16日発売なので、もう10年前
3. Diff algorithm abstraction in Go
4. Diffのアルゴリズム解説と実装 by Me • Software Design2009年6月号に記載した記事 • di の動作原理を知る〜どのようにして差分を導き出すのか • https://gihyo.jp/dev/column/01/prog/2011/di ̲sd200906 • (多分)2008年頃にC++(のテンプレート)で実装したdi ライブラリ：dtl • https://github.com/cubicdaiya/dtl • Go(のGenerics)で実装したdi ライブラリ：gonp ff ff ff ff • https://github.com/cubicdaiya/gonp
5. 今日の発表時間は10分 • 差分を計算するというのは次の3つを求めることと同義 • Edit/Levenshtein Distance(編集距離、レーベンシュタイン距離) • Longest Common Subsequence(LCS、最長共通部分列) • Shortest Edit Script(SES) • 続きは前のページにあるリンクから
6. 文字列間のdiffを取る by gonp ff https://github.com/cubicdaiya/gonp/blob/master/examples/strdi .go
7. 時は2010年代後半 • GoにはまだGenericsがなかった • Genericsが導入されたのは2022年にリリースされたGo1.18 • 当時のGoにはGenericsが要る/要らない？論争が各所で観測されていた • ※個人の感想です • 私は要る派だった(ホントだよ) • Genericsがないとデータ構造とアルゴリズムを抽象化するのが困難だった • アルゴリズムを抽象化できないとデータ型毎に実装が必要でスケールしない(めんどい) fl • interface{}やre ectionではさすがに無理がある
8. diffアルゴリズムの抽象化 in dtl(C++版)
9. diffアルゴリズムの抽象化 in dtl(C++版)
10. diffアルゴリズムの抽象化 in gonp(Go版)
11. diffアルゴリズムの抽象化 in gonp(Go版)
12. diffアルゴリズムの抽象化 in gonp(Go版)
13. diffアルゴリズムの抽象化 in gonp(Go版)
14. diffアルゴリズムの抽象化 in gonp(Go版)
15. diffアルゴリズムの抽象化 in gonp(Go版)
16. diffアルゴリズムの抽象化 in gonp(Go版)
17. diffアルゴリズムの抽象化 in gonp(Go版)
18. diffアルゴリズムの抽象化 in gonp(Go版)
19. diffアルゴリズムの抽象化 in gonp(Go版)
20. データ構造/アルゴリズムを抽象化するためのGenerics • Genericsの真価はデータ構造やアルゴリズムの抽象化において発揮される • 一般的なWebアプリケーションやAPIの開発だとあまり使う機会はない • 差分アルゴリズム1つを取っても抽象化することのメリットは大きい • 文字列間、テキストファイル間等 • 差分にも種類がある(e.g. Uni ed Format Di erence) • 2010年代にgonpを実装した頃は面倒なので文字列しかサポートしていなかった • Genericsが導入されたその月(2022/03)に実装しました。簡単だね。 ff fi • https://zenn.dev/cubicdaiya/articles/0fa9c15e9cd295
21. おまけ https://github.com/cubicdaiya/gonp
22. おまけ https://github.com/cubicdaiya/gonp
23. おまけ https://github.com/cubicdaiya/gonp
24. いつの間にか結構使われていた • sqlcでも使われているそうです(本スライド作成時：2026/09/14) • https://github.com/sqlc-dev/sqlc • sqlc di というサブコマンドがある • https://github.com/sqlc-dev/sqlc/pull/1963 • https://docs.sqlc.dev/en/latest/howto/ci-cd.html • 最近だと上司が使ってた ff ff • https://github.com/monitoring-forge/check-di /pull/11
25. まとめ • Genericsの真価はアルゴリズムの抽象化において発揮される • Di 実装は結構需要がある • 差分をテキストではなく、データ構造として扱えるのはなんだかんだ で便利 • dtl(C++実装） • https://github.com/cubicdaiya/dtl • gonp(Go実装) ff • https://github.com/cubicdaiya/gonp