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
Fuzzy finder as a Go library
Search
ktr
May 18, 2019
Programming
3
6.1k
Fuzzy finder as a Go library
Go Conference 2019 Spring
ktr
May 18, 2019
Tweet
Share
More Decks by ktr
See All by ktr
あまり知られていない MCP 仕様たち / MCP specifications that aren’t widely known
ktr_0731
0
350
CLI ツールを Go ライブラリ として再実装する理由 / Why reimplement a CLI tool as a Go library
ktr_0731
3
1.3k
激動の一年を通じて見えてきた「技術でリードする」ということ
ktr_0731
8
9.9k
Monorepo における Go テストの差分実行 / Running Differential Go Tests in a Monorepo
ktr_0731
1
310
Designing libraries in Go way
ktr_0731
7
1.6k
Go Modules and Proxy Walkthrough
ktr_0731
8
27k
ソフトウェアの複雑さに立ち向かう技術 / Tackling software complexity
ktr_0731
0
220
つよくてニューゲーム / NewGame++
ktr_0731
0
1k
やはり俺の Go アプリケーション設計はまちがっている。 / My Go Application Design Is Wrong, As I Expected
ktr_0731
13
3.7k
Other Decks in Programming
See All in Programming
TFLintカスタムプラグインで始める Terraformコード品質管理
bells17
2
160
スマホから Youtube Shortsを見られないようにする
lemolatoon
27
31k
Your Perfect Project Setup for Angular @BASTA! 2025 in Mainz
manfredsteyer
PRO
0
170
Six and a half ridiculous things to do with Quarkus
hollycummins
0
170
Go言語はstack overflowの夢を見るか?
logica0419
0
260
CSC509 Lecture 05
javiergs
PRO
0
300
私達はmodernize packageに夢を見るか feat. go/analysis, go/ast / Go Conference 2025
kaorumuta
2
550
Swift Concurrency - 状態監視の罠
objectiveaudio
2
520
Range on Rails ―「多重範囲型」という新たな選択肢が、複雑ロジックを劇的にシンプルにしたワケ
rizap_tech
0
120
kiroとCodexで最高のSpec駆動開発を!!数時間で web3ネイティブなミニゲームを作ってみたよ!
mashharuki
0
170
Introducing ReActionView: A new ActionView-Compatible ERB Engine @ Kaigi on Rails 2025, Tokyo, Japan
marcoroth
3
1k
Catch Up: Go Style Guide Update
andpad
0
220
Featured
See All Featured
A Modern Web Designer's Workflow
chriscoyier
697
190k
Distributed Sagas: A Protocol for Coordinating Microservices
caitiem20
333
22k
Product Roadmaps are Hard
iamctodd
PRO
54
11k
ReactJS: Keep Simple. Everything can be a component!
pedronauck
667
120k
Unsuck your backbone
ammeep
671
58k
The Invisible Side of Design
smashingmag
302
51k
Building an army of robots
kneath
306
46k
Refactoring Trust on Your Teams (GOTO; Chicago 2020)
rmw
35
3.2k
The MySQL Ecosystem @ GitHub 2015
samlambert
251
13k
Practical Orchestrator
shlominoach
190
11k
4 Signs Your Business is Dying
shpigford
185
22k
Balancing Empowerment & Direction
lara
4
690
Transcript
BU(P$POGFSFODF4QSJOH Fuzzy finder as a Go library
XIPBNJ w LUS Ωλϩʔɺ!LUS@ w ৽ଔ w (Pͱ$-*πʔϧ͕͖͢
None
'V[[ZpOEFSJTԿ
wೖྗʹର͠ɺ͍͋·͍ݕࡧ ʹΑͬͯΠϯλϥΫςΟϒʹ ಛఆͷߦΛબͰ͖Δ wίϚϯυϥΠϯGV[[ZpOEFS G[G G[Z FUD 'V[[ZpOEFS
$ cd `ghq root`/`ghq list | fzf` HIRԼͷϦϙδτϦʹҠಈ
$ git branch | egrep -v '^\*' | fzf |
xargs git checkout ΠϯλϥΫςΟϒʹνΣοΫΞτઌ ϒϥϯνΛબ
ίϚϯυϥΠϯGV[[ZpOEFSΛ ѻ͏ࡍʹൃੜ͢Δ
w ߦࢦͰ͋ΔͨΊɺؚΊΒΕΔใྔʹ੍ݶ͕͋Δ w πʔϧʹΈࠐΉࡍͷෳࡶ͞ ίϚϯυϥΠϯGV[[ZpOEFS Λѻ͏ࡍʹൃੜ͢Δ
w ߦࢦͰ͋ΔͨΊɺؚΊΒΕΔใྔʹ੍ݶ͕͋Δ w πʔϧʹΈࠐΉࡍͷෳࡶ͞ ίϚϯυϥΠϯGV[[ZpOEFS Λѻ͏ࡍʹൃੜ͢Δ
None
None
None
w શ͘ಉ͡༰Λද͍ࣔͯ͠Δߦ͕ෳ͋Δͱ͖ɺ ϓϩάϥϜతɺϢʔβతʹͦΕΒΛ۠ผͰ͖ͳ͍ w ใྔΛ૿͢͜ͱͰϢχʔΫʹͰ͖Δ͕ʜ w ͱʹ͔͘ݟͮΒ͍ w ิॿతͳใݕࡧରʹͳΓɺݕࡧਫ਼͕Լ͢Δ ߦࢦͷݶք
w ߦࢦͰ͋ΔͨΊɺؚΊΒΕΔใྔʹ੍ݶ͕͋Δ w πʔϧʹΈࠐΉࡍͷෳࡶ͞ ίϚϯυϥΠϯGV[[ZpOEFS Λѻ͏ࡍʹൃੜ͢Δ
w DEίϚϯυͷ֦ு w ύεͷཤྺΛΠϯλϥΫςΟϒʹબͯ͠Ҡಈ CCSFOIBODE
w J5VOFTΛίϚϯυϥΠϯ͔Βૢ࡞Ͱ͖Δ w J5VOFTͷۂΛΠϯλϥΫςΟϒʹબɺ࠶ੜ LUSJUVOFTDMJ
w ίϚϯυϥΠϯGV[[ZpOEFSͷΠϯετʔϧ w πʔϧʹೝࣝͤ͞ΔͨΊͷઃఆ w ڥมͳͲ πʔϧʹΈࠐΉࡍͷෳࡶ͞
'V[[ZpOEFSΛϥΠϒϥϦ ͱͯ͠ఏڙ͢Δ
w ߦࢦͰ͋ΔͨΊɺؚΊΒΕΔใྔʹ੍ݶ͕͋Δ ‣ ෦తʹঢ়ଶΛ࣋ͭ͜ͱ͕Ͱ͖ɺϓϩάϥϜଆͰॏෳߦ Λ۠ผͰ͖Δ w πʔϧʹΈࠐΉࡍͷෳࡶ͞ ‣ (PʹͷΈґଘ͢ΔͨΊɺͦͦπʔϧͷઃఆ͕ෆཁ 'V[[ZpOEFSBTBMJCSBSZ
LUSHPGV[[ZpOEFS
func Find( slice interface{}, itemFunc func(i int) string, opts ...Option,
) (idx int, err error) LUSHPGV[[ZpOEFS
EFNP
EFNP ίϚϯυϥΠϯGV[[ZpOEFS
func main() { var slice []string s := bufio.NewScanner(os.Stdin) for
s.Scan() { slice = append(slice, s.Text()) } idx, err := fuzzyfinder.Find(slice, func(i int) string { return slice[i] }) if err != nil { fmt.Fprintf(os.Stderr, "failed to find: %s\n", err) os.Exit(1) } fmt.Println(slice[idx]) }
$ (cd $GOPATH/src/github.com/golang/go; git ls-files) | ./cli
EFNP ಉҰ༰ͷߦͷදࣔ
w ϓϩάϥϜࣗॏෳߦͷผ͕Ͱ͖Δ͕ɺ ϢʔβવผͰ͖ͳ͍ w ิॿతͳใΛϓϨϏϡʔΠϯυͰදࣔ ಉҰ༰ͷߦͷදࣔ
func main() { idx, err := fuzzyfinder.FindMulti(songs, func(i int) string
{ return songs[i].Title }, fuzzyfinder.WithPreviewWindow(func(i, w, h int) string { if i == -1 { return "" } return fmt.Sprintf( "Title: %s\nArtist: %s\nAlbum: %s\n", songs[i].Title, songs[i].ArtistName, songs[i].AlbumName) })) if err != nil { fmt.Fprintf(os.Stderr, "failed to find: %s\n", err) os.Exit(1) } for _, i := range idx { fmt.Println(fmt.Sprintf( "%s / %s / %s", songs[i].Title, songs[i].ArtistName, songs[i].AlbumName)) } }
$ ./orange
HPGV[[ZpOEFSͷ࣮
w ೖྗͱީิߦͷϚονϯά w Ϛονͨ͠ߦͷείΞϦϯά 'V[[ZpOEFSΛߏ͢Δཁૉ
w ೖྗlHSQDzΛؚΉߦΛ୳͢ w ۪ʹೋॏϧʔϓճ͚ͩ͢ Ϛονϯά
w ظ͍ͯ͠ΔߦΛ༏ઌతʹදࣔ͢ΔͨΊʹඞཁ w ֤ߦΛιʔτ͢ΔͨΊͷείΞΛࢉग़͢Δ είΞϦϯά
w ϨʔϕϯγϡλΠϯڑ w /FFEMFNBO8VOTDI w 4NJUI8BUFSNBO ৭ʑͳείΞϦϯάΞϧΰϦζϜ
w ϨʔϕϯγϡλΠϯڑεϖϧνΣοΧʔ w /FFEMFNBO8VOTDIG[Z w 4NJUI8BUFSNBOG[G ৭ʑͳείΞϦϯάΞϧΰϦζϜ
w ϨʔϕϯγϡλΠϯڑ w /FFEMFNBO8VOTDI w 4NJUI8BUFSNBO ৭ʑͳείΞϦϯάΞϧΰϦζϜ
w άϩʔόϧ ΞϥΠϯϝϯτΞϧΰϦζϜͷҰͭ w ͋ΔͭͷจࣈྻΛྻͤ͞ΔͨΊʹ ඞཁͳίετΛಈతܭը๏ΛͬͯٻΊΔ /FFEMFNBO8VOTDIΞϧΰϦζϜ
/FFEMFNBO8VOTDIΞϧΰϦζϜ | A T A C ------------------------- | A| C|
w ҎԼͷ͍ͣΕ͔ͷૢ࡞ͷ͏ͪɺ࠷είΞ͕ߴ͍ͷΛબ w ۭന Ϊϟοϓ ΛࠨͷจࣈྻʹҰͭૠೖ w ۭന Ϊϟοϓ Λ্ͷจࣈྻʹҰͭૠೖ
w จࣈͱจࣈͷରԠ͚ ϚονPSϛεϚον /FFEMFNBO8VOTDIΞϧΰϦζϜ
w ҎԼͷ͍ͣΕ͔ͷૢ࡞ͷ͏ͪɺ࠷είΞ͕ߴ͍ͷΛબ w ۭന Ϊϟοϓ ΛࠨͷจࣈྻʹҰͭૠೖ w ۭന Ϊϟοϓ Λ্ͷจࣈྻʹҰͭૠೖ
w จࣈͱจࣈͷରԠ͚ ϚονPSϛεϚον PS /FFEMFNBO8VOTDIΞϧΰϦζϜ
/FFEMFNBO8VOTDIΞϧΰϦζϜ ยํ͕ۭจࣈͷͱ͖ͷ είΞ࠷ॳʹٻ·Δ | A T A C ------------------------- |
0 -2 -4 -6 -8 A| -2 C| -4
/FFEMFNBO8VOTDIΞϧΰϦζϜ e.g. “ATAC” ʹରͯ͠ “” ΛΞϥ Πϯϝϯτ͢Δʹ 4 ͭ
ΪϟοϓΛૠೖ͢Εྑ͍ | A T A C ------------------------- | 0 -2 -4 -6 -8 A| -2 C| -4
/FFEMFNBO8VOTDIΞϧΰϦζϜ “” ͱ “” ʹͦΕͧΕ จࣈΛରԠ͚Δ߹ɺ Ϛον͍ͯ͠ΔͷͰ +2 (0 +
2 = 2) | A T A C ------------------------- | 0 -2 -4 -6 -8 A| -2 C| -4
/FFEMFNBO8VOTDIΞϧΰϦζϜ “A” ͱ “” ͕͋Γɺ ޙऀʹΪϟοϓΛૠೖ ͢ΔͷͰ -2 (-2 -
2 = -4) | A T A C ------------------------- | 0 -2 -4 -6 -8 A| -2 C| -4
/FFEMFNBO8VOTDIΞϧΰϦζϜ “” ͱ “A” ͕͋Γɺ લऀʹΪϟοϓΛૠೖ ͢ΔͷͰ -2 (-2 -
2 = -4) | A T A C ------------------------- | 0 -2 -4 -6 -8 A| -2 C| -4
/FFEMFNBO8VOTDIΞϧΰϦζϜ match = 2 left gap = -4 top gap
= -4 Ͳ͔͜ΒٻΊ͔ͨΛه | A T A C ------------------------- | 0 -2 -4 -6 -8 A| -2 2 C| -4
/FFEMFNBO8VOTDIΞϧΰϦζϜ mismatch = -3 left gap = 0 top gap
= -6 | A T A C ------------------------- | 0 -2 -4 -6 -8 A| -2 2 0 C| -4
/FFEMFNBO8VOTDIΞϧΰϦζϜ match = -2 left gap = -2 top gap
= -8 | A T A C ------------------------- | 0 -2 -4 -6 -8 A| -2 2 0 -2 C| -4
/FFEMFNBO8VOTDIΞϧΰϦζϜ mismatch = -7 left gap = -4 top gap
= -10 | A T A C ------------------------- | 0 -2 -4 -6 -8 A| -2 2 0 -2 -4 C| -4
| A T A C ------------------------- | 0 -2 -4
-6 -8 A| -2 2 0 -2 -4 C| -4 0 1 -1 0 /FFEMFNBO8VOTDIΞϧΰϦζϜ ࠷ऴతͳঢ়ଶ
| A T A C ------------------------- | 0 -2 -4
-6 -8 A| -2 2 0 -2 -4 C| -4 0 1 -1 0 /FFEMFNBO8VOTDIΞϧΰϦζϜ ඌͷείΞ͕ ͜ͷจࣈྻؒͷείΞ είΞ = 0
| A T A C ------------------------- | 0 -2 -4
-6 -8 A| -2 2 0 -2 -4 C| -4 0 1 -1 0 /FFEMFNBO8VOTDIΞϧΰϦζϜ A T A C | | A - - C ඌ͔ΒҹͷॱʹḷΔ
w ϨʔϕϯγϡλΠϯڑ w /FFEMFNBO8VOTDI w 4NJUI8BUFSNBO ৭ʑͳείΞϦϯάΞϧΰϦζϜ
w ϩʔΧϧΞϥΠϯϝϯτΞϧΰϦζϜͷҰͭ w શମతʹࣅ͍ͯͳ͍ͭͷจࣈྻͷ ہॴతͳΞϥΠϯϝϯτΛٻΊΔΞϧΰϦζϜ w /FFEMFNBO8VTDIͱඇৗʹࣅ͍ͯΔ͕ɺ είΞ͕ϚΠφεʹͳΒͳ͍ 4NJUI8BUFSNBOΞϧΰϦζϜ
4NJUI8BUFSNBOΞϧΰϦζϜ w ҎԼͷ͍ͣΕ͔ͷૢ࡞ͷ͏ͪɺ࠷είΞ͕ߴ͍ͷΛબ w ۭന Ϊϟοϓ ΛࠨͷจࣈྻʹҰͭૠೖ w ۭന Ϊϟοϓ
Λ্ͷจࣈྻʹҰͭૠೖ w จࣈͱจࣈͷରԠ͚ ϚονPSϛεϚον w θϩ
| A T A C ------------------------- | 0 0 0
0 0 A| 0 2 0 2 0 C| 0 0 1 0 4 4NJUI8BUFSNBOΞϧΰϦζϜ ඌ͔Βઌ಄Ͱͳ͘ɺ ෦తͳΞϥΠϯϝϯτ (ඌ͔Β 0 ·Ͱ)
| A T A C ------------------------- | 0 0 0
0 0 A| 0 2 0 2 0 C| 0 0 1 0 4 4NJUI8BUFSNBOΞϧΰϦζϜ είΞ = 4
| A T A C ------------------------- | 0 0 0
0 0 A| 0 2 0 2 0 C| 0 0 1 0 4 4NJUI8BUFSNBOΞϧΰϦζϜ A T A C | | - - A C
w ΪϟοϓΛ࡞Δ͜ͱࣗମͷϖφϧςΟ w ઌ಄ҰகϘʔφε w FUD ϘʔφεͱϖφϧςΟ
w ઃܭͦΕͧΕͷ࣮ʹΑΔ w G[ZKIBXUIPSOG[Z"-(03*5).NE w G[GKVOFHVOOG[GTSDBMHPBMHPHP ϘʔφεͱϖφϧςΟ
·ͱΊ
ೖྗʹϚον͢ΔߦΛߜΓࠐΉ 4NJUI8BUFSNBOͰ֤ߦΛείΞϦϯά είΞ͕ߴ͍ͷ͔Βॱʹදࣔ HPGV[[ZpOEFSͷ࣮
w ॏෳߦͷ۠ผ w ϓϨϏϡʔΠϯυͰͷิॿతͳใͷ༩ w πʔϧ͔ΒGV[[ZpOEFSΛͭ͘Δࡍʹɺ ίϚϯυϥΠϯGV[[ZpOEFSͷґଘΛղফͰ ͖Δ HPGV[[ZpOEFSͷղܾ͢Δ͜ͱ
5IBOLTGPSMJTUFOJOH