Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!ucbvax!CS.WASHINGTON.EDU!wgg
From: wgg@CS.WASHINGTON.EDU (William Griswold)
Newsgroups: comp.lang.icon
Subject: Re: deleting characters
Message-ID: <9001200111.AA16921@june.cs.washington.edu>
Date: 20 Jan 90 01:11:14 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Distribution: inet
Organization: The Internet
Lines: 22


> The delete routine is quadratic wrt the length of the source string,
> while the strip routines are quadratic wrt the result.

I may be wrong, but I believe you will find that in modern implementations 
of Icon that the strip routines are linear in time.  Icon is smart enough 
to know that a string is located at the end of the string memory region 
(in this case the value of the variable holding the accumulating result 
string), and can just add to the end of it to concatenate.  Any other 
*modification* of a string requires copying--substring creation does not
require copying, since it is implemented as a pointer and an index. 

> You can get linear performance if you do it in C.

Many common operations in Icon require *more* time to perform in C--using
available abstractions--such as computing the length of a string.  Also
note that string concatentation in C in the standard way (using strcat)
takes linear time.  It also requires knowing the destination string is
long enough to hold the longer result.  Thus making strip as ``fast'' as
Icon's requires a little effort. 

					Bill Griswold