From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Andy Wingo Newsgroups: gmane.lisp.guile.devel Subject: Re: efficient implementation of string-replace-substring / string-replace-all Date: Sun, 23 Mar 2014 21:48:45 +0100 Message-ID: <87a9cgsksy.fsf@pobox.com> References: <87y570pzbm.wl%arne_bab@web.de> <87wqmkjyqr.fsf@tines.lan> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1395607736 1768 80.91.229.3 (23 Mar 2014 20:48:56 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 23 Mar 2014 20:48:56 +0000 (UTC) Cc: arne_bab@web.de, guile-devel@gnu.org To: Mark H Weaver Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Sun Mar 23 21:49:06 2014 Return-path: Envelope-to: guile-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 1WRpKL-0002iY-N5 for guile-devel@m.gmane.org; Sun, 23 Mar 2014 21:49:05 +0100 Original-Received: from localhost ([::1]:33393 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WRpKL-00058z-6B for guile-devel@m.gmane.org; Sun, 23 Mar 2014 16:49:05 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:35168) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WRpKB-00050w-29 for guile-devel@gnu.org; Sun, 23 Mar 2014 16:48:59 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WRpK6-0008Fn-7j for guile-devel@gnu.org; Sun, 23 Mar 2014 16:48:54 -0400 Original-Received: from a-pb-sasl-quonix.pobox.com ([208.72.237.25]:57207 helo=sasl.smtp.pobox.com) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WRpK6-0008Fe-2m for guile-devel@gnu.org; Sun, 23 Mar 2014 16:48:50 -0400 Original-Received: from sasl.smtp.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-quonix.pobox.com (Postfix) with ESMTP id 3632C108CD; Sun, 23 Mar 2014 16:48:49 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=pobox.com; h=from:to:cc :subject:references:date:in-reply-to:message-id:mime-version :content-type; s=sasl; bh=7GtyOvIuV9HGblOlWN8yldlR4qI=; b=wQsSUf iuvnUiKYa6mjxgQVKXweCQ3uNgTQLBECm11Qj6bHTxUYy6osIaqaEZ0ZVHIGh5nS 785DPrOSEfQoldC5zE7sWq5FoSWu+yd0DNfTRJuq7HlAEr9BSaH4BjX4ZAR/BLE6 Is3Z8i0HgXLkPzMekE0JbI9ZDrZrpe5tPjF8Q= DomainKey-Signature: a=rsa-sha1; c=nofws; d=pobox.com; h=from:to:cc :subject:references:date:in-reply-to:message-id:mime-version :content-type; q=dns; s=sasl; b=AGCHIv2oOzIRW+wtUka+8iOa36RzxVdp hEdooUIHH4yzUcfwOmFKQgHlv4Ru2tacVvXQpoFF1EpVF7f31Yd1Dkcl0x495oPr WSc+M5Ht9lkD4nJ+snenO3BYYyEoFc6UkF3ZelPXwpSYg5FtAK/Z2iSPj5Z7Fqsn RHwNhy8Sf+o= Original-Received: from a-pb-sasl-quonix.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-quonix.pobox.com (Postfix) with ESMTP id 2C7EB108CB; Sun, 23 Mar 2014 16:48:49 -0400 (EDT) Original-Received: from badger (unknown [88.160.190.192]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by a-pb-sasl-quonix.pobox.com (Postfix) with ESMTPSA id 5CB3C108CA; Sun, 23 Mar 2014 16:48:48 -0400 (EDT) In-Reply-To: <87wqmkjyqr.fsf@tines.lan> (Mark H. Weaver's message of "Fri, 13 Sep 2013 15:41:16 -0400") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) X-Pobox-Relay-ID: 888B7B0C-B2CC-11E3-B1C7-873F0E5B5709-02397024!a-pb-sasl-quonix.pobox.com X-detected-operating-system: by eggs.gnu.org: Solaris 10 X-Received-From: 208.72.237.25 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:16996 Archived-At: On Fri 13 Sep 2013 21:41, Mark H Weaver writes: > Here's an implementation that does this benchmark about 80 times faster > on my machine: (20 milliseconds vs 1.69 seconds) > > (define* (string-replace-substring s substr replacement > #:optional > (start 0) > (end (string-length s))) > (let ((substr-length (string-length substr))) > (if (zero? substr-length) > (error "string-replace-substring: empty substr") > (let loop ((start start) > (pieces (list (substring s 0 start)))) > (let ((idx (string-contains s substr start end))) > (if idx > (loop (+ idx substr-length) > (cons* replacement > (substring s start idx) > pieces)) > (string-concatenate-reverse (cons (substring s start) > pieces)))))))) Inspired to code-golf a bit, here's one that's even faster :) (define (string-replace-substring s substring replacement) "Replace every instance of substring in s by replacement." (let ((sublen (string-length substring))) (with-output-to-string (lambda () (let lp ((start 0)) (cond ((string-contains s substring start) => (lambda (end) (display (substring/shared s start end)) (display replacement) (lp (+ end sublen)))) (else (display (substring/shared s start))))))))) Just marginally so, though. Andy -- http://wingolog.org/