 more useful options PerlMonks

Re: Variable number of foreach loops (non-recursive solution)

by smls (Friar)
 on Nov 28, 2013 at 17:44 UTC ( #1064853=note: print w/replies, xml ) Need Help??

in reply to Variable number of foreach loops

Non-recursive solution

For completeness, here's a solution that does not use a recursive subroutine:

sub nested_foreach(&@) { my \$code = shift; my @indices = map { 0 } @_; # First set of indices is all zeroes my @sizes = map { scalar @\$_ } @_; # Cache array sizes (optional) my \$k; do { # Determine the array elements corresponding to the current set # of indices, and pass them to the closure: \$code->( map { \$_[\$_][\$indices[\$_]] } 0..\$#_ ); # Determine the next set of indices: for (\$k = \$#_; \$k >= 0; \$k--) { \$indices[\$k]++; if (\$indices[\$k] < \$sizes[\$k]) { last; } else { \$indices[\$k] = 0; } } # If \$k went out-of-bounds, there are no more valid iterations: } while (\$k >= 0); } my @a = ...; my @b = ...; my @c = ...; nested_foreach { say join ' ', @_ } \@a, \@b, \@c;

The "Determine the next set of indices" step may seem a little complicated at first sight, but it becomes more intuitive if you think of the @indices array as an integer number (with each element representing a digit), and imagine that we want to "increment" that "number" by 1. It's not a decimal (i.e. base-10) number, but rather one where each digit can have a different base (i.e. the sizes of the input arrays) - but that doesn't really change anything.

Incrementing the "number" by 1 works just like the integer addition (here with an addend of 1) that you were taught back in primary school: Start with the right-most digit; increment it; if it's still within the valid range of digits then you're done; if instead it went above the limit then wrap it around to zero, "carry the one", and repeat the same steps with the next digit to the left.

Update:

Performance comparison

Interestingly, my iterative solution seems to be significantly slower than BrowserUK's recursive solution, at least when running on my PC and with various different numbers/sizes of input arrays I tried:

sub nested_foreach(&@) { ... # see above } sub nForX(&@) { ... # see BrowserUK's post } # my @size = (500, 900); # my @size = (5, 5, 5, 5, 5, 5, 5, 5); my @size = (100, 4, 75, 23); my @AoA = map { [map { chr(\$_+64) x int(rand(10)) } 1 .. \$_] } @size; cmpthese -10, { iterative => sub { nested_foreach { join("", @_) } @AoA }, recursive => sub { nForX { join("", @_) } scalar @AoA, @AoA }, };
s/iter iterative recursive iterative 1.86 -- -71% recursive 0.532 249% --

Replies are listed 'Best First'.
Re^2: Variable number of foreach loops (non-recursive solution)
by abhay180 (Sexton) on Nov 29, 2013 at 09:48 UTC
Thanks a lot. That helps.

Just in case performance is a consideration:

#! perl -slw use strict; use Algorithm::Loops qw[ NestedLoops ]; use Time::HiRes qw[ time ]; sub nFor(&@) { my \$code = shift; my @indices = map { 0 } @_; # First set of indices is all zeroes my @sizes = map { scalar @\$_ } @_; # Cache array sizes (optional) my \$k; do { # Determine the array elements corresponding to the current se +t # of indices, and pass them to the closure: \$code->( map { \$_[\$_][\$indices[\$_]] } 0..\$#_ ); # Determine the next set of indices: for (\$k = \$#_; \$k >= 0; \$k--) { \$indices[\$k]++; if (\$indices[\$k] < \$sizes[\$k]) { last; } else { \$indices[\$k] = 0; } } # If \$k went out-of-bounds, it means we're finished: } while (\$k >= 0); } sub nForX(&@) { my \$code = shift; my \$n = shift; return \$code->( @_ ) unless \$n; for my \$i ( @{ shift() } ) { &nForX( \$code, \$n-1, @_, \$i ); } } my %stuff = ( A => [ 1..1000 ], B => [ 'a'..'z', 'A'..'Z' ], C => [ map chr, 33..47, 58..64, 92..96 ], ); my \$start; for my \$pat ( qw[ A::B A::C B::C A::B::C ] ) { print "\nProcessing \$pat"; my @keys = split '::', \$pat; \$start = time; nForX { my @set = @_; } scalar @keys, @stuff{ @keys }; printf "\tRecursive: %f seconds\n", time - \$start; \$start = time; nFor { my @set = @_; } @stuff{ @keys }; printf "\tIterative: %f seconds\n", time - \$start; \$start = time; NestedLoops [ @stuff{ @keys } ], sub { my @set = @_; }; printf "\tNestedLoops %f seconds\n", time - \$start; } __END__ C:\test>nforx Processing A::B Recursive: 0.107126 seconds Iterative: 0.227112 seconds NestedLoops 0.474461 seconds Processing A::C Recursive: 0.049802 seconds Iterative: 0.117263 seconds NestedLoops 0.235748 seconds Processing B::C Recursive: 0.002990 seconds Iterative: 0.006834 seconds NestedLoops 0.014829 seconds Processing A::B::C Recursive: 3.072954 seconds Iterative: 7.725672 seconds NestedLoops 15.938471 seconds

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1064853]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (4)
As of 2022-01-21 18:37 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In 2022, my preferred method to securely store passwords is:

Results (59 votes). Check out past polls.

Notices?