From: Kaldrenon <kaldrenon@...>
Date: 2007-07-26T06:29:59+09:00
Subject: Re: Efficiency/runtime trouble - may not be Ruby-specific

On Jul 25, 2:42 pm, "Jano Svitok" <jan.svi...@gmail.com> 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