Quick actions

cmd+k|ctrl+k

Navigation

Languages

How to break nest loop (bench solutions)

Snippet info

Language

Php

Visibility

public

Author

zjmainstay

Created

2016-07-12T02:32:43Z

Updated

2016-07-12T03:00:26Z

<?php

    //Problem: When the investList run up to 10000, the loop times can be 10000*10000=100000000, how to optimize this?

    //create test data
    $investList = [];
    $times = 5000;
    for($i = 1; $i <= $times; $i++) {
        $investList[] = [
                'id'    => $i,
                'cash'  => mt_rand(1, 10000),
            ];
    }
    
    echo 'Run Times: ' . $times, "\n";
    
    //copy a investList as refundList but shuffle it
    $refundList = $investList;
    shuffle($refundList);
    
    //nest loop solution bench
    $refundList1 = $refundList;
    bench();
    foreach($refundList1 as $index => $refund) {
        foreach($investList as $invest) {
            if($invest['id'] == $refund['id']) {
                $refundList1[$index]['invest_cash'] = $invest['cash'];
            }
        }
    }
    echo 'Execute Time(nest loop): ' . bench(), "\n";
    
    //break nest loop solution bench
    $refundList2 = $refundList;
    bench();
    $investList = array_combine(array_column($investList, 'id'), $investList);
    foreach($refundList2 as $index => $refund) {
        #foreach($investList as $invest) {
            #if($invest['id'] == $refund['id']) {
            if(isset($investList[$refund['id']])) {
                $invest = $investList[$refund['id']];
                $refundList2[$index]['invest_cash'] = $invest['cash'];
            }
            #}
        #}
    }
    echo 'Execute Time(break nest loop): ' . bench(), "\n";
    
    //check two solution's result match in the end
    $result = (md5(print_r($refundList1, true)) === md5(print_r($refundList2, true))) ? 'true' : 'false';
    echo 'Result Match: ' . $result, "\n";
    
    // print_r($refundList1);
    // print_r($refundList2);
    
    //output an item to check its struct
    echo 'Last Item: ';
    print_r(array_pop($refundList1));
    print_r(array_pop($refundList2));
    
    //Solution: https://glot.io/snippets/eggpzzp1tm
    
    /**
     * first call bench() store start time
     * second call bench() get runtime from last time and reset start time
     * @example
     bench();   //start
     for($i = 0; $i < 1e6; $i++) {
        //do something
     }
     echo 'Execute Time: ' . bench();
     */
    function bench() {
        static $start;
        if (! $start) {
            $start = microtime(true);
            return;
        }
        $duration = microtime(true) - $start;
        $start = 0;
        return $duration;
    }
INFO