Re: [External] : Use of an associated list with completing-read

[Stefan Monnier via Users list for the GNU Emacs text editor <help-gnu-emacs@gnu.org>]

>> >     (setq-local tema-lugar
>> >                 (append tema--lugar (list (cons lnum strg))))
>> 
>> This is the classic recipe for poor scaling performance since the above
>> operation takes time proportional to the length of the list, so if you
>> execute this N times (in a loop), the loop builds a list of length N
>> but takes time N² to do it.  When N is small, noone notices, and as it gets
>> large the performance starts to suck.
>
> Heime:
>
> One programming cliche for this is to
> (1) start with a list that you create
> (e.g., a let-binding to nil), so you
> don't modify any existing list that
> you might not want to mess with, (2)
> use `nconc' instead of `append', to
> append quickly (the _list structure_
> is modified - destructive), (3) being
> sure to set your list variable to the
> result of each modification.

While this is slightly better because it avoid the O(N²) memory
allocation, it's still O(N²) operations.

> An even more common cliche for doing
> the same thing is to do #1, then (2)
> cons instead of append, and (3) when
> finished adding list elements, do an
> `nreverse' of the list you created.
> That too is a destructive operation.

That's the usual solution, with the desired linear
(i.e. optimal) complexity, indeed.


        Stefan