Fuzzy finder as a Go library

Go Conference 2019 Spring

Transcript

1. BU
   (P
   $POGFSFODF
   
   4QSJOH Fuzzy finder as a
 Go library
2. 
   XIPBNJ w LUS
   Ωλϩʔɺ!LUS@
   w 
   ৽ଔ
   w (P
   ͱ
   $-*
   πʔϧ͕͖͢
4. 'V[[Z
   pOEFS
   JT
   Կ
5. w
   ೖྗʹର͠ɺ͍͋·͍ݕࡧ

   ʹΑͬͯΠϯλϥΫςΟϒʹ

   ಛఆͷߦΛબ୒Ͱ͖Δ
   w
   ίϚϯυϥΠϯ
   GV[[Z
   pOEFS

   G[G
   G[Z
   FUD 'V[[Z
   pOEFS
6. $ cd `ghq root`/`ghq list | fzf` HIR
   ഑ԼͷϦϙδτϦʹҠಈ
7. $ git branch | egrep -v '^\*' | fzf | 
 xargs git checkout ΠϯλϥΫςΟϒʹνΣοΫΞ΢τઌ
 ϒϥϯνΛબ୒
8. ίϚϯυϥΠϯ
   GV[[Z
   pOEFS
   Λ
 ѻ͏ࡍʹൃੜ͢Δ໰୊
9. w ߦࢦ޲Ͱ͋ΔͨΊɺؚΊΒΕΔ৘ใྔʹ੍ݶ͕͋Δ
   w πʔϧʹ૊ΈࠐΉࡍͷෳࡶ͞ ίϚϯυϥΠϯ
   GV[[Z
   pOEFS
   
 Λѻ͏ࡍʹൃੜ͢Δ໰୊
   
10. w ߦࢦ޲Ͱ͋ΔͨΊɺؚΊΒΕΔ৘ใྔʹ੍ݶ͕͋Δ
    w πʔϧʹ૊ΈࠐΉࡍͷෳࡶ͞ ίϚϯυϥΠϯ
    GV[[Z
    pOEFS
    
 Λѻ͏ࡍʹൃੜ͢Δ໰୊
    
14. w શ͘ಉ͡಺༰Λද͍ࣔͯ͠Δߦ͕ෳ਺͋Δͱ͖ɺ
 ϓϩάϥϜతɺϢʔβతʹ΋ͦΕΒΛ۠ผͰ͖ͳ͍
    w ৘ใྔΛ૿΍͢͜ͱͰϢχʔΫʹ͸Ͱ͖Δ͕ʜ
    w ͱʹ͔͘ݟͮΒ͍
    w ิॿతͳ৘ใ΋ݕࡧର৅ʹͳΓɺݕࡧਫ਼౓͕௿Լ͢Δ ߦࢦ޲ͷݶք
15. w ߦࢦ޲Ͱ͋ΔͨΊɺؚΊΒΕΔ৘ใྔʹ੍ݶ͕͋Δ
    w πʔϧʹ૊ΈࠐΉࡍͷෳࡶ͞ ίϚϯυϥΠϯ
    GV[[Z
    pOEFS
    
 Λѻ͏ࡍʹൃੜ͢Δ໰୊
    
16. w DE
    ίϚϯυͷ֦ு
    w ύεͷཤྺΛΠϯλϥΫςΟϒʹબ୒ͯ͠Ҡಈ CCSFOIBODE
17. w J5VOFT
    ΛίϚϯυϥΠϯ͔Βૢ࡞Ͱ͖Δ
    w J5VOFT
    ͷۂΛΠϯλϥΫςΟϒʹબ୒ɺ࠶ੜ LUSJUVOFTDMJ
18. w ίϚϯυϥΠϯ
    GV[[Z
    pOEFS
    ͷΠϯετʔϧ
    w πʔϧʹೝࣝͤ͞ΔͨΊͷઃఆ
    w ؀ڥม਺ͳͲ πʔϧʹ૊ΈࠐΉࡍͷෳࡶ͞
19. 'V[[Z
    pOEFS
    ΛϥΠϒϥϦ
 ͱͯ͠ఏڙ͢Δ
20. w ߦࢦ޲Ͱ͋ΔͨΊɺؚΊΒΕΔ৘ใྔʹ੍ݶ͕͋Δ
    ‣ ಺෦తʹঢ়ଶΛ࣋ͭ͜ͱ͕Ͱ͖ɺϓϩάϥϜଆͰॏෳߦ Λ۠ผͰ͖Δ
    w πʔϧʹ૊ΈࠐΉࡍͷෳࡶ͞
    ‣ (P
    ʹͷΈґଘ͢ΔͨΊɺͦ΋ͦ΋πʔϧͷઃఆ͕ෆཁ 'V[[Z
    pOEFS
    BT
    B
    MJCSBSZ
21. LUSHPGV[[ZpOEFS
22. func Find( slice interface{}, itemFunc func(i int) string, opts ...Option, ) (idx int, err error) LUSHPGV[[ZpOEFS
23. EFNP
24. EFNP
    ίϚϯυϥΠϯ
    GV[[Z
    pOEFS
25. 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]) }
26. $ (cd $GOPATH/src/github.com/golang/go; git ls-files) | ./cli
27. EFNP
    ಉҰ಺༰ͷߦͷදࣔ
28. w ϓϩάϥϜࣗ਎͸ॏෳߦͷ൑ผ͕Ͱ͖Δ͕ɺ
 Ϣʔβ͸౰વ൑ผͰ͖ͳ͍
    w ิॿతͳ৘ใΛϓϨϏϡʔ΢Πϯυ΢Ͱදࣔ ಉҰ಺༰ͷߦͷදࣔ
29. 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)) } }
30. $ ./orange
31. HPGV[[ZpOEFS
    ͷ࣮૷
32. w ೖྗͱީิߦͷϚονϯά
    w Ϛονͨ͠ߦͷείΞϦϯά 'V[[Z
    pOEFS
    Λߏ੒͢Δཁૉ
33. w ೖྗ
    lHSQDz
    ΛؚΉߦΛ୳͢
    w ۪௚ʹೋॏϧʔϓճ͚ͩ͢ Ϛονϯά
34. w ظ଴͍ͯ͠ΔߦΛ༏ઌతʹදࣔ͢ΔͨΊʹඞཁ
    w ֤ߦΛιʔτ͢ΔͨΊͷείΞΛࢉग़͢Δ είΞϦϯά
35. w ϨʔϕϯγϡλΠϯڑ཭
    w /FFEMFNBO8VOTDI
    w 4NJUI8BUFSNBO ৭ʑͳείΞϦϯάΞϧΰϦζϜ
36. w ϨʔϕϯγϡλΠϯڑ཭
    
    εϖϧνΣοΧʔ
    w /FFEMFNBO8VOTDI
    
    G[Z
    w 4NJUI8BUFSNBO
    
    G[G ৭ʑͳείΞϦϯάΞϧΰϦζϜ
37. w ϨʔϕϯγϡλΠϯڑ཭
    w /FFEMFNBO8VOTDI
    w 4NJUI8BUFSNBO ৭ʑͳείΞϦϯάΞϧΰϦζϜ
38. w άϩʔόϧ
    ΞϥΠϯϝϯτΞϧΰϦζϜͷҰͭ
    w ͋Δ
    
    ͭͷจࣈྻΛ੔ྻͤ͞ΔͨΊʹ
 ඞཁͳίετΛಈతܭը๏Λ࢖ͬͯٻΊΔ /FFEMFNBO8VOTDI
    ΞϧΰϦζϜ
39. /FFEMFNBO8VOTDI
    ΞϧΰϦζϜ | A T A C ------------------------- | A| C|
40. w ҎԼͷ͍ͣΕ͔ͷૢ࡞ͷ͏ͪɺ࠷΋είΞ͕ߴ͍΋ͷΛબ୒
    w ۭന
    Ϊϟοϓ
    ΛࠨͷจࣈྻʹҰͭૠೖ
    w ۭന
    Ϊϟοϓ
    Λ্ͷจࣈྻʹҰͭૠೖ
    
    w จࣈͱจࣈͷରԠ෇͚
    Ϛον
    PS
    ϛεϚον /FFEMFNBO8VOTDI
    ΞϧΰϦζϜ
41. w ҎԼͷ͍ͣΕ͔ͷૢ࡞ͷ͏ͪɺ࠷΋είΞ͕ߴ͍΋ͷΛબ୒
    w ۭന
    Ϊϟοϓ
    ΛࠨͷจࣈྻʹҰͭૠೖ
    
    
    w ۭന
    Ϊϟοϓ
    Λ্ͷจࣈྻʹҰͭૠೖ
    
    
    w จࣈͱจࣈͷରԠ෇͚
    Ϛον
    PS
    ϛεϚον
    
    
    PS
     /FFEMFNBO8VOTDI
    ΞϧΰϦζϜ
42. /FFEMFNBO8VOTDI
    ΞϧΰϦζϜ ยํ͕ۭจࣈͷͱ͖ͷ
 είΞ͸࠷ॳʹٻ·Δ | A T A C ------------------------- | 0 -2 -4 -6 -8 A| -2 C| -4
43. /FFEMFNBO8VOTDI
    ΞϧΰϦζϜ e.g.
 
 “ATAC” ʹରͯ͠ “” ΛΞϥ Πϯϝϯτ͢Δʹ͸ 4 ͭ ΪϟοϓΛૠೖ͢Ε͹ྑ͍ | A T A C ------------------------- | 0 -2 -4 -6 -8 A| -2 C| -4
44. /FFEMFNBO8VOTDI
    ΞϧΰϦζϜ “” ͱ “” ʹͦΕͧΕ จࣈΛରԠ෇͚Δ৔߹ɺ Ϛον͍ͯ͠ΔͷͰ +2
 (0 + 2 = 2) | A T A C ------------------------- | 0 -2 -4 -6 -8 A| -2 C| -4
45. /FFEMFNBO8VOTDI
    ΞϧΰϦζϜ “A” ͱ “” ͕͋Γɺ
 ޙऀʹΪϟοϓΛૠೖ
 ͢ΔͷͰ -2 (-2 - 2 = -4) | A T A C ------------------------- | 0 -2 -4 -6 -8 A| -2 C| -4
46. /FFEMFNBO8VOTDI
    ΞϧΰϦζϜ “” ͱ “A” ͕͋Γɺ
 લऀʹΪϟοϓΛૠೖ
 ͢ΔͷͰ -2
 (-2 - 2 = -4) | A T A C ------------------------- | 0 -2 -4 -6 -8 A| -2 C| -4
47. /FFEMFNBO8VOTDI
    ΞϧΰϦζϜ match = 2 left gap = -4 top gap = -4
 
 Ͳ͔͜ΒٻΊ͔ͨΛه࿥ | A T A C ------------------------- | 0 -2 -4 -6 -8 A| -2 2 C| -4
48. /FFEMFNBO8VOTDI
    ΞϧΰϦζϜ mismatch = -3 left gap = 0 top gap = -6 | A T A C ------------------------- | 0 -2 -4 -6 -8 A| -2 2 0 C| -4
49. /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
50. /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
51. | A T A C ------------------------- | 0 -2 -4 -6 -8 A| -2 2 0 -2 -4 C| -4 0 1 -1 0 /FFEMFNBO8VOTDI
    ΞϧΰϦζϜ ࠷ऴతͳঢ়ଶ
52. | A T A C ------------------------- | 0 -2 -4 -6 -8 A| -2 2 0 -2 -4 C| -4 0 1 -1 0 /FFEMFNBO8VOTDI
    ΞϧΰϦζϜ ຤ඌͷείΞ͕
 ͜ͷจࣈྻؒͷείΞ 
 είΞ = 0
53. | 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 ຤ඌ͔Β໼ҹͷॱʹḷΔ
54. w ϨʔϕϯγϡλΠϯڑ཭
    w /FFEMFNBO8VOTDI
    w 4NJUI8BUFSNBO ৭ʑͳείΞϦϯάΞϧΰϦζϜ
55. w ϩʔΧϧΞϥΠϯϝϯτΞϧΰϦζϜͷҰͭ
    w શମతʹ͸ࣅ͍ͯͳ͍
    
    ͭͷจࣈྻͷ
 ہॴతͳΞϥΠϯϝϯτΛٻΊΔΞϧΰϦζϜ
    w /FFEMFNBO8VTDI
    ͱඇৗʹࣅ͍ͯΔ͕ɺ
 είΞ͕ϚΠφεʹͳΒͳ͍ 4NJUI8BUFSNBO
    ΞϧΰϦζϜ
56. 4NJUI8BUFSNBO
    ΞϧΰϦζϜ w ҎԼͷ͍ͣΕ͔ͷૢ࡞ͷ͏ͪɺ࠷΋είΞ͕ߴ͍΋ͷΛબ୒
    w ۭന
    Ϊϟοϓ
    ΛࠨͷจࣈྻʹҰͭૠೖ
    w ۭന
    Ϊϟοϓ
    Λ্ͷจࣈྻʹҰͭૠೖ
    
    w จࣈͱจࣈͷରԠ෇͚
    Ϛον
    PS
    ϛεϚον
    w θϩ஋
57. | A T A C ------------------------- | 0 0 0 0 0 A| 0 2 0 2 0 C| 0 0 1 0 4 4NJUI8BUFSNBO
    ΞϧΰϦζϜ ຤ඌ͔Βઌ಄Ͱ͸ͳ͘ɺ ෦෼తͳΞϥΠϯϝϯτ (຤ඌ͔Β 0 ·Ͱ)
58. | A T A C ------------------------- | 0 0 0 0 0 A| 0 2 0 2 0 C| 0 0 1 0 4 4NJUI8BUFSNBO
    ΞϧΰϦζϜ είΞ = 4
59. | 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
60. w ΪϟοϓΛ࡞Δ͜ͱࣗମ΁ͷϖφϧςΟ
    w ઌ಄ҰகϘʔφε
    w FUD ϘʔφεͱϖφϧςΟ
61. w ઃܭ͸ͦΕͧΕͷ࣮૷ʹΑΔ
    w G[Z
    
    KIBXUIPSOG[Z"-(03*5).NE
    w G[G
    
    KVOFHVOOG[GTSDBMHPBMHPHP ϘʔφεͱϖφϧςΟ
62. ·ͱΊ
63.  ೖྗʹϚον͢ΔߦΛߜΓࠐΉ
     4NJUI8BUFSNBO
    Ͱ֤ߦΛείΞϦϯά
     είΞ͕ߴ͍΋ͷ͔Βॱʹදࣔ HPGV[[ZpOEFS
    ͷ࣮૷
64. w ॏෳߦͷ۠ผ
    w ϓϨϏϡʔ΢Πϯυ΢Ͱͷิॿతͳ৘ใͷ෇༩
    w πʔϧ͔Β
    GV[[Z
    pOEFS
    Λͭ͘Δࡍʹɺ
 ίϚϯυϥΠϯ
    GV[[Z
    pOEFS
    ΁ͷґଘΛղফͰ ͖Δ HPGV[[ZpOEFS
    ͷղܾ͢Δ͜ͱ
65. 5IBOLT
    GPS
    MJTUFOJOH