OpenEuphoria

Sequence ins/del

• Posted by Michael Palffy <vulcan at win.co.nz> Oct 29, 2000
• 388 views

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

>Anyway, i have noticed a useful code speed-up that can be used for a
large
>1-d sequence where insertion of an element is required.

This could mean that for some obscure reason my postings are being
filtered out (ie, being mistaken for MTS) or maybe no-one bothered to
actually read the whole thing where they would have found some useful info
for speed-hungry programmers.

Below is small program that demonstrates a significant speed-up for
inserting/deleting an element via a large sequence. I have only tested it
with elements of integers but it may also work for sequences too. The
database.ex program in euphoria\demo\bench increased its transactions rate
by 3% simply by altering the delete code in DELETE area.

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.

Yours Truly
Mike

vulcan at win.co.nz



without warning

global sequence data

integer extent extent = 10000

data = repeat(0, extent)

procedure insertconventional(integer pos, integer n)
data = data[1..pos-1] & n & data[pos..length(data)]
end procedure

procedure deleteconventional(integer pos)
data = data[1..pos-1] & data[pos+1..length(data)]
end procedure

procedure insertfaster(integer pos, integer n)
integer len
data &= 0    -- reserve some space
len = length(data)
data[pos+1..len] = data[pos..len-1] -- move top half up a notch
data[pos] = n -- assign the new value
end procedure

procedure deletefaster(integer pos)
integer len
len = length(data)
data[pos..len-1] = data[pos+1..len] -- move upper half down a notch
data = data[1..len-1] -- trim end piece
end procedure

procedure blank(integer n)
end procedure


integer loop loop = 2000

atom a, b, c
puts(1, "Testing speed for INSERT & DELETE...\n\n\n")

a=time()
for i=1 to loop do
deleteconventional(rand(extent))
insertconventional(rand(extent), 0)
end for
a = time() - a


b=time()
for i=1 to loop do
deletefaster(rand(extent))
insertfaster(rand(extent), 0)
end for
b = time() - b


c=time()
for i=1 to loop do
blank(rand(extent))
blank(rand(extent))
end for
c = time() - c

a -= c
b -= c


printf(1, "Times for conventional ins/del : %.3f" &
  "\n\nTimes for faster ins/del : %.3f\n\n\n" &
  "Speed ratio : %.2f", {a,b,a/b})