OpenEuphoria

Re: Slice sequence--new algorithm

• Posted by ddparnell at bigpond.com Feb 21, 2001
• 416 views

Its nearly always hard to improve on any of Jiri's routines, but I might
have a slight speed improvement for this one.

I noticed that Jiri's method does a lot of work for no effect until the
first occurrance of 'n' in 's'. So I tested for that condition first and
then applied Jiri's method. This gave me about a 30% average speed increase
using the test program below.

--------remove.e------------------
global function remove(sequence s, object n)
    integer p

    -- Is there any 'n' in 's'?
    p = find(n , s)
    -- If not, then get out of here.
    if p = 0 then
        return s
    end if

    -- Start the sequential search and shift
    -- from the first 'n'
    for i = p+1 to length(s) do
        if compare(s[i], n) then
            s[p] = s[i]
            p += 1
        end if
    end for
    return  s[1..p-1]
end function


---------testrem.ex---------------------
include remove.e

atom e
sequence VOID
integer x

-- Reset the counter
x = 0

-- Calculate the stop time (10 seconds from now)
e = time() + 10

-- Until the time's up, do the tests and count them.
while e > time() do
    x += 1

    VOID = remove({2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1}, 1)
    VOID = remove({1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1}, 1)
    VOID = remove({}, 1)
    VOID = remove({1}, 1)
    VOID = remove({1,1}, 1)
    VOID = remove({2,3,4,5,6,7,8,9,0,2,3,4,5,6,7,8,9,0,2,3,4,5,6,7,8,9,0},
1)
    VOID = remove({2,3,4,5,6,7,8,9,0,1,1,1,1,2,3,4,5,6,7,8,9,0}, 1)
    VOID = remove({2,3,4,5,6,7,8,9,0,2,3,4,5,6,7,8,9,0,2,3,4,5,6,7,8,9,1},
1)
    VOID =
")
    VOID =
remove({"the","quick","brown","fox","jumped","over","the","lazy","dog"}, 1)

end while
-- Display how many cycles I got through in 10 seconds.
? x

--------------
On my machine I'm getting an average of 17,000 test cycles per second and
12,800 per second using Jiri's routine.

------
Derek Parnell
Melbourne, Australia
(Vote [1] The Cheshire Cat for Internet Mascot)