Fuzzy finder as a Go library

BU(P$POGFSFODF4QSJOH Fuzzy finder as a  Go library

XIPBNJ w LUS Ωλϩʔɺ!LUS@ w ৽ଔ w (Pͱ$-*πʔϧ͕͖͢

'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 ৘ใྔΛ૿΍͢͜ͱͰϢχʔΫʹ͸Ͱ͖Δ͕ʜ 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 ίϚϯυϥΠϯ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ΞϧΰϦζϜ

/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

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

Fuzzy finder as a Go library

Fuzzy finder as a Go library

More Decks by ktr

Other Decks in Programming

Featured

Transcript