XP is just a number | |
PerlMonks |
Re^3: Challenge: Number of unique ways to reach target sumby fergal (Chaplain) |
on Feb 15, 2006 at 03:03 UTC ( [id://530287]=note: print w/replies, xml ) | Need Help?? |
When I came back it was using 500M of memory (growing very very slowly) and was clocking 1.9M answers per second which puts it at a total time between 2 and 3 hours. Which isn't bad. I'm leaving it running overnight on a machine to verfiy that. By the way, to store the answers would require > 400GB of space! The code below has functions. string_ways() generates an array of strings from a tree of ways of summing things, it's memoized. nasty_print_ways() is like print_ways() but it also takes a depth. When it reaches that depth it starts making calls to string_ways() to get lists of strings to finish off the current way. This avoids recomputing a lot of stuff. You can adjust the depth if you have more or less memory but I think a change of 1 results in about a 100-fold difference in memory usage. This dumps out performance other stats every million lines. You get how many have been printed, how many times string_ways was called, how many times it was really called (that is the memoization didn't help us) and a rate of lines/CPU second
In Section
Seekers of Perl Wisdom
|
|