Lots of foreach with over 37 million features

Question

I was tasked with creating a list of all the features using data in 8 blocks.

8 blocks have the following number of features:

*Block 1: 12 possibilities *Block 2: 8 possibilities *Block 3: 8 possibilities *Block 4: 11 possibilities *Block 5: 16 possibilities *Block 6: 11 possibilities *Block 7: 5 possibilities *Block 8: 5 possibilities 

This gives a potential number of 37,171,200 possibilities.

I tried just doing and restricting only the display of return values ​​with the correct string length as follows:

 foreach($block1 AS $b1){ foreach($block2 AS $b2){ foreach($block3 AS $b3){ foreach($block4 AS $b4){ foreach($block5 AS $b5){ foreach($block6 AS $b6){ foreach($block7 AS $b7){ foreach($block8 AS $b8){ if (strlen($b1.$b2.$b3.$b4.$b5.$b6.$b7.$b8) == 16) { echo $b1.$b2.$b3.$b4.$b5.$b6.$b7.$b8.'<br/>'; } } } } } } } } } 

However, the runtime was too long to calculate. I was wondering if anyone knows of a simpler way to do this?

Answer 1

You can improve your algorithm by caching string prefixes and remember their length. Then you do not need to do this for each combination.

 $len = 16: // array for remaining characters per level $r = array($len); // array of level parts $p = array(); foreach ($block1 AS &$b1) { // skip if already too long if (($r[0] - strlen($b1)) <= 0) continue; $r[1] = $r[0] - strlen($b1); foreach ($block2 AS &$b2) { if (($r[1] - strlen($b2)) <= 0) continue; $r[2] = $r[1] - strlen($b2); foreach ($block3 AS $b3) { // … foreach ($block8 AS &$b8) { $r[8] = $r[7] - strlen($b8); if ($r[8] == 0) { echo implode('', $p).'<br/>'; } } } } } 

Also, using references in foreach will stop PHP using an internal copy of the array.

Answer 2

You can try to save the previously calculated part in the concatenated line, known in each of the previous leels, for subsequent reuse, avoiding the concatenation of everything in the innermost loop

 foreach($block7 AS $b7){ $precomputed7 = $precomputed6.$b7 foreach($block8 AS $b8){ $precomputed8 = $precomputed7.$b8 if (strlen($precomputed8) == 16) { echo $precomputed8.'<br/>'; } } } 

Doing this is similar for use case levels. Then you can try testing at one of the higher loop levels for strings that are already longer than 16 characters. You can use the shortcut and avoid other features. But be careful when calculating the length of a string, it costs a lot of performance, maybe the last improvement is not worth it at all, depending on the input.

Another idea is to pre-calculate the lengths for each block, and then recurse over an array of lengths, calculating the sums should be faster than concatenating and calculating the length of the strings. For Vector indexes that match a length of 16, you can easily output the full concatenated string.

Answer 3

Since you have a length requirement of 16 and assuming that each (i) opportunity in each (b) of the eight blocks is x_i_b in length, you may get some reduction when some cases become impossible.

For example, let's say we have a requirement of length 16, but only 4 blocks, with capabilities with specified lengths

block1: [2,3,4] block2: [5,6,7] block3: [8,9,10] block4: [9,10,11]

Then all possibilities are impossible, since the lengths of block 4 are too long for any combination of blocks 1 to 3 to comprise the rest of 16.

Now, if you have a length, this is really 16, which means that your (possible) lengths range from 1 to 9 if the length is not long.

I see two ways to approach this:

• Greedy
• Dynamic programming

Perhaps even combine them. For the “Greedy” approach, select the largest opportunity in all blocks, then the next largest, etc. Follow this until you pass threshold 16. If you have received all the blocks, you can emit this.

Whether you get the threshold or not, you can iterate over the possibilities.

Dynamic evaluation means that you must save some of the results that you have already calculated. As a choice of some blocks that give you a length of 7, you do not need to re-comment this in the future, but you can iterate over the remaining blocks to see if you can find a combination to give you the tenth of 9.

EDIT . This is similar to a backpack problem, but with an additional restriction of 1 choice per block in each instance. In any case, from the point of view of other optimizations, definitely pre-process blocks only in arrays of lengths and save the current amount at each iteration level. Thus, you should only make 1 amount for each iteration of each cycle, and not 8 amounts for each iteration. Also only str concat if you need to select a selection.

If you don’t need a general solution (perhaps easier if you don’t), you can compose the code with special accelerations of the problem instance by excluding the largest too small combination of lengths (and all choices are shorter than this) and excluding the smallest too large combination of lengths ( and all the choices are bigger).

Answer 4

If you can express this as a nested array, try RecursiveIteratorIterator, http://php.net/manual/en/class.recursiveiteratoriterator.php