Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Re^3: possible combinations in sequence

by roboticus (Canon)
on Jun 09, 2006 at 12:10 UTC ( #554479=note: print w/ replies, xml ) Need Help??


in reply to Re^2: possible combinations in sequence
in thread possible combinations in sequence

ikegami:

Thanks for the tip on the speed boost. Once I get the benchmarking stuff installed I'll play with it. While I do like your suggestion, I prefer the order that my method generates--all one-word combinations first, then the two-word combinations, etc.)

Re: shoddy code. Yeah, I guess so, consider me properly admonished. ++ for calling me on it and keeping me honest. When I thunk up the technique to use, I just erased the original function body and started whacking away at it. I didn't think to clarify things by using better variable names. (Of course, I just came off of a little golfing trip so my head was in "trim keystrokes" mode.</lame_excuse_mode>) Now, I guess the proper thing to do is to clean it up a little and insert your suggestion, so here goes:

<pedagogical_mode>

sub function { my @parts = split /:/, shift; # Null is the complete list of combinations for # an empty word list my @combinations=(); # Sequentially (recursively with tail recursion # removed) rebuild the combination list adding one # new word each iteration for my $new_word (@parts) { # Given a complete set of combinations for a # given list of words, we can add a new word to # the list and generate all new valid combinations # by concatenating to the original list: push @combinations, # the new word (a single word is a valid # combination) $new_word, # and the original list with the new word # glommed onto the end of each member map {$_.':'.$new_word} @combinations ; } return @combinations; }
</pedagogical_mode>

--roboticus


Comment on Re^3: possible combinations in sequence
Download Code
Re^4: possible combinations in sequence
by ruzam (Curate) on Jun 09, 2006 at 14:15 UTC
    Just when you thought it couldn't get any faster...
    Here's a comparison of the revised roboticus version (with ikegami's speed suggestion):
    source: horse:cow:dog:cat Rate ruzam roboticus roboticus2 ruzam 4695/s -- -80% -86% roboticus 23049/s 391% -- -33% roboticus2 34607/s 637% 50% -- source: horse Rate ruzam roboticus2 roboticus ruzam 64954/s -- -71% -76% roboticus2 223392/s 244% -- -16% roboticus 266354/s 310% 19% -- source: horse:cat Rate ruzam roboticus roboticus2 ruzam 26625/s -- -72% -76% roboticus 96711/s 263% -- -13% roboticus2 111706/s 320% 16% -- source: horse:cow:cat Rate ruzam roboticus roboticus2 ruzam 11023/s -- -77% -82% roboticus 46987/s 326% -- -24% roboticus2 62225/s 465% 32% -- source: horse:cow:dog:cat:mouse Rate ruzam roboticus roboticus2 ruzam 1913/s -- -82% -89% roboticus 10826/s 466% -- -39% roboticus2 17652/s 823% 63% -- source: horse:cow:dog:cat:rat:mouse Rate ruzam roboticus roboticus2 ruzam 798/s -- -85% -91% roboticus 5253/s 559% -- -43% roboticus2 9221/s 1056% 76% --

    The new function is now an magnitude faster than my original attempt. That's no small change. Is this the limit of optimizing or can yet more juice be squeezed out of this function?
      Well ... I've tried a few things off and on for a couple of days. I can't make it one whit faster.

      I've found a good few ways to make it slower, though! 8^)

      --roboticus

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (7)
As of 2014-09-18 22:24 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (125 votes), past polls