GNU bug report logs - #70077
An easier way to track buffer changes

Previous Next

Full log

View this message in rfc822 format

From: Ihor Radchenko <yantar92 <at> posteo.net>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: casouri <at> gmail.com, 70077 <at> debbugs.gnu.org, qhong <at> alum.mit.edu, frederic.bour <at> lakaban.net, joaotavora <at> gmail.com, mail <at> nicolasgoaziou.fr, acm <at> muc.de, Eli Zaretskii <eliz <at> gnu.org>, stephen_leake <at> stephe-leake.org, alan.zimm <at> gmail.com, phillip.lord <at> russet.org.uk
Subject: bug#70077: An easier way to track buffer changes
Date: Thu, 04 Apr 2024 17:58:43 +0000

Stefan Monnier <monnier <at> iro.umontreal.ca> writes:

>> I am not 100% where the O(N^2) is coming from.
>
> If you add N times 1 char to an (initially empty) string, the total cost
> of constructing the resulting N-char string is O(N²).

I guess that another approach is not concatenating the strings and
instead accumulating them into a list (or two lists - before/after).
That will get rid of logN multiplier :)

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.