Re: sleepless night & UFOs
I concur, Gabriel. Your routine looks like it would execute faster than
mine for more than a couple of recursions. I knew that passing the extra
variables would make it slower (although I didn't know by how much). I
think my routine is slightly more readable than yours, but for long
sequences, yours would be much faster than mine.
IMHO, unless speed is critical, I think it's best to opt for readability.
If it executes too slowly, you can always optimize it.
Anyway, sorry if I wasted your time. I've never written a program in
Euphoria. I just saw an opportunity to try to help someone, so I wrote my
posting off the top of my head without testing it...
Joe
-----Original Message-----
From: Boehme, Gabriel [SMTP:gboehme at MUSICLAND.COM]
Sent: Tuesday, April 20, 1999 5:23 PM
To: EUPHORIA at LISTSERV.MUOHIO.EDU
Subject: Re: sleepless night & UFOs
Colin Taylor wrote:
>I don't see how a complex function like Gabriel's can possibly be faster
>than a straight-forward approach such as:
>
>function remap(sequence s, sequence index, object newvalue)
> if length(index) > 1 then
> s[index[1]] = remap(s[index[1]], index[2..length(index)],
newvalue)
> else
> s[index[1]] = newvalue
> end if
> return s
>end function -- remap
In my tests, both my original and modified routines are almost always
faster
than Joe Otto's routine. Colin's routine (shown above) is almost always
*slower* than Joe's. There are several good reasons why my two "complex"
routines are generally faster than either Joe's or Colin's. Code efficiency
doesn't always result from code simplicity; there are other factors which
come into play.
1) Calling length() multiple times vs. storing it once in a variable
If you're going to use a sequence's length value more than once in a given
section of code (and the sequence's length isn't changing), it's almost
always faster to define another integer variable, store the length() value
there, and then reference the variable instead. This is one reason why
Colin's routine is slower than Joe's, and this is the main change I made to
my original routine to gain 5+% in execution speed.
2) Subscripting a sequence vs. storing the value in a variable
If you're going to access a given sequence element more than once in a
given
section of code (and the sequence element isn't changing), it's almost
always faster to define another variable, store the sequence element there,
and then reference the variable instead. This is another reason why Colin's
routine is slower than Joe's -- Colin's routine references "index[1]" twice
in the recursive call, while Joe's routine stores "index[1]" in a variable
and uses that instead.
3) Recursive calls: parameter passing vs. local variables
When writing recursive functions, there is usually only one parm actually
being treated recursively -- the others are just along for the ride. This
is
quite true with remap() -- newvalue only actually gets used on the final
recursive call, the rest of the time it just takes up space. Instead of
requiring the interpreter to continually reallocate space for a variable
that will only be used once, it makes more sense just to store it in a
local
variable until you actually need it. This is also true for the index_list
--
instead of passing index_list[2..length(index_list)] along as a parm, it's
much faster to store the list in a local variable and grab the first
element. Then, *only* if you have another recursive call coming up, you
truncate index_list to index_list[2..len] before making the call.
4) The test data
This is an often-overlooked part of any benchmarking procedure. The data
being used to test your routines can have a *major* impact on your results.
Whatever routines you're testing, it's a good idea to vary the test data.
Look closely at your code, and choose data that will test very specific
parts of the routines (if conditions, recursive calls, etc.). Also, keep in
mind the most likely real-world uses of your routines, to avoid testing
unnecessary or unlikely situations.
In my remap() tests, I found that my routines always run faster with an
index_list length of 3 or more. Joe's routine runs faster with an
index_list
length of 2, and Colin's runs the fastest with an index_list length of 1.
The longer index_list is, the more recursive calls the routine has to make,
and the more points 1-3 above come into play.
Now, it's unlikely that a programmer will use remap() very often on
length-1
index_lists -- it may occur incidentally as part of an algorithm, but it's
not likely to be the primary use of remap(). So, if you'll primarily be
using length-2 index_lists in your program, Joe's routine will be faster.
If
you'll primarily be using length-3 or greater index_lists in your program,
then my modified routine is the faster. My assumption (which may be wrong)
is that general use of remap() would regularly involve length-3 or longer
index_lists. I therefore conclude that my modified routine is probably the
best choice for general-purpose use.
No matter what coding tips or suggestions you follow, it's *always* a good
idea to run some benchmarks and check things out for yourself. I have
included my remap benchmark program below. It's not too flashy, but it gets
the job done. (I don't trust call_func() anymore, since the exact *same*
code will come back with *different* execution times, depending on the
code's physical location in the program!)
I hope all of this has been helpful and/or educational (and I hope I got
all
my facts right!).
Be seeing you,
Gabriel Boehme
-----------------------------------------------------------------
-- remap.exw by Gabriel Boehme
--
-- This benchmark program will run under Windows or DOS.
--
-- However, Windows tickcounts are more reliable, since they
-- only count the time the program is actually executing.
-- (Somebody correct me if this statement is inaccurate!)
-----------------------------------------------------------------
include get.e
include machine.e -- for running under DOS
tick_rate(10000) -- does nothing under Windows
-- execution parms
constant
ITER = 1e6 -- benchmark iterations
-- test sequence depth determined by LEVELS length
,LEVELS = {5,10,3} -- length of each level in the test sequence
,LIST = {3,5,2} -- *must* all be integers >= 1 and <= LEVELS[x]
-----------------------------------------------------------------
-- Gabriel Boehme's original routine
sequence list
object val
function remap_recursive_old(sequence s)
integer i
i = list[1]
list = list[2..length(list)]
if length(list) then
s[i] = remap_recursive_old(s[i])
else
s[i] = val
end if
return s
end function
function remap1(sequence s, sequence index_list, object newvalue)
list = index_list
val = newvalue
return remap_recursive_old(s)
end function
-----------------------------------------------------------------
-- Joe Otto's routine
function remap2 (sequence s, sequence indexList, object newValue)
integer listLen, i1
listLen = length (indexList)
i1 = indexList [1]
if listLen > 1 then
s [i1] = remap2 (s [i1], indexList [2..listLen], newValue)
elsif listLen = 1 then
s [i1] = newValue
end if
return s
end function
-----------------------------------------------------------------
-- Gabriel Boehme's modified routine
sequence remap_list
object remap_value
function remap_recursive(sequence s)
integer i, len
i = remap_list[1]
len = length(remap_list)
if len > 1 then
remap_list = remap_list[2..len]
s[i] = remap_recursive(s[i])
else
s[i] = remap_value
end if
return s
end function
function remap3(sequence s, sequence index_list, object new_value)
remap_list = index_list
remap_value = new_value
return remap_recursive(s)
end function
-----------------------------------------------------------------
-- Colin Taylor's routine
function remap4(sequence s, sequence index, object newvalue)
if length(index) > 1 then
s[index[1]] = remap4(s[index[1]], index[2..length(index)],
newvalue)
else
s[index[1]] = newvalue
end if
return s
end function -- remap
-----------------------------------------------------------------
procedure msg_wait(sequence msg)
puts(2, msg & "\n\nPress any key to continue . . .")
if wait_key() then end if
puts(2, "\n")
end procedure
-- verify execution parms
if length(LIST) = 0 or length(LIST) > length(LEVELS) then
msg_wait("Invalid LIST sequence length")
abort(1)
end if
for i = 1 to length(LIST) do
if not integer(LIST[i]) or LIST[i] < 1 or LIST[i] > LEVELS[i] then
msg_wait("Invalid LIST sequence - index values out of bounds")
abort(1)
end if
end for
-- build the test sequence
sequence s
s = repeat(0, LEVELS[length(LEVELS)]) -- start with the innermost level
for i = length(LEVELS)-1 to 1 by -1 do -- and work your way outward
s = repeat(s, LEVELS[i])
end for
printf(1, "A remap() benchmark program by Gabriel Boehme\n"
& "Sequence depth %d, remap depth %d\n\n",
{length(LEVELS), length(LIST)})
puts(1, "[Smaller values are better]\n---------------------------\n")
-----------------------------------------------------------------
atom t
-- the moment of truth
puts(1, "Gabriel's original routine: ")
t = time()
for i = 1 to ITER do
s = remap1(s, LIST, 1)
end for
? time() - t
puts(1, "Joe's routine: ")
t = time()
for i = 1 to ITER do
s = remap2(s, LIST, 1)
end for
? time() - t
puts(1, "Gabriel's modified routine: ")
t = time()
for i = 1 to ITER do
s = remap3(s, LIST, 1)
end for
? time() - t
puts(1, "Colin's routine: ")
t = time()
for i = 1 to ITER do
s = remap4(s, LIST, 1)
end for
? time() - t
msg_wait("")
-----------------------------------------------------------------
________________________________________________________
NetZero - We believe in a FREE Internet. Shouldn't you?
Get your FREE Internet Access and Email at
http://www.netzero.net/download.html
|
Not Categorized, Please Help
|
|
