Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Re^7: Challenge: Number of unique ways to reach target sum

by fergal (Chaplain)
on Feb 15, 2006 at 21:02 UTC ( [id://530521]=note: print w/replies, xml ) Need Help??


in reply to Re^6: Challenge: Number of unique ways to reach target sum
in thread Challenge: Number of unique ways to reach target sum

Well, blokhead's memoize version take < 10s so that the easiest thing available as a benchmark and it's takes little effort to run it.

I managed to generate all solutions just using Perl in 74 mins on one machine and 2 hours on another. I'd like to be able to compare these results to your 72 mins without having to chew 72 mins of CPU. I just tried it on that machine and killed it after 93 mins. It was compiled with -O2. Have you got a very very fast machine? If so then I think Perl with ugly-memoize beats the C, which is very surprising.

Replies are listed 'Best First'.
Re^8: Challenge: Number of unique ways to reach target sum
by Limbic~Region (Chancellor) on Feb 15, 2006 at 21:10 UTC
    fergal,
    I compiled with the following optimizations:
    gcc -Wall -march=pentium4 -s -funroll-loops -fomit-frame-pointer -O3 l +oops.c -o loops.exe
    When you say that you were able to generate all the solutions in Perl in 74 mins on 1 machine was it using blokhead's code without Memoize or your modification to that code? I ask because then we would be comparing apples and oranges. I had a completely different algorithm.

    Cheers - L~R

    Update: Added second hyphen to -fomit-frame-pointer

      My modified code. Blockhead's used memo for counting but not for generation. I suspect that without memoize blokhead's code would take hours or days.

      So we're comparing apples to oranges which is perfectly legitimate if you want to find out whether apples are faster than oranges :).

      As far as I can tell my Perl is faster than your C. So (for a sanity check) if you run blokhead's memoized counting code on your machine (the machine that takes 72 mins for the C) how long does it take?

        fergal,
        As far as I can tell my Perl is faster than your C. So (for a sanity check) if you run blokhead's memoized counting code on your machine (the machine that takes 72 mins for the C) how long does it take?

        Ok - I will assume I am just being dense here. When you say that you suspect your Perl is faster than my C, I presume you are talking about this code. I modified it slightly as to not penalize it for IO. IOW, I made it go through the solutions without actually printing them. It has been running for 4 1/2 hours on the same machine that my C code takes 72 minutes to complete on and is still not finished.

        When you ask me to run blokhead's memoized counting code on the same machine as the one that completes the C code in 72 minutes, I am not sure why you would want me to do this. I presume it will finish in 10 seconds or less since it isn't actually going through the solutions.

        I am not trying to be unhelpful here but I just don't get at what you are trying to get me to test. Any code that I have tested that actually goes through the solutions (without printing them) takes so long I give up on including your code I linked to. What am I missing?

        Cheers - L~R

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://530521]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (2)
As of 2024-03-19 05:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found