On Wed, Jan 25, 2006 at 08:33:56PM -0500, Eric M. Ludlam wrote:
> >>> "Toby 'qubit' Cubitt" <toby-dated-1138652795.b55a62@...> seems to think that:
> [ ... ]
> >I probably should have mentioned the reason I'm obsessed with
> >completion speed isn't just for the sake of it. It's because my
> >package continuously looks up possible completions as you type, and
> >can even provisionally insert the most likely one (based on the usage
> >frequency it's learnt as it goes along) into the buffer. Completion is
> >"switched on" all the time. Even a few tenths of a second delay gets
> >in the way of typing, hence the fancy data structures.
> Hmmm. Sounds like a job for the profiler.
Yup! I've used it extensively. And it told me that large dictionaries
simply kill completion speed when you use an O(n) algorithm or data
structure (e.g. a list). It's even worse if you want to return just
the top 10 completions by frequency and you use the simplest sort and
My data structures were originally pure ternary search trees, but that
still proved slightly too slow for completing short prefices from the
large English dictionary, and the profiler told me code optimisation
and tweaking was unlikely to solve it. That's when I added a caching
layer using hash tables (good speed but very bad memory scaling, but
very little ends up needing to be cached so it works well).
Useful package, elp! Wish it did full profiling instead of just
Of course, these speed considerations might not be an issue for the
smaller lists of symbols there'll be to complete from in a programming
mode. But since I have the code for these fancy structures, along with
the code for learning word frequencies as you type (the more important
feature), programming modes might as well benefit from them.
> Good Luck
Thanks. I'll let you know how I get on.
Quantum Information Theory group
Max Planck Institute for Quantum Optics