If you are porting might be good to look into comparing and porting other libraries. Would be also good to trying in real big projects such as chromium.
https://github.com/wincent/command-t - C (actual search algorithm is in C) https://github.com/jhawthorn/fzy - C https://github.com/lotabout/skim - Rust ( https://github.com/lotabout/fuzzy-matcher) https://github.com/JazzCore/ctrlp-cmatcher/blob/master/autoload/fuzzycomt.c - C https://github.com/garybernhardt/selecta Most of these are multi threaded so they are extremely fast. If really want multithreading could write to file and then have another thread look at it. I briefly mentioned this at https://github.com/mattn/gof/issues/18 On Monday, October 5, 2020 at 1:41:02 PM UTC-7 vim-dev ML wrote: > Hi, > > On Sun, Oct 4, 2020 at 7:10 PM lacygoill <[email protected]> wrote: > > > If you have any comments about the function arguments and the return > > values, please let me know. We cannot change this after some time. > > > > I haven't had the time to read all the comments, but I'm using > > matchfuzzypos(), and I had difficulties using its output for what I > > wanted. I'm trying to implement a generic fuzzy search plugin. For now, I > > just wrote a command to fuzzy search through Vim's help tags.I get the > help > > tags via a grep(1) > > < > https://github.com/lacygoill/vim-fuzzy/blob/ef8173581e2dfc7ee2b7a04d87815a07927630e9/autoload/fuzzy.vim#L239-L245 > > > > command, which is formatted by a perl(1) > > < > https://github.com/lacygoill/vim-fuzzy/blob/ef8173581e2dfc7ee2b7a04d87815a07927630e9/autoload/fuzzy.vim#L228 > > > > (or awk(1)) command. Both are started asynchronously via a job. I use > > perl so that an output line of grep(1) such as this one: > > > > /home/user/.fzf/doc/tags:fzf-toc fzf.txt /*fzf-toc* > > > > Is transformed into: > > > > fzf-toc fzf.txt > > > > Between the name of the tag and the name of the file where the tag is, > > there is some whitespace including a tab. I rely on this tab to ignore > the > > name of the file when fuzzy searching through the tags. I only want to > see > > the names of the files to get some extra info. > > > > Here is how I do it > > < > https://github.com/lacygoill/vim-fuzzy/blob/ef8173581e2dfc7ee2b7a04d87815a07927630e9/autoload/fuzzy.vim#L394-L434 > > > > : > > > > var str = substitute(filter_text, '\s*', '', 'g') > > var pos: list<list<number>> > > var matchfuzzypos: list<list<any>> = matchfuzzypos(TAGLIST, str) > > [taglist_filtered, pos] = matchfuzzypos > > map(taglist_filtered, {i, v -> [v] + pos[i]}) > > filter(taglist_filtered, {_, v -> v[-1] < match(v[0], "\t")}) > > pos = copy(taglist_filtered)->map({_, v -> v[1:]}) > > map(taglist_filtered, {_, v -> v[0]}) > > > > I would like to simplify this code by passing the output of > > matchfuzzypos() directly to filter() so that it removes the entries where > > a match is located after the tab. But I can't do it, because if filter() > > removes one tag name from taglist_filtered, the next time pos[i] is > > evaluated, it will no longer apply to the right item. IOW, I need to > filter > > both lists returned by matchfuzzypos() simultaneously. The only way I > > found to do that is to temporarily merge the lists into a single one. It > > works but I think it would be easier and more efficient if > matchfuzzypos() > > returned a single list. Maybe a list of dictionaries: > > > > :echo matchfuzzypos(['clay', 'lacy'], 'la') > > [{'match': 'lacy', 'pos': [0, 1]}, {'match': 'clay', 'pos': [1, 2]}] > > > > > The previous implementation of matchfuzzypos() returned the match position > along with > the matched text. But Prabir commented that it will make it easier for > plugins if all the > matched stings are returned in a single List. It is a trade-off between > these two > approaches. I am not sure which one will be more useful for the plugins: > > 1. Returning a list with all the matched strings and another list with the > matching > positions (current implementation). > 2. Return a single list where each item contains both the matched string > and the > matching position. > > Or a list of lists: > > > > :echo matchfuzzypos(['clay', 'lacy'], 'la') > > [['lacy', 0, 1], ['clay', 1, 2]] > > > > This way, we wouldn't need to temporarily merge the lists, then split > them > > back later. I'm a bit concerned by the impact it can have on performance, > > especially when the operation is repeated frequently (e.g. every keypress > > when a popup menu is visible), and the source of strings is big. > > ------------------------------ > > > > There is something else which I think would be useful but it's more a > > feature request. If you use fzf(1) to search through help tags via > > :Helptags > > < > https://github.com/junegunn/fzf.vim/blob/0fe8e198a3a501b54dbc4f9587526c097599f95a/plugin/fzf.vim#L66 > >, > > you should notice that we can use spaces between tokens. And when you do, > > fzf(1) does 2 interesting things: > > > > - it ignores whitespace > > - it looks for the tokens in no particular order > > > > So if you look for the help tag function-search-undo but only remember > > that there was fun and undo somewhere in the name, and if you type the > > tokens in the wrong order (i.e. undo before fun), fzf(1) will still find > > the tag. That's not the case with matchfuzzypos(). It does not ignore > > whitespace; but this can be easily fixed with a substitute(). However, > > then the issue is to make it look for the tokens in all possible orders. > I > > don't know how fzf(1) does it. And I don't know what would be the impact > > on performance; especially since the bigger the number of > > whitespace-separated tokens, the bigger the number of possible > > permutations. Could this feature be one day implemented and maybe enabled > > via an optional dictionary (similar to the final {dict} argument of > > matchadd())? > > > > If that's not possible, it's not a big issue. I'll just write a recursive > > function which computes all possible permutations of tokens (but only > for a > > small number, 3, 4 or 5), run matchfuzzypos() on each permutation via a > > map(), and merge the results via reduce(). > > > > > > The current fuzzy matching algorithm can be turned to ignore whitespaces. > > BTW, it is also possible to port the fuzzy matching algorithm used by FZF: > https://github.com/junegunn/fzf/blob/master/src/algo/algo.go > > Regards, > Yegappan > > — > You are receiving this because you are subscribed to this thread. > > Reply to this email directly, view it on GitHub > <https://github.com/vim/vim/pull/6932#issuecomment-703876416>, or > unsubscribe > <https://github.com/notifications/unsubscribe-auth/ACY5DGGDVCBBLY5XBTNZEUTSJIVNPANCNFSM4RGT5TOA> > . > -- -- You received this message from the "vim_dev" maillist. Do not top-post! Type your reply below the text you are replying to. For more information, visit http://www.vim.org/maillist.php --- You received this message because you are subscribed to the Google Groups "vim_dev" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/vim_dev/e9ebf95f-2748-46fb-a2c2-710992c07297n%40googlegroups.com.
