From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: David Kastrup Newsgroups: gmane.emacs.devel Subject: Re: (n)reverse vs. length Date: Thu, 15 May 2014 07:49:35 +0200 Message-ID: <8761l7sia8.fsf@fencepost.gnu.org> References: <53737B79.7020704@yandex.ru> <87r43wrufz.fsf@fencepost.gnu.org> <5374429A.3090704@yandex.ru> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1400133028 1736 80.91.229.3 (15 May 2014 05:50:28 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 15 May 2014 05:50:28 +0000 (UTC) Cc: Stefan Monnier , emacs-devel@gnu.org To: Dmitry Antipov Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Thu May 15 07:50:23 2014 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1WkoYe-00063m-VQ for ged-emacs-devel@m.gmane.org; Thu, 15 May 2014 07:50:21 +0200 Original-Received: from localhost ([::1]:55746 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WkoYe-0004Du-Al for ged-emacs-devel@m.gmane.org; Thu, 15 May 2014 01:50:20 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:51573) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WkoYa-0004Dn-Gd for emacs-devel@gnu.org; Thu, 15 May 2014 01:50:17 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WkoYZ-0004ot-5q for emacs-devel@gnu.org; Thu, 15 May 2014 01:50:16 -0400 Original-Received: from fencepost.gnu.org ([2001:4830:134:3::e]:55675) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WkoYZ-0004od-2b for emacs-devel@gnu.org; Thu, 15 May 2014 01:50:15 -0400 Original-Received: from localhost ([127.0.0.1]:34618 helo=lola) by fencepost.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WkoYY-0006ux-D8; Thu, 15 May 2014 01:50:14 -0400 Original-Received: by lola (Postfix, from userid 1000) id EB207E0BD9; Thu, 15 May 2014 07:49:35 +0200 (CEST) In-Reply-To: <5374429A.3090704@yandex.ru> (Dmitry Antipov's message of "Thu, 15 May 2014 08:29:14 +0400") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.4.50 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2001:4830:134:3::e X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:171847 Archived-At: Dmitry Antipov 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