1. Slice sequence--new algorithm
--Slice sequence--new algorithm follows
Hello Lutz,
Thats a nice little algorithm too! As i was saying in
a previous post, there are probably many ways to accomplish
the goal of removing elements from a sequence. My little
example algorithm was more memory efficient, so the speed
difference between the two algorithms has alot to do with
installed memory in the system, and overall mem resources
available at the time. This is mainly due to the fact that
your algorithm creates a second copy of the original sequence,
meaning at the end of the code there exists two copies of the
same sequence given no removals, or very closely matching for
removals of only a small amount of elements. If your target
system can handle this, i would certainly use it.
In light of what Rob had said about speed of accessing
random elements being the primary speed consideration
when coding the Euphoria interpreter, i would think
if your application target memory can accept two sequences
like that, then i would immediately create a second copy and
then enter an algorithm that simply copies all the data to
be retained into the second copy, while skipping over any
data that is to be removed. This should show a tremendous
speed advantage over algorithms using '&' or 'append'.
A quick algorithm would look like this:
sequence s,t
integer len,pA,pB,n
s={99,1,2,3,99,4,5,99,6,99,7,8,9,99}--test sequence
?s
len=length(s)
n=99 --test value--normally this is user input
--maintain two pointers:
pA=0
pB=0
--create clone sequence:
t=s
while pA<len do
pA=pA+1 --point to next element in s
if s[pA] = n then
--skip that element
else
--copy that element to the clone sequence
pB=pB+1
t[pB]=s[pA] --replace element in sequence t
end if
end while
s=t[1..pB]--adjust total length of final sequence
t={}--recover memory unless t will be used again later...
?s
On the down side, this kind of algorithm might be hard to
adapt to a more complex sequence structure while retaining
the same speed advantages.
On the up side, single dimension sequences are used a lot
anyway.
Good luck with it.
--Al
2. Re: Slice sequence--new algorithm
Lutz, Al & co,
I think the routines below for removal of all occurrences of an
element from a sequence are both simpler and slightly faster than the
ones proposed so far.
jiri
function remove(sequence s, integer n)
integer p
p = 0
for i = 1 to length(s) do
if s[i] != n then
p += 1
s[p] = s[i]
end if
end for
return s[1..p]
end function
-- generalized:
function remove(sequence s, object n)
integer p
p = 0
for i = 1 to length(s) do
if compare(s[i], n) then
p += 1
s[p] = s[i]
end if
end for
return s[1..p]
end function
3. Slice sequence--new algorithm
- Posted by Lutz_Heitmann at NF.MAUS.DE
Feb 20, 2001
-
Last edited Feb 21, 2001
Kommentar zu P48305@KI in der Gruppe EUPHORIA
Hello Al,
AG>That's a nice little algorithm too!
No big deal - simple and straight forward... ;)
AG>My little example algorithm was more memory efficient
Yes, but nowadays time is more valuable than memory space!
AG>This is mainly due to the fact that your algorithm creates
AG>a second copy of the original sequence, meaning at the end
AG>of the code there exists two copies of the same sequence
AG>given no removals
What do you think EUPHORIA does internally? To create a
sequence with only the last element different, all the
pointers to sequence elements up to this point have to be
copied anyway!
A points to B, B points to C, C points to - something other
than D. So the sequence from A to C needs to be rebuilt.
Think of LISP's CARs and CDRs! (do you know LISP?)
AG>If your target system can handle this, i would certainly
AG>use it.
Go ahead! My "target system" is plain DOS, but from what I
know I can guess a lot about data structures.
Lutz.
4. Re: Slice sequence--new algorithm
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)
5. Re: Slice sequence--new algorithm
Nice one, Derek! Redundant copying bothered me a bit, but obviously
not enough to do anything about it :). jiri
----- Original Message -----
From: <ddparnell at bigpond.com>
To: "EUforum" <EUforum at topica.com>
Sent: Thursday, February 22, 2001 2:02 AM
Subject: Re: Slice sequence--new algorithm
> 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 =
> 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 =
> 1)
> VOID =
>
},"the
> ")
> VOID =
>
}, 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
6. Re: Slice sequence--new algorithm
Al, did you have something like the following function in mind?
jiri
function remove(sequence s, object n)
object si
integer p
p = 0
for i = 1 to length(s) do
si = s[i]
if compare(si, n) then
if sequence(si) then
si = remove(si, n)
end if
p += 1
s[p] = si
end if
end for
return s[1..p]
end function
----- Original Message -----
From: "Al Getz" <Xaxo at aol.com>
To: "EUforum" <EUforum at topica.com>
Sent: Thursday, February 22, 2001 2:07 AM
Subject: RE: Slice sequence--new algorithm
> Lutz & Juri:
>
> Hi Juri,
> Nice algorithm! I think i'll use that one myself.
> Since now your in the mood, perhaps you would care to
> generalize one step further:
> Adapt your algorithm to handle an arbitrarily complex
> sequence. The time factor has stumped me a bit, as
> elements wont be the same in all locations in the sequence,
> therefore sometimes a larger element will replace a smaller
> element, which brings in a longer time cost factor. If there
> was some way around that...
> Perhaps recursion would help for the more complex case, even
> if it takes more time to complete, which brings a second
> question to mind which ill ask in a separate post about
> recursion and memory resources.
>
> Hi Lutz,
> Thanks for your insight!
>
> Lutz wrote:
> >>Yes, but nowadays time is more valuable than memory space!
> Time isnt always independent of memory: if you get low on memory
> and windows resorts to disk swapping, it could take 10x longer to
> run then a more complicated program that doesnt use up all the
> ram in the system.
>
> >>What do you think EUPHORIA does internally?
> Check out Rob's response to the thread.
>
>
> Have fun with it!
> --Al
>
>
>
