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

[Heime <heimeborgia@protonmail.com>]

On Saturday, April 20th, 2024 at 1:52 PM, Stefan Monnier via Users list for the GNU Emacs text editor <help-gnu-emacs@gnu.org> wrote:

> > > > (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

How would the implementation be like exactly ?