OpenEuphoria

Re: modified reverse

• Posted by Derek Parnell <ddparnell at bigpond.com> Aug 05, 2001
• 496 views

> From: Robert Craig <rds at RapidEuphoria.com>
> To: EUforum <EUforum at topica.com>
> Reply-To: EUforum at topica.com
> Organization: Rapid Deployment Software
> Subject: Re: modified reverse
> Date: 6/08/2001 2:21:37 PM
> 
> 
> rforno writes:
> > The following modified reverse routine is simpler and, 
> > most of the times, slightly faster than the standard one. 
> > However, I noticed that the comparison between the two 
> > is affected by the type of data (integer or not,
> > simple or compound sequence), and even it seems that 
> > the way of generating the data (by means of a single 
> > sentence or by a loop) affects the resulting
> > timings. Any explanation for such a behavior?
> >
> > global function reverse1(sequence s)
> >    integer n
> >    sequence t
> >    n = length(s)
> >    t = repeat(0,n)
> >    for i = 1 to n do
> >         t[n] = s[i]
> >         n -= 1
> >    end for
> >    return t
> > end function
> 
> I did a quick test, and your reverse1() above does seem to
> be slightly faster than reverse() in misc.e. 
> This is counter-intuitive since you do n decrements of n
> where the standard reverse() only does n/2 increments.
> The number of copies, t[n] = s[i], is the same, since the
> standard reverse() does two copies per loop but only
> half as many loops.
> 

Strange but I found rforno's version slightly slower (96%) than the
standard. One way to get the standard one going slightly faster is to force
an integer conversion of the floor() function. Because the floor() function
is in the for..loop, Euphoria assumes that it is possible to generate a
really big result and does tests for atom-ness and integer overflow on every
comparison of the 'upper' variable. It even does extra work when adding one
to it for the next iteration, just in case it overflows the integer bounds.

This version is ever so slightly faster (3%) ...

global function reverse2(sequence s)
    integer lower, n, max
    sequence t
    
    n = length(s)
    t = repeat(0, n)
    lower = 1

    -- Force an integer result.
    max = floor(n/2)+1
    
    -- Now 'upper' knows that it can safely do integer comparisions
    -- because both 'n' and 'max' are integers.
    for upper = n to max by -1 do
	t[upper] = s[lower]
	t[lower] = s[upper]
	lower += 1
    end for
    return t
end function

-----------
cheers,
Derek Parnell
Senior Design Engineer
Global Technology Australasia Ltd
dparnell at glotec.com.au

---------------------



confidential information intended solely for the use of the individual or
entity to whom they are addressed. If you are not the intended recipient of
this message you are hereby notified that any use, dissemination,
distribution or reproduction of this message is prohibited. If you have
received this message in error please notify the sender immediately. Any
views expressed in this message are those of the individual sender and may
not necessarily reflect the views of Global Technology Australasia Limited.