5
\$\begingroup\$

I am writing one logic to iterate numbers first and then additional logic to putting them into particular subset of array.

What does this code do:

  1. Code accept first $n
  2. It creates an array of $n number from 1 to $n
  3. Then started converting to subset of $main_array to possible one like ['1'] [1,2] [1,2,3] [2] [2,3] [3] etc. same like this
  4. After creating subset i am counting those some subset which satisfy condition
  5. Condition is xyz[0] should not come in subset with abc[0] and xyz[i] should not come in subset abc[i]. Example 2 and 3 is coming subset then don't count that subset, same 1 and 4 is coming then don't count.

Here is my nested for loop:

$n = 1299;
$main_array = range(1,$n); 
$counter = 0; 
$count = sizeof($abc);  // $abc and $xyz size will same always. 
$abc = [2,1];
$xyz = [3,4];

for ($i=0; $i <$n; $i++) {  
         for($j = $i;$j < $n; $j++){  
            $interval_array = array();
          for ($k = $i; $k <= $j; $k++){
                array_push($interval_array,$main_array[$k]);
          }
           $counter++;
           for ($l=0; $l < $count ; $l++) {
                //if block here to additional condition using in_array() php function. which do $counter--
                if(in_array($abc[$l], $interval_array) && 
                 in_array($xyz[$l], $interval_array)){ 
                     $counter--;
                     break;
                 } 
             } 
         }
    }

$main_array I have to create on the spot after receiving $n values.

Following is cases:

  1. when running $n = 4 its run in 4s
  2. when running $n = 1200 or 1299 or more than 1000 its run in 60s-123s

Expected execution timing is 9s. I reduce from 124s to 65s by removing function calling inside for loop but it's not coming to point.

Expectation of code is if I have an array like:

$array = [1,2,3];

Then subset need to generate:

[1],[1,2],[1,2,3],[2],[2,3],[3]

Any help in this?

\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

I've seen this on SO, but only realised the biggest optimisation today.

The first optimization is to not build the $interval_array array in each iteration. This code starts with the empty array and then in each loop just adds the next number in sequence to this array.

for ($i=0; $i <$n; $i++) {
    // Reset array in outer loop
    $interval_array = array();
    for($j = $i;$j < $n; $j++){
        // Add in new number to interval array as the key
        $interval_array[$main_array[$j]] = 0;

So the first time round it will add be [1], then on the second loop it add the next number in and will be [1,2] etc. (although they are actually [1=>0], [1=>0, 2=>0] the principle is the same)

The main difference is note that it adds the number as the key of the array and not the value. This allows the main optimization which is when you are checking if you want to exclude particular combinations in...

        if(in_array($abc[$l], $interval_array) && 
         in_array($xyz[$l], $interval_array)){ 

it will look through (up to) the entire array twice to check for the values.

If instead you had the values as the key, you could use isset()...

            if(isset($interval_array[$abc[$l]]) &&
                isset($interval_array[$xyz[$l]]))   {

This is much more efficient at just checking a value exists.

The last thing I've added is that I create an array with all of the numbers you are checking against in (use array_flip() to again make these numbers the keys)...

$interest = array_flip(array_merge($abc, $xyz));

This allows me to check if the number is even something I'm interested in before running the more detailed checks...

    if ( isset($interest[$main_array[$j]] )) {

Put all of this together...

$n = 1299;
$start = microtime(true);
$main_array = range(1,$n);
$counter = 0;
$abc = [2,1];
$xyz = [3,4];
$count = sizeof($abc);  // $abc and $xyz size will same always.

// Create a combined array which lists all the numbers interested in
$interest = array_flip(array_merge($abc, $xyz));
for ($i=0; $i <$n; $i++) {
    // Reset array in outer loop
    $interval_array = array();
    for($j = $i;$j < $n; $j++){
        // Add in new number to interval array as the key
        $interval_array[$main_array[$j]] = 0;
        $counter++;
        // Only check for exclusion if interested in the number
        if ( isset($interest[$main_array[$j]] )) {
            for ($l=0; $l < $count ; $l++) {
                // if block here to additional condition using isset()
                if(isset($interval_array[$abc[$l]]) &&
                    isset($interval_array[$xyz[$l]]))   {
                        $counter--;
                        // Exit 2 levels of array as all further combinations will be excluded
                        break 2;
                }
            }
        }
    }
}

echo $counter."=".(microtime(true)-$start);

On my laptop (i7-3632QM, 8GB) the results of running this for 1299 are

original code...

841756=206.25858306885

modified code...

841756=0.34013700485229
\$\endgroup\$
1
  • \$\begingroup\$ for 120000 number getting time out while executing. I am trying this case in hackerrank. @nigel-ren \$\endgroup\$ Jan 3, 2020 at 7:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.