OpenEuphoria

Re: Sequence ins/del

• Posted by Derek Parnell <derekp at solace.com.au> Oct 30, 2000
• 380 views

>Alas, it seems no-one responded to my posting last week, er, now weeks
>ago.

Sorry, I've been so busy I forgot to test it out.

>
>The new code will ins/del an element at about twice the speed compared to
>the usual way. However for a sequence length entering the millions the
>speed could easily quadruple.

I agree, with your routines I've been getting a 2-3 times speed up.

I then added a further refinement and I'm now getting around 7 times speed
up.

I wondered if the speed would be effected by how many elements Euphoria had
to shift around. So I coded it so that it would always do the minimum amount
of shifting elements.

------------------------
procedure insertfaster(integer pos, integer n)
integer len
len = length(data) + 1
-- Test for the smallest # of elements to move.
if pos < (len - pos) then
data = 0 & data  -- reserve space at the front
data[1..pos-1] = data[2..pos] -- move front portion down
else
data &= 0    -- reserve some space at the end
data[pos+1..len] = data[pos..len-1] -- move back portion up a notch
end if
data[pos] = n -- assign the new value
end procedure

procedure deletefaster(integer pos)
integer len
len = length(data)
-- Test for the smallest # of elements to move.
if pos < (len - pos) then
data[2 .. pos] = data[1 .. pos - 1] -- move front portion up
data = data[2 .. len] -- trim off first element
else
data[pos..len-1] = data[pos+1..len] -- move back portion down a notch
data = data[1..len-1] -- trim off last element
end if
end procedure
-------------------------

-----
cheers,
Derek Parnell
derekp at solace.com.au