1. test valid
Hi,
I wished to optimize a test that find a value in a sequence of valid
numbers. I wondered that the third test was the fastest though it seems
to be poor programming. Following the tests and results.
Any advice or comment is welcome.
Regards,
--
--TESTT.EX Comparison of speed:
-- 3 tests to find a valid value JHendrickx 5/7/97
include machine.e
machine_proc(38,100)
atom t, t1, t2 , t3
integer tstval, ok, okk, okkk, search
sequence valid
tstval=11 ok=0 okk=0 okkk=0
valid={3,5,7,11}
-- Test 1 with or ---------------------------
t= time()
for a=1 to 500000 do
if tstval=3 or tstval=5 or tstval=7 or tstval=11 then
ok=1
end if
end for
t1=time()-t
-- Test 2 with find --------------------------
t= time()
for a=1 to 500000 do
search=find(tstval,valid)
--search=find(tstval,{3,5,7,11}) --this form takes much more time :
-- 2.61 sec (srch f. 3), 2.66 (srch f. 5),
-- 2.71 (srch f. 7), 2.77 (srch f. 11)
if search!=0 then
okk=1
end if
end for
t2=time()-t
-- Test 3 with if-elsif -----------------------
t= time()
for a=1 to 500000 do
if tstval=3 then okkk=1
elsif tstval=5 then okkk=1
elsif tstval=7 then okkk=1
elsif tstval=11 then okkk=1
end if
end for
t3=time()-t
--
? ok
? okk
? okkk
? t1
? t2
? t3
-- Results (PC 486 DX2 80 Mhz):
-- search for 1 : or -> 1.21 sec find -> 0.95 sec elsif -> 0.42 sec
-- search for 3 : 1.28 0.85 0.30
-- search for 5 : 1.28 0.90 0.39
-- search for 7 : 1.29 0.95 0.47
-- search for 11: or -> 1.30 sec find -> 1.01 sec elsif -> 0.51 sec
--
-- Jean.Hendrickx. j.hendrickx at infoboard.be
2. Re: test valid
Jean Hendrickx wrote:
>I wished to optimize a test that find a value in a sequence of valid
>numbers. I wondered that the third test was the fastest though it seems
>to be poor programming. Following the tests and results.
>Any advice or comment is welcome.
> <SKIPPED>
>-- Test 1 with or ---------------------------
> <SKIPPED>
>-- Test 2 with find --------------------------
> <SKIPPED>
>-- Test 3 with if-elsif -----------------------
> <SKIPPED>
>-- Results (PC 486 DX2 80 Mhz):
>-- search for 1 : or -> 1.21 sec find -> 0.95 sec elsif -> 0.42 sec
>-- search for 3 : 1.28 0.85 0.30
>-- search for 5 : 1.28 0.90 0.39
>-- search for 7 : 1.29 0.95 0.47
>-- search for 11: or -> 1.30 sec find -> 1.01 sec elsif -> 0.51 sec
>--
>-- Jean.Hendrickx. j.hendrickx at infoboard.be
The or test results make sense, since Euphoria doesn't use short
circuit evaluation (i.e. it doesn't stop evaluating expressions just because
the total expression's result is already certain, it *always* evaluates the
entire conditional, at least as far as my own experiments have shown).
Therefore they *should* be slower than a find() call since the find call
will presumably drop out and return a value as soon as it finds the value.
The or'ing method should also have less time variation(same reason), which
does seem to be the case in your test results.
The elsif results, however, are definitely weird. I can see how they
would be faster in *some* cases since they would find a true condition, do
their thing, and drop out without further testing. But you are right, it
is certainly odd that the worst-case elsif should still be faster than
either of the other methods.
Any suggestions, gurus?
Craig
3. test valid
Jean Hendrickx wrote:
>Hi,
>I wished to optimize a test that find a value in a sequence of valid
>numbers. I wondered that the third test was the fastest though it seems
>to be poor programming. Following the tests and results.
>Any advice or comment is welcome.
>Regards,
>--
>--TESTT.EX Comparison of speed:
>-- 3 tests to find a valid value JHendrickx 5/7/97
<------>code snipped<------->
I'm not sure what you are trying to do with your code. The for value of
500000 seems a little much; it would be a lot easier to use this function=
I'm posting right now to check if a value is contained in a sequence.
----code starts here----
function check_value(atom tstval, sequence valid)
if not find(tstval,valid) then
return 0
else
return 1
end if
end function
--usage--
atom t, v
sequence s
v =3D 6
s =3D {4,5,2,9,6,7}
t =3D check_value(v,s)
---code ends here---
t will be true since s contains the value 6. Most of the time, you will
use this function to check user input and such against values already bui=
lt
into the program. Hope this helps.
Regards,
Bryan Watts
4. Re: test valid
On Wed, 6 Aug 1997 18:41:06 +0100 Jean Hendrickx
<jean.hendrickx at EURONET.BE> writes:
>Subject: test valid
>Hi,
>I wished to optimize a test that find a value in a sequence of valid
>numbers. I wondered that the third test was the fastest though it
>seems
>to be poor programming. Following the tests and results.
>Any advice or comment is welcome.
Optimizing algorithms one of the things I have found to be a very
interesting subject. Took a programming logic class a short time ago and
we spent a week on this subject alone.
You can boil it down to two major items to consider; Time and Space. Just
reading the clock T1 tells us how efficient it is on one machine, with a
one set of data and one size of data. Each line of code has to be
analyzed and a algebraic function developed that takes all the lines into
consideration and removes the data and machine dependency.
Basically you can say "time complexity" is the number of time units to
perform the command plus the number of time units to setup the command or
t(n)=an+b. Here a is the command time constant, b is the setup time
constant and n is the number of times the command executes.
In your first two examples the "time complexity" ends up being a
quadratic function while the 3rd example it ends up being liner. The
third method although it appears to be "bad programming form" actually
does less testing. The inner loop instructions only executes 500K times.
Example one has to perform the if check 500K times and the or test 1500K
times. Example two has a similar "time complexity" function as example
one, although slightly more efficient due to the already optimized find
function. The time difference between the two forms of find are due to
the "space complexity" factor of how memory is used for them that effects
their time complexity.
Some sorting algorithms are faster than others on small sets of data
while others are faster on large sets of data. To see this look at the
sort demo that came with Euphoria. If "time and space" complexities made
no difference then there would only be one common sorting algorithm in
use for everything.
For hobby programmers these things and how to calculate them are
generally of no importance. They do have an effect when writing code for
large tasks such as calculating and printing IRS refunds or Stock Holder
Dividend checks. It also get real important for 3D video display and the
more complex games I see some people are working on. Sometimes there is
even a need to slow the algorithm down so that external equipment can
handle the data flow without buffer overflow.
I don't have a good reference book for you as my instructor used
information from many sources and made us learn it by doing problems,
"practical application". It can also be a real PITA to extract the real
complexity functions from code. The functions can also be converted to
one of seven common complexity functions known as Big-O notation for ease
of comparing one algorithm to an other one.
What I would tell you is, the bottom line for a hobbyist is to test a
couple of algorithms, as you have done, and use the one you find to be
consistently the fastest. Where I work we have a fellow that all he does
is calculate "time complexities" and convert to Big-O notation. He has a
degree in Mathematics and could not write a single line of code if he
tried, but he sure can read algorithms and extract the algebraic
functions from them.
Larry D. Poos
-[USMC (Retar{bks}{bks}ired) Havelock, NC]-
- Programming and System Consultant, LTAD Enterprises -
- Yep, they called me back to work -
5. Re: test valid
- Posted by Daniel Berstein <danielberstein at USA.NET>
Aug 07, 1997
-
Last edited Aug 08, 1997
Continuing Larry's catedra on code optimization I would recommend the
following books:
(please notice I'm translating the book names from Spanish, but I
guess that you can ask the librarian will make it)
1.- "Data Structures" from the Shawm collection. I think it's
published my McGraw-Hill.
2.- "Algorithms and Data Structures" (has some topics about
"complexity" of the algorithm) I dont' remember the bibliographic
information.
3.- "Principles of Compiler Design" by Aho and Ullman. Edited by
Addison-Wesly.
4.- "Compilers: Principles, Techniques and Tools" A new version of
the above book, by Aho, Sethi and Ullman. Also edited by
Addison-Wesly.
The two last books teach advanced technics in code analisys and
optimization. I guess Rob Craig readed them several times ;)
Regards,
Daniel Berstein
danielberstein at usa.net
http://www.geocities.com/SiliconValley/Heights/9316
