PHP循环 - 运行时 - 非常高级的微调 - 计算混合比率

Question

I want to calculate blending ratios, but I have runtime problems, It seems 7 components with a precision of 4% are the limit in PHP ... So I try to find a way to avoid superfluous loops, to calculate faster.

I have ingredients and a limit (here 6). I want find all combinations lower than 6. In a secound step (not shown here) I just order these hits after price. I would like to find the cheapest combination with ingredient_x lower than 6.

I try two ways, to do this, just simple sum the ingredients, and step by step, to abort the loops early (to safe loops).

<?php

    $beginn = microtime(true);
    $loops = 0;
    $hits = 0;

    $m =  array();

    // 1. TEST
    $component[0]['ingredient_x'] = 6.95;
    $component[1]['ingredient_x'] = 65.7;
    $component[2]['ingredient_x'] = '';
    $component[3]['ingredient_x'] = 2;
    $component[4]['ingredient_x'] = '';
    $component[5]['ingredient_x'] = '';
    $component[6]['ingredient_x'] = '';

    /*
    Results:

        With abort Loops
            Loops: 285.188
            Hits: 285.077
            Seconds: 1,707 sec.

        Without:
            Loops: 736.281
            Hits: 285.077
            Seconds: 6,582 sec.
    */

    // 2. TEST
    $component[0]['ingredient_x'] = 6.95;
    $component[1]['ingredient_x'] = 6.7;
    $component[2]['ingredient_x'] = '';
    $component[3]['ingredient_x'] = 2;
    $component[4]['ingredient_x'] = '';
    $component[5]['ingredient_x'] = '';
    $component[6]['ingredient_x'] = '';

    /*
    Results:

        With abort Loops
            Loops: 735.244
            Hits: 735.167
            Seconds: 4,467 sec.

        Without:
            Loops: 736.281
            Hits: 735.167
            Seconds: 3,191 sec.
    */


    $abort_loops = 1;


    for ($m[0] = 0; $m[0] <= 100;                                                   $m[0] += 4) {
    for ($m[1] = 0; $m[1] <= (100 - $m[0]);                                         $m[1] += 4) {
    for ($m[2] = 0; $m[2] <= (100 - $m[0] - $m[1]);                                 $m[2] += 4) {
    for ($m[3] = 0; $m[3] <= (100 - $m[0] - $m[1] - $m[2]);                         $m[3] += 4) {
    for ($m[4] = 0; $m[4] <= (100 - $m[0] - $m[1] - $m[2] - $m[3]);                 $m[4] += 4) {
    for ($m[5] = 0; $m[5] <= (100 - $m[0] - $m[1] - $m[2] - $m[3] - $m[4]);         $m[5] += 4) {
                    $m[6]  = (100 - $m[0] - $m[1] - $m[2] - $m[3] - $m[4] - $m[5]);

        $loops++;

        if ($abort_loops) {

            $r = 0;
            $do_break = 0;

            // Checking ingredient_x sum, component by component
            for ($i = 0; $i <= 6; $i++) {
                $r += ($m[$i] * ($component[$i]['ingredient_x'] / 100));

                // If Limit is reached, end all following loops
                if ($r > 6) {
                    $m[$i] = 100;
                    // Cant break here, because of inner loop ...
                    $do_break = 1;
                }
            }
            // ... so do it outside
            if ($do_break) {
                break;
            }

            $hits++;

        } else {

            // just sum ingredient_x
            $r = ($m[0] * ($component[0]['ingredient_x'] / 100)) +
                      ($m[1] * ($component[1]['ingredient_x'] / 100)) +
                      ($m[2] * ($component[2]['ingredient_x'] / 100)) +
                      ($m[3] * ($component[3]['ingredient_x'] / 100)) +
                      ($m[4] * ($component[4]['ingredient_x'] / 100)) +
                      ($m[5] * ($component[5]['ingredient_x'] / 100)) +
                      ($m[6] * ($component[6]['ingredient_x'] / 100));

            if ($r <= 6) {
                $hits++;
            }
        }

    }
    }
    }
    }
    }
    }

    print('Loops: ' . number_format($loops, 0, '', '.') . '<br>');
    print('Hits: ' . number_format($hits, 0, '', '.') .  '<br>');
    print('Seconds: ' . number_format((microtime(true) - $beginn), 3, ',', '') . ' sec.');



?>

But this depends very on the ingredients. As you can see in Test 1 (abort loops is 5 times faster) and Test 2 (the simple sum way is faster).

Is it possible to make these loop faster? Better "abort loop" code? Is there a faster way to find the cheapest combination?

Answer 1

One approach is to use simple math to improve your summing up:

// just sum ingredient_x
$r = (
          $m[0] * $component[0]['ingredient_x'] +
          $m[1] * $component[1]['ingredient_x'] +
          $m[2] * $component[2]['ingredient_x'] +
          $m[3] * $component[3]['ingredient_x'] +
          $m[4] * $component[4]['ingredient_x'] +
          $m[5] * $component[5]['ingredient_x'] +
          $m[6] * $component[6]['ingredient_x']
    );
;

if ($r <= 600) {
    $hits++;
}

Allt thos divisons by 100 can be completely dropped if you simply raise your limit to 100 times your limit.

a0 / 100 + a1 / 100 + a2/100 + ... a6/100

is the same as

(a0 + a1 + a2 + ... + a6) /100

This will just need one division instead of 7.

Even this division can be avoided if you adjust your limit to 100 * your limit.

Speed improvement on my machine is about 10-15%.