6 Jan
2015
6 Jan
'15
10:56 p.m.
On Tue, Jan 6, 2015 at 11:51 AM, Johnny Billquist <bqt(a)update.uu.se> wrote:
On 2015-01-06 17:32, Mary Ann
Horton<mah(a)mhorton.net> wrote:
I believe that Mary Ann is referring to repeatedly looking up (presumably
different) elements in the entry. Assuming that e.g. `vi` looks up O(n)
elements, where $n$ is the number of elements, doing a linear scan for
each, you'd end up with quadratic behavior.
Hashing, or storing in some kind of balanced-tree like structure or
something, would of course help but would also necessitate doing a copy and
would entail some additional memory inefficiency.
- Dan C.
Even with TERMCAP in the environment,
there's still that quadratic
algorithm every time vi starts up.
I must be stupid or something. What quadratic algorithm?
vi gets the "correct" terminal database entry directly from the
environment. Admittedly, getting any variable out of the environment means
a linear search of the environment, but that's about it.
What am I missing? And once you have that, any operation still means
either searching through the terminal definition for the right function,
which in itself is also linear, unless you hash that up in your program.
But I fail to see where the quadratic behavior comes in.