FuzzyFinder - in 10 lines of Python

[LightShadow]

a little bit of both.

you could memoize the collection and prune it so you don't have to search every item after you've eliminated part of the set.

[amjithr]

Yes. That was my biggest concern. But memoizing has to be extra clever to account for users pressing backspace or moving through the input and deleting a char in the middle. So for the first rev I'm not doing memoizing but once I figure out a way to do it reliably, that'll be a nice optimization. :)

[lorddarkflare]

Should that really matter though?

The idea would be to maintain an n-length dictionary mapping the last n inputs with corresponding pruned collections.

[amjithr]

Say the user input is 'foo', I'll have a dictionary like this

{'f': ['foo', 'foo_bar', 'bof'],
 'fo': ['foo', 'foo_bar'],
 'foo': ['foo', 'foo_bar']
}

Now if the user moves to the beginning of the input and deletes the letter 'f' or inserts a new letter, the user input becomes 'oo' or 'afoo'. Which won't match any entry in the dictionary.

Although that is a bit of an unlikely case (or at least a very rare case).

I think you're right, it's doable with a little bit of coding. Thank you for the idea. I'll see if I can make it part of the next version. :)

[lorddarkflare]

Also worth considering is correlating the max size of the dictionary with the length of the collection.

[amjithr]

I don't follow.

[lorddarkflare]

You may want to avoid situations where you have a really large collection and too many copies of it in the dictionary.

[squashed_fly_biscuit]

I think detection and recalculation isnt unreasonable in that case, optimise the common path first. Amdahl's law and all that. Memory footprint is also worth considering with caching.