Re: (n)reverse vs. length

[David Kastrup]

Dmitry Antipov <address@hidden> writes:

> On 05/15/2014 05:45 AM, Stefan Monnier wrote:
>
>>>> strings should be immutable
>>> Doesn't aset work on strings?
>>
>> Yes, I said "should be" not "are".
>
> Hm, what about an existing code which relies on aset'table strings? Questions
> like http://lists.gnu.org/archive/html/emacs-devel/2014-04/msg00378.html shows
> that treating string as an array of characters is a common practice (which is
> "natural" for the people with C background). And, in case of large strings,
> in-place reverse may save a lot of memory.

I am not sure there is a use case for in-place reverse of strings.  If
there is, the algorithm for multibyte characters would definitely
warrant writing in C as it is quite non-trivial.  Two characters of
buffer should suffice: just copy one character from each end to its
respective buffer, and then repeat copying and refilling the respective
one of the two buffers which has enough space to fit in the original
string.  Doing it in C would be O(n), doing it with aset instead would
be O(n^2).

-- 
David Kastrup