php function perform very slow over large chunk of data and output. How to make it fast without changing php.ini or max_execution_server setup

Question

I have large indexed array where element of array can vary from 1 to 2*10^5 and php function goes out of Max_execution_timeout. how to make it fast or make it work properly without making changes in any other document directly (if there is a way to make execution time more within function). function working properly with small chunk of data.

here is the file attached https://drive.google.com/file/d/1egyzLQWV69IDKjbMzS1ZG3e-bPy3qjjM/view?usp=sharing

<?php
 // $count = array of element

function activityNotifications($expenditure, $d) {

    $size = sizeof($expenditure);
    $count = 0 ;
    for($i=0;$i<$size-$d;$i++){
        $median = array();
        for($k=0;$k<$d;$k++){ 
            $median[$k] = $expenditure[$i+$k];
        }
        sort($median);

        if($d%2 == 1){
            $middle = $median[floor($d/2)];
        } else if($d%2 == 0){ 
            $value = $d/2;
            $middle = $median[$value] + $median[$value-1];
            $middle = $middle/2;
        }
        $value = $middle*2;

        if($value<=$expenditure[$d+$i]){
            $count++;
        }
    }
    return $count;
}

echo activityNotifications($count2,$d);

?>

Answer 1

Since $d acts like a constant in this function, a general improvment is extract fixed data outside the loop.

The important part I think is declare $median once, and reuse it, this may reduce some GC overhead.

function activityNotifications($expenditure, $d)
{
    $size = sizeof($expenditure);
    $count = 0 ;
    $median = array_fill(0, $d, 0); #create an array with predefined size
    $d_divide_by_2 = $d/2;
    $d_divide_by_2_int = floot($d_divide_by_2);

    if($d%2 == 1)
    {
        for($i=0;$i<$size-$d;$i++)
        {
            for($k=0;$k<$d;$k++)
            { 
                $median[$k] = $expenditure[$i+$k];
            }
            sort($median);

            $value = $median[$d_divide_by_2_int]*2;

            if($value<=$expenditure[$d+$i]){
                $count++;
            }
        }
    }
    else
    {
        for($i=0;$i<$size-$d;$i++)
        {
            for($k=0;$k<$d;$k++)
            { 
                $median[$k] = $expenditure[$i+$k];
            }
            sort($median);

            $value = $median[$d_divide_by_2] + $median[$d_divide_by_2-1];

            if($value<=$expenditure[$d+$i]){
                $count++;
            }
        }
    }

    return $count;
}

Answer 2

Some suggestions for improving the performance are:

Instead of:

for($k=0;$k<$d;$k++){ 
    $median[$k] = $expenditure[$i+$k];
}

Use:

$median = array_slice($expenditure, $i, $d);

In general array functions will be quicker than loops.

Another different idea is to reduce the cost of the sort() function. You can do this by maintaining the $median array mostly sorted throughout. So instead of taking a slice each time, you push one value on and pull one value off. Something like:

$median[$i+$d] = $expenditure[$i+$d]; // append a value
unset($median[$i]); // remove a value

Then use asort to sort and maintain the key associations:

asort($median);

In essence $median will always be a window into $expenditure of size d, and maintains key associations. You can initialise your $median from the outset by first taking the a slice using: $median = array_slice($expenditure, $i, $d); outside of the loop.

So very roughly (not tested myself):

function activityNotifications($expenditure, $d) {

    $size = sizeof($expenditure);
    $count = 0 ;
    $median = array_slice($expenditure, 0, $d, TRUE); // initial slice with keys
    for($i=$d;$i<$size;$i++){

        $median[$i]=$expenditure[$i];
        unset($median[$i-$d]);
        asort($median);

        $median_values = array_values($median);
        if($d%2 == 1){
            $middle = $median_values[floor($d/2)];
        } else if($d%2 == 0){ 
            $value = $d/2;
            $middle = $median_values[$value] + $median_values[$value-1];
            $middle = $middle/2;
        }
        $value = $middle*2;

        if($value<=$expenditure[$d+$i]){
            $count++;
        }
    }
    return $count;
}

Note the above code won't work directly, because when you extract your midpoint value, the keys won't be in order. So you may need to use array_values first (I've added this above).