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
5.6k
Fuzzy finder as a Go library
Go Conference 2019 Spring
ktr
May 18, 2019
Tweet
Share
More Decks by ktr
See All by ktr
Monorepo における Go テストの差分実行 / Running Differential Go Tests in a Monorepo
ktr_0731
0
39
Designing libraries in Go way
ktr_0731
6
1.5k
Go Modules and Proxy Walkthrough
ktr_0731
8
26k
ソフトウェアの複雑さに立ち向かう技術 / Tackling software complexity
ktr_0731
0
170
つよくてニューゲーム / NewGame++
ktr_0731
0
920
やはり俺の Go アプリケーション設計はまちがっている。 / My Go Application Design Is Wrong, As I Expected
ktr_0731
13
3.5k
GopherCon2018
ktr_0731
2
1.7k
Evans: more expressive gRPC client
ktr_0731
2
440
自作 CLI ツールのワークフローとそれを支える技術 / the workflow of my CLI tool and technologies which supports it
ktr_0731
0
1.7k
Other Decks in Programming
See All in Programming
rbs-inlineを導入してYARDからRBSに移行する
euglena1215
1
270
What is Parser
yui_knk
9
4.1k
今インフラ技術をイチから学び直すなら
yuhta28
1
130
ECMAScript、Web標準の型はどう管理されているか / How ECMAScript and Web standards types are maintained
petamoriken
3
390
僕が思い描くTypeScriptの未来を勝手に先取りする
yukukotani
9
2.4k
watsonx.ai Dojo #2 生成AIを使ったアプリ開発入門編
oniak3ibm
PRO
0
110
月間4.5億回再生を超える大規模サービス TVer iOSアプリのリアーキテクチャ戦略 - iOSDC2024
techtver
PRO
1
930
Modular Monolith Go Server with GraphQL Federation + gRPC
110y
1
580
Jakarta EE meets AI
ivargrimstad
1
480
Crafting Cross-Platform Adventures: Building a Game Engine with Kotlin Multiplatform
dwursteisen
0
100
Our Websites Need a Lifestyle Change, Not a Diet
ryantownsend
0
140
状態管理ライブラリZustandの導入から運用まで
k1tikurisu
3
470
Featured
See All Featured
How STYLIGHT went responsive
nonsquared
93
5.1k
Fashionably flexible responsive web design (full day workshop)
malarkey
401
65k
A Philosophy of Restraint
colly
202
16k
From Idea to $5000 a Month in 5 Months
shpigford
379
46k
Building an army of robots
kneath
302
42k
Git: the NoSQL Database
bkeepers
PRO
425
64k
Navigating Team Friction
lara
183
13k
Infographics Made Easy
chrislema
239
18k
Optimising Largest Contentful Paint
csswizardry
30
2.8k
Designing Experiences People Love
moore
138
23k
What's in a price? How to price your products and services
michaelherold
242
11k
Robots, Beer and Maslow
schacon
PRO
157
8.2k
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