OpenEuphoria

Re: Interesting Experiment With String/Sequence Slicing

• Posted by Derek Parnell <ddparnell at bigpond.com> Aug 20, 2001
• 432 views

> From: slie at theage.fairfax.com.au
> To: EUforum <EUforum at topica.com>
> Reply-To: EUforum at topica.com
> Subject: Re: Interesting Experiment With 
> String/Sequence Slicing
> Date: 21/08/2001 12:58:45 PM
> 
> 
> i am just wild guessing here, but could it 
> be true that a function can be
> specifically written to deal with string 
> type sequences and so speeding up
> the slicing function?
> 

Hi Sam,
we have discovered that the fastest method of inserting, deleting, and
replacing text in sequences is to minimize the number and size of
concatenations.

Consider the general case where you have a text of <aaa><bbb><ccc> and a
replacement text of <ddd> which is going to replace <bbb>.

If the length of <ddd> is longer than <bbb> then create a new sequence (
using the repeat() function) with the length of <aaa> + <ddd> + <ccc> then
copy these sub-strings into the new sequence and return the new sequence. 

Where <ddd> is shorter than <bbb>, you can avoid the overhead of creating a
new sequence and reuse the space in the exiting string. The trick here is to
move either <aaa> closer to <ccc> or <ccc> closer to <aaa>, depending on
which is smaller, and leaving enough room for <ddd> to slide in between
them. Then you just return the truncated sequence. If you didn't move <aaa>
then that is S[1 .. length(<aaa>)+length(<ddd>)+length(<ccc>)], but if you
did move <aaa> it is S[length(S) -
(length(<aaa>)+length(<ddd>)+length(<ccc>)) .. length(S)].

There are further optimisations if <aaa>, <ccc>, or <ddd> are empty
sequences.

I know this looks complex but it is almost always faster than creating
temporary sequences and concatenating them, depending on the length of the
sequences involved.
----
Derek


confidential information intended solely for the use of the individual or
entity to whom they are addressed. If you are not the intended recipient of
this message you are hereby notified that any use, dissemination,
distribution or reproduction of this message is prohibited. If you have
received this message in error please notify the sender immediately. Any
views expressed in this message are those of the individual sender and may
not necessarily reflect the views of Global Technology Australasia Limited.