[TUHS] termcap vs terminfo

[crossd@gmail.com (Dan Cross)]

On Tue, Jan 6, 2015 at 11:51 AM, Johnny Billquist <bqt at update.uu.se> wrote:

> On 2015-01-06 17:32, Mary Ann Horton<mah at mhorton.net> wrote:
>
>> 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.


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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20150106/113d08c2/attachment.html>