Re: Efficiency/runtime trouble - may not be Ruby-specific

On Jul 25, 2:42 pm, "Jano Svitok" <jan.svi...@xxxxxxxxx> wrote:
1. Move things out of cycle if it doesn't depend on the inner variable.

I try to do this in general, but am I correct in my thinking that it's
not applicable to this script?

2. Cache hard-to-compute expressions, especially those involving floats.

I'm still very much a novice - could you explain to me in simple terms
what you mean, or point me to a document/resource on this topic?

3. Use Set instead of array.

Had a BIG impact on run-time, thank you!

4. Move easy-to-compute conditions (<, >) before the hard ones (hcf)

This is something I feel dumb for not remembering myself - although
some of these other things are new material for me, this is something
I've dealt with before. Thanks for the reminder. Also had a big impact
on time.

5. Optimize the ranges of your loops

As with tip #1, is there a way this technique can improve this script?
I know it's wise in general.

6. Try to avoid sqrt and floats as much as possible.

Like #1 and #5, I think - Can I really avoid floats, since I need to
get a number that's between two floats?

Some stats (core2duo T7200 2ghz/1gb ram/4mb cache, ruby 1.8.5, wxpsp2)
d <= 500 (12687)
your version: 20.453 seconds
with change #3: 6.981
with #3 and #4: 1.484
with #3,4,2: 1.203

On my system (2.4ghz/256mb ram/(don't know cache), ruby 1.8.6, wxpsp2)
(taking into account a number of other programs were running at the
time, it's much slower than it was for you but the rate of change is
comparable.)
d <= 500
with change #3: ~38 seconds
with changes #3 and #4: ~8 seconds.

I also took Morton's advice and dropped my hcf method in favor of
Mathn's gcd2(), along with dropping the array/set for a counter. I was
wary of this at first until I realized that with /reduced/ proper
fractions, there's no chance of a duplicate value. I had been using
the "push unless include?" style in order to avoid duplication, but
avoiding duplication is inherent.

My full script is now:

p Time.now
require 'mathn'
red_prop_fract = 0
for d in 2..10_000 do
for n in 1...d do
if n.to_f/d > 1.0/3 && n.to_f/d < 0.5 && n.gcd2(d) == 1
red_prop_fract += 1
end
end
end

p red_prop_fract.length
p Time.now

Many thanks to both of you! I always love it when people who know
their stuff are genuinely willing to help newbies like me.

-Andrew

.

Relevant Pages

  • [HPADM] RE : [SUMMARY] duplication of standard output
    ... The general answer is to use "tee". ... duplication of standard output ... i need to duplicate standard output in a script. ... this work fine for redirection, ...
    (HP-UX-Admin)
  • Re: Is there a script I can launch to ensure computer restarts into Safe Mode?
    ... every respondent in every group can ... This prevents duplication ... which does not have the switch. ... code or with a small number of script lines. ...
    (microsoft.public.windows.server.scripting)
  • Re: RC runs stuff twice?
    ... Warren Block wrote: ... mergebase.sh script adds this line to /etc/rc.conf to prevent the ... and guess what I found at the head of my /etc/rc.conf? ...
    (comp.unix.bsd.freebsd.misc)
  • RE: Duplicate entries on reports
    ... The script took care of most of the duplication but have a look below and you will see that there is still duplication. ... > HTH ...
    (microsoft.public.sms.misc)
  • Instant validation problem
    ... novice when it comes to Javascript, but i'm trying to write a script ... tick or cross appears deppending on if the input is valid. ... and how to fix the script. ...
    (comp.lang.javascript)