From: Jano Svitok <jan.svitok@...>
Date: 2007-07-26T03:42:02+09:00
Subject: Re: Efficiency/runtime trouble - may not be Ruby-specific

On 7/25/07, Kaldrenon <kaldrenon@gmail.com> wrote:
> Hi all - apologies in advance since this issue is not necessarily a
> Ruby issue, but I've written the program in Ruby and the community
> here has been very helpful/friendly in my experience.
>
> I'm working on another problem from Project Euler ( http://www.projecteuler.net
> ). This one is problem 73 (I'm not actually that smart, I just jump
> around ;-) ):
>
> "Consider the fraction, n/d, where n and d are positive integers. If
> nd and HCF(n,d)=1, it is called a reduced proper fraction. How many
> fractions lie between 1/3 and 1/2 in the sorted set of reduced proper
> fractions for d  10,000?"
>
> So I set up an hcf(n,d) function that prime-factor-izes n and d to see
> if n/d is reduced and proper:
>
> Primes_under_100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
>                     43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
> def hcf(n,d)
>   Primes_under_100.each do |prime|
>     if (prime < Math.sqrt(d) &&
>         n % prime == 0 &&
>         d % prime == 0) ||
>         d % n == 0
>       return 2
>     end
>   end
>   return 1
> end
>
> Then I ran that through a loop that builds an array of unique
> instances of fractions between 1/2 and 1/3:
>
> red_prop_fract = []
> for d in 2..10_000 do
>   for n in 1...d do
>     if hcf(n,d) == 1 && n.to_f/d > 1.0/3 && n.to_f/d < 0.5
>       red_prop_fract.push(n.to_f/d) unless red_prop_fract.include?
> (n.to_f/d)
>     end
>   end
> end
>
> #Get the answer
> p red_prop_fract.length
>
>
> Now, I'm fairly certain that the algorithm is right, because I ran it
> on their example of d < 9 and got the correct answer. However, this
> setup is taking ridiculously long and I can't determine why. Running
> on a computer with a 2.4GHz CPU and 256 Mb of RAM, I started it at
> 4:30 yesterday and it hasn't terminated!
>
> I know that a nested 'for' loop that goes to n is O(n^2). And I know
> that the array I'm building is rather big, and growing it gradually is
> going to cause a lot of allocations and GCs. But I can't figure out
> why it's being so ridiculous.
>
> My first rule as a programmer is "Assume all problems are my fault."
>
> Insights?
>
> TIA,
> Andrew

Hi,

I don't want to spoil the fun, so just few hints:

hcf(14,35) == 1 which is wrong.

I don't think you have a problem with GC. Your algorithm is too slow.
You can verify this using profiler.

There are two ways of enhancing the speed:
1. enhacing the algorithm itself, i.e. lowering the O(n^2)and
2. tweaking the implementation (i.e. the constants)

Install the profiler, gem install ruby-prof, and run it
ruby-prof -p graph_html yourprog.rb > profile.html

Have a look at the output, and find the parts that take the most time.

Suggested changes:

1. Move things out of cycle if it doesn't depend on the inner variable.

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

3. Use Set instead of array.

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

5. Optimize the ranges of your loops

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


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

d <= 700 (24836)
your version: 66.281
with #3,4,2: 2.515
with #3,4,2,5: 2.141

d <= 1000 (50695)
with #3,4,2,5: 5.094
fixing hcf: 2.547

(I'm not sure about the results, I suspect at least 1/2 is included
there somehow, if not more false positives)

J.