Performance with time related algorithm

Question

I have a function that take 2 arrays ($schedule, $remove), both are arrays of days with time inside, it will remove time from the schedule .

Now this function is working fine if I have between 1 & 20 user it takes 2-4 seconds to generate the calendar which is fine but when having 20+ user with a lot of schedules entries it goes to 15+ seconds.

I'm working with CodeIgniter and I have this function in a helper where it's called a lot.

So I wanted to know if you guys can see any better way to deal with my problem or adjustments that I make to my algorithm to make it faster.

Note: In my code below, the big problem I see is the recursive call and the break of the loop every time I modify the structure.

I loop on both arrays and do test to see if the absence is inside/overlap/equal/outside of the availability and then recall the function if the structure was modified if not return the final structure.

Note 2 :

On local the Apache crash because the recursive function sometime is called more than 100 times .

Here is the code I have :

   function removeSessionsFromSchedule($schedule, $remove) {

    $modified = false;
    if (is_array($schedule) && count($schedule) > 0 && is_array($remove) && count($remove) > 0 && checkArrayEmpty($remove)) {

        // Minimise the iterations
        $remove = minimiseRemoveSchedule($remove);
        foreach ($schedule as $s => $dispo) {

            if ($modified) {
                break;
            }

            $pos        = 0;
            $countdispo = count($dispo);

            foreach ($dispo as $d) {

                $abs = isset($remove[$s]) ?  $remove[$s] :null;
                $counter = 0;
                // availability start/end
                $dis_s = strtotime($d['heure_debut']);
                $dis_e = strtotime($d['heure_fin']);
                if (is_array($abs) && count($abs) > 0) {
                    foreach ($abs as $a) {
                        // absence start/end
                        $abs_s = strtotime($a['heure_debut']);
                        $abs_e = strtotime($a['heure_fin']);
                        // Tests to see the if there is overlap between absence and availability
                        // (2) [a_s]---[ds - de]---[a_e]
                        if ($abs_s <= $dis_s && $abs_e >= $dis_e) {
                            // delete availability
                            unset($schedule[$s][$pos]);
                            $modified = true;
                            break;
                        }
                        // (7)[as == ds] && [ae < de]
                        else if ($abs_s == $dis_s && $abs_e < $dis_e) {
                            unset($schedule[$s][$pos]);
                            $schedule[$s][$pos] = $d;
                            $schedule[$s][$pos]['heure_debut'] = date("H:i", $abs_e);
                            $schedule[$s][$pos]['heure_fin'] = date("H:i", $dis_e);
                            $modified = true;
                            break;
                        }
                        // (6) [ds -de] --- [as  ae] return dispo as is
                        else if ($abs_s >= $dis_e) {
                            unset($schedule[$s][$pos]);
                            $schedule[$s][$pos] = $d;
                            $modified ?: false;
                        }
                        // (5)[as  ae] [ds -de] ---  return dispo as is
                        else if ($abs_e <= $dis_s) {
                            unset($schedule[$s][$pos]);
                            $schedule[$s][$pos] = $d;
                            $modified ?: false;
                        }
                        // (1)[ds] --- [as] --- [ae] --- [de] (duplicate dis with new times)
                        else if ($abs_s > $dis_s && $abs_e <= $dis_e) {
                            // new times as : // s1 = ds-as &&  s2 = ae-de
                            unset($schedule[$s][$pos]);
                            $schedule[$s][$pos] = $d;
                            $schedule[$s][$pos + 1] = $d;

                            $schedule[$s][$pos]['heure_debut'] = date("H:i", $dis_s);
                            $schedule[$s][$pos]['heure_fin'] = date("H:i", $abs_s);
                            $schedule[$s][$pos + 1]['heure_debut'] = date("H:i", $abs_e);
                            $schedule[$s][$pos + 1]['heure_fin'] = date("H:i", $dis_e);

                            // a revoir si ca ne cause pas d'autre problem qu'on fasse pos++ ...
                            $pos++;

                            $modified = true;
                            break;
                        }
                        // (3)[as] -- [ds] --- [ae] -- [de]
                        else if ($abs_s < $dis_s && $abs_e < $dis_e) {
                            unset($schedule[$s][$pos]);
                            $schedule[$s][$pos] = $d;
                            $schedule[$s][$pos]['heure_debut'] = date("H:i", $abs_e);
                            $schedule[$s][$pos]['heure_fin'] = date("H:i", $dis_e);
                            $modified = true;
                            break;
                        }
                        // (4) [ds]---[as]--- [de]--- [ae]
                        else if ($abs_s > $dis_s && $abs_s < $dis_e && $abs_e > $dis_e) {
                            unset($schedule[$s][$pos]);
                            $schedule[$s][$pos] = $d;
                            $schedule[$s][$pos]['heure_debut'] = date("H:i", $dis_s);
                            $schedule[$s][$pos]['heure_fin'] = date("H:i", $abs_s);
                            $modified = true;
                            break;
                        } else {
                            $modified ?: false;
                        }
                    }

                    // if($modified == true) { break;}


                } else {
                    $modified = false;
                }
                $pos++;
            }
        }
    } else {
        $modified = false;
    }

    if ($modified) {
        $schedule = resetIndexes($schedule);
        $schedule = sortByTime($schedule);
        $schedule = removeSessionsFromSchedule($schedule, $remove);
    }

    return $schedule;
}

Related Helpers

function checkArrayEmpty($array) {
    if(is_array($array) && !empty($array)) {
        foreach($array as $arr) {
            if(is_array($arr) && !empty($arr)) {
                return true;
            }
        }
    }
    return false;
}

function subval_sort_by_time($a, $subkey) {
    if (is_array($a) && count($a) > 0) {
        foreach ($a as $k => $v) {
            $b[$k] = strtotime($v[$subkey]);
        }
        asort($b);
        foreach ($b as $key => $val) {
            $c[] = $a[$key];
        }
        return $c;
    }
    else
        return $a;
}



// Reset Index function 
function resetIndexes($array) {
        $new = array();
        foreach($array as $date => $arr) {
            //$new[$date]= array_values($arr);
            $new[$date]= array_merge(array(),$arr);
        }
        return $new;
    }

// sort by time
function sortByTime($array) {
    $sorted = array();
    if(is_array($array) && !empty($array)){
        foreach ($array as $s => $val) {
            $sorted[$s] = subval_sort_by_time($val, 'heure_debut');
        }
    }
    return $sorted;
  }


 function minimiseRemoveSchedule($array) {
    $new = array();
    foreach($array as $date => $arr) {
        $i=0;
        if(is_array($arr) && !empty($arr)) {

            foreach($arr as $a) {

                if(isset($new[$date][$i])) {
                    if($new[$date][$i]['heure_fin'] == $a['heure_debut']) {
                        $new[$date][$i]['heure_fin']  = $a['heure_fin'];
                    }
                    else {
                        $i++;
                        $new[$date][$i]['heure_debut'] = $a['heure_debut'];
                        $new[$date][$i]['heure_fin']   = $a['heure_fin'];
                    }

                } else {
                    $new[$date][$i]['heure_debut'] = $a['heure_debut'];
                    $new[$date][$i]['heure_fin']   = $a['heure_fin'];
                }
            }
        }
    }
    return $new;
}

Example of Array that I pass:

$schedule = Array(
    '2012-11-12' => Array(),
    '2012-11-13' => Array(),
    '2012-11-14' => Array( 0 => Array("employe_id" => 8 , "heure_debut" => '16:00' ,"heure_fin" => '20:00' ,"date_seance" => 2012-11-14 , "jour_id" => 3)),
    '2012-11-15' => Array( 
        0 => Array("employe_id" => 8 , "heure_debut" => '09:00' ,"heure_fin" => '15:00' ,"date_seance" => 2012-11-15 , "jour_id" => 4),
        1 => Array("employe_id" => 8 , "heure_debut" => '16:00' ,"heure_fin" => '21:00' ,"date_seance" => 2012-11-15 , "jour_id" => 4)
    ),
    '2012-11-16' => Array(),
    '2012-11-17' => Array(),
    '2012-11-18' => Array(),
    '2012-11-19' => Array(0 => Array("employe_id" => 8 ,"heure_debut" => '10:00' ,"heure_fin" => '22:00' ,"date_seance" => 2012-11-19 ,"jour_id" => 1)),
    '2012-11-20' => Array(
        0 => Array("employe_id" => 8 ,"heure_debut" => '09:00' ,"heure_fin" => '15:00' ,"date_seance" => 2012-11-20 ,"jour_id" => 2),
        1 => Array("employe_id" => 8 ,"heure_debut" => '16:00' ,"heure_fin" => '20:00' ,"date_seance" => 2012-11-20 ,"jour_id" => 2)
    )
);

And for the second array:

$remove = array(
    '2012-11-12' => Array(),
    '2012-11-13' => Array(),
    '2012-11-14' => Array(),
    '2012-11-15'  => Array(),
    '2012-11-16' => Array(),
    '2012-11-17' => Array(),
    '2012-11-18' => Array(),
    // in this example i only have 1 absence ... I could have N absences
    '2012-11-19' => Array(0 => Array("employe_id" => 8 ,"date_debut" => 2012-11-19,"date_fin" => 2012-11-19  ,"heure_debut" => '12:00:00',"heure_fin"   => '14:00:00')),
    '2012-11-20' => Array(),
    '2012-11-21' => Array()
);

The resulting array would be:

$result = array(
Array
(
       [2012-11-12] => Array()
       [2012-11-13] => Array()
       // no change 
       [2012-11-14] => Array( [0] => Array("employe_id" => 8 , "heure_debut" => 16:00 ,"heure_fin" => 20:00 ,"date_seance" => 2012-11-14 , "jour_id" => 3))
       // no change
       [2012-11-15] => Array( 
                              [0] => Array("employe_id" => 8 , "heure_debut" => 09:00 ,"heure_fin" => 15:00 ,"date_seance" => 2012-11-15 , "jour_id" => 4),
                              [1] => Array("employe_id" => 8 , "heure_debut" => 16:00 ,"heure_fin" => 21:00 ,"date_seance" => 2012-11-15 , "jour_id" => 4)
                            )
       [2012-11-16] => Array()
       [2012-11-17] => Array()
       [2012-11-18] => Array()
       // since absence from 12 to 14 and  we had availability from 8 to 22 instead we will have 8->12 and 14->22
       [2012-11-19] => Array(
                          [0] => Array("employe_id" => 8 ,"heure_debut" => 08:00 ,"heure_fin" => 12:00 ,"date_seance" => 2012-11-20 ,"jour_id" => 1),
                          [1] => Array("employe_id" => 8 ,"heure_debut" => 14:00 ,"heure_fin" => 22:00 ,"date_seance" => 2012-11-20 ,"jour_id" => 1)
                        )
       // no changes since no absence during those time
       [2012-11-20] => Array(
                          [0] => Array("employe_id" => 8 ,"heure_debut" => 09:00 ,"heure_fin" => 15:00 ,"date_seance" => 2012-11-20 ,"jour_id" => 2),
                          [1] => Array("employe_id" => 8 ,"heure_debut" => 16:00 ,"heure_fin" => 20:00 ,"date_seance" => 2012-11-20 ,"jour_id" => 2)
                        )
)

Answer 1

I don't see why you need an exponential time recursion to execute this task. You can get away with an O(r * e^2) solution (where e is the average number of availabilities/removals per day, and r is size of removed times) via nested loop. Pseudocode below:

for removeday in remove:
    define scheduleday := schedule[removeday.date]
    if scheduleday not found:
        continue
    for removesegment in removeday:
        define temparray := empty
        for availsegment in scheduleday:
            if availsegment.employeid != removesegment.employeid:
                continue
            if no overlap:
                temparray.add(availsegment)
            if partial overlap:
                temparray.add(availsegment.split(removesegment))
        scheduleday = temparray
    schedule[removeday.date] := scheduleday
return schedule

Answer 2

If you don't want to add recursion to your function then you have to kind of convert it first to seconds of available schedule array matrix. Here the idea:

function scheduleToSecondsMatrix($value, $available=true){

    if(!is_array($value) || empty($value))
        return false;

    $object = array();

    foreach($value as $v) {
        $s = strtotime('1970-01-01 ' . $v['heure_debut'] . (!$available ? ' +1 seconds' : '')); // ref. http://stackoverflow.com/questions/4605117/how-to-convert-a-hhmmss-string-to-seconds-with-php
        $e = strtotime('1970-01-01 ' . $v['heure_fin'] . (!$available ? ' -1 seconds' : ''));

        if($e < $s) continue; // logically end time should be greater than start time

        while($s <= $e) {
            // i use string as key as this result will be merged: http://php.net/manual/en/function.array-merge.php
            $object["in_" . $s] = $available; // means in this seconds range is available
            $s++;
        }
    }

    return $object;
}

/**
 * This function assume: 
 * - all parameters refer to only one employee
 */
function removeSessionsFromScheduleRev($schedule, $remove) {

    if(!is_array($schedule) || !is_array($remove) || empty($schedule) || empty($remove)) return false;

    foreach($schedule as $s => &$dispo){

        if(empty($remove[$s]))
            continue;

        // convert the schedule to seconds array matrix, that's i call it :)
        $seconds_available = scheduleToSecondsMatrix($dispo, true);
        $seconds_not_available = scheduleToSecondsMatrix($remove[$s], false);

        if( !$seconds_available || !$seconds_not_available ) continue; // nothing changed

        $seconds_new = array_merge($seconds_available, $seconds_not_available);
        $seconds_new = array_filter($seconds_new); // remove empty/false value

        $new_time_schedule = array();
        $last_seconds = 0;

        $i=0;

        foreach($seconds_new as $in_seconds => $val){

            $in_seconds = intval(str_replace('in_', '', $in_seconds));

            if($in_seconds > ($last_seconds+1)){
                if(!empty($new_time_schedule)) $i++;
            }

            if(empty($new_time_schedule[$i]['start'])) $new_time_schedule[$i]['start'] = $in_seconds;
            $new_time_schedule[$i]['end'] = $in_seconds;

            $last_seconds = $in_seconds;
        }

        foreach($new_time_schedule as $idx => $val){
            if($idx && empty($dispo[$idx])) $dispo[$idx] = $dispo[$idx-1];

            $dispo[$idx]['heure_debut'] = date('H:i:s', $val['start']);
            $dispo[$idx]['heure_fin'] = date('H:i:s', $val['end']);
        }
    }

    return $schedule;
}

I haven't benchmark the performance yet so you may try this code on yours. I hope it works.

Answer 3

The code below produces the same output for the given sample but I haven't tested all possible cases.

Working Demo

function removeSessionsFromScheduleHelper(&$schedule,&$remove) {

    $change = false;

    foreach($remove as $date => &$remove_ranges) {

        if(empty($remove_ranges) || !isset($schedule[$date]))
            continue;

        foreach($remove_ranges as &$remove_range) {
            foreach($schedule[$date] as $day_key => &$time) {

                //start after finish, no overlap and because schedules are sorted
                //next items in schedule loop will also not overlap
                //break schedule loop & move to next remove iteration
                if($time['heure_debut'] >= $remove_range['heure_fin'])
                    break;

                //finish before start, no overlap
                if($time['heure_fin'] <= $remove_range['heure_debut'])
                    continue;

                //complete overlap, remove
                if($time['heure_debut'] >= $remove_range['heure_debut']
                  && $time['heure_fin'] <= $remove_range['heure_fin']) {
                    unset($schedule[$date][$day_key]);
                    continue;
                }

                //split into 2 ranges
                if($time['heure_debut'] < $remove_range['heure_debut']) {

                    if($time['heure_fin'] > $remove_range['heure_fin']) {
                        $schedule[$date][] = array(
                            'heure_debut' => $remove_range['heure_fin'],
                            'heure_fin' => $time['heure_fin']
                        );
                    }

                    $change = true;
                    $time['heure_fin'] = $remove_range['heure_debut'];                     
                    continue;
                }

                if($time['heure_debut'] >= $remove_range['heure_debut']) {
                    $change = true;
                    $time['heure_debut'] = $remove_range['heure_fin'];
                }                
            }
        }
    }

    if($change) {    
       foreach($schedule as &$values) {
          usort($values,'compare_schedule');
       }
    }

    return $change;
}

function compare_schedule($a,$b) {
    return strtotime($a['heure_debut']) - strtotime($b['heure_debut']);
}

function removeFromSchedule(&$schedule,$remove) {

    foreach($remove as $k => &$v) {
        foreach($v as $k2 => &$v2) {
            $v2['heure_debut'] = substr($v2['heure_debut'],0,5);
            $v2['heure_fin'] = substr($v2['heure_fin'],0,5);
        }
    }

    while(removeSessionsFromScheduleHelper($schedule,$remove));    
}

removeFromSchedule($schedule,$remove);
print_r($schedule);

Answer 4

I think jma127 is on the right track with their pseudocode. Let me supplement their answer with some commentary.

Your basic structure is to loop through entries of $schedule, and then for each one, pull out the corresponding entry from $remove, and make some changes. As soon as a change happens, you break out of the loop, and start over again. The control structure you use to start over again is a recursive call. When you start over again, you loop again through all the entries of $schedule which you've already checked and don't need to change anymore.

Array $schedule and array $remove are related through shared subscripts. For a given index i, $remove[i] affects only $schedule[i] and no other part. If there is no entry $remove[i], then $schedule[i] is unchanged. Thus jma127 is right to restructure the loop to iterate first through entries of $remove, and have an inner code block to combine the entries of $remove[i] and $schedule[i]. No need for recursion. No need for repeatedly iterating over $schedule.

I believe this is the major reason your code becomes slow as the number of entries increases.

For a given day's entries in $remove and $schedule, the way you combine them is based on start times and end times. jma127 is right to point out that if you sort the day's entries by time (start time firstly, and end time secondly), then you can make a single pass through the two arrays, and end up with the correct result. No need for recursion or repeated looping.

I believe this is a secondary reason your code becomes slow.

Another thing I notice about your code is that you frequently put code inside a loop that isn't affected by the loop. It would be a tiny bit more efficient to put it outside the loop. For instance, your validity check for $remove and $schedule:

if (is_array($schedule) && count($schedule) > 0 \
  && is_array($remove) && count($remove) > 0)...

is repeated every time the routine is called recursively. You could instead move this check to an outer function, which calls the inner function, and the inner function won't need to check $remove and $schedule again:

function removeSessionsFromSchedule_outer($schedule, $remove) {

    if (   is_array($schedule) && count($schedule) > 0 
        && is_array($remove) && count($remove) > 0     ) {
        $schedule = removeSessionsFromSchedule($schedule, $remove);
    }

    return $schedule;
}

Similarly,

foreach ($dispo as $d) {
    if (isset($remove[$s])) {
        $abs = $remove[$s];
    } else
        $abs = null;
    // rest of loop....
}/*foreach*/

could be rewritten as:

if (isset($remove[$s])) {
    $abs = $remove[$s];
} else
     $abs = null;
foreach ($dispo as $d) {
    // rest of loop....
}/*foreach*/

Another minor inefficiency is that your data structures don't contain the data in the format that you need. Instead of receiving a structure with data like:

[2012-11-14] => Array( [0] => Array(..."heure_debut" => 16:00 ...))

and each time during the loop, doing a data conversion like:

$abs_s = strtotime($a['heure_debut']);

How about having your upstream caller convert the data themselves:

["2012-11-14"] => Array([0]=>Array(..."heure_debut"=>strtotime("16:00") ...))

Another little detail is that you use syntax like 2012-11-14 and 16:00. PHP treats these as strings, but your code would be clearer if you put them in quotes to make it clear they are strings. See Why is $foo[bar] wrong? in PHP documenation Arrays.

I won't try to rewrite your code to make all these changes. I suspect you can figure that out yourself, looking at my comments and jma127's answer.

Answer 5

You have an availability schedule, implemented as a 2D array on day and entry number, and an absence schedule, implemented the same way, both sorted on time, and wish to update first using the second.

Both arrays are indexed the same way on their major dimension (using dates), so we can safely work on each of these rows without fear of modifying the rest of the arrays.

For a given day:

Within a day the simplest way to do it is to loop through all the $remove entries, and for each match on the employee_id, check the time and modify the schedule accordingly (something you already implemented, so we can reuse some of it). You want to keep the day schedule in order of time. The original arrays are well sorted, and if we store the modification in a new array in order creation, we won't have to sort it afterwards.

<?php

// create a schedule entry from template, with begin & end time
function schedule($tmpl, $beg, $end) {
    $schedule = $tmpl;
    $schedule['heure_debut'] = date("H:i", $beg);
    $schedule['heure_fin'] = date("H:i", $end);
    return $schedule;
}

// return one updated entry of a schedule day, based on an absence
function updateAvailability($d, $a){
    // absence start/end
    $dis_s = strtotime($d['heure_debut']);
    $dis_e = strtotime($d['heure_fin']);
    $abs_s = strtotime($a['heure_debut']);
    $abs_e = strtotime($a['heure_fin']);
    // Tests to see the if there is overlap between absence and availability
    // (2) [a_s]---[ds - de]---[a_e]
    if ($abs_s <= $dis_s && $abs_e >= $dis_e) {
        return array();
    }
    // (7)[as == ds] && [ae < de]
    else if ($abs_s == $dis_s && $abs_e < $dis_e) {
        return array(schedule($d,$abs_e,$dis_e));
    }
    // (1)[ds] --- [as] --- [ae] --- [de] (duplicate dis with new times)
    else if ($abs_s > $dis_s && $abs_e <= $dis_e) {
        // new times as : 
        // s1 = ds-as &&  s2 = ae-de
        return array(schedule($d,$dis_s,$abs_s), schedule($d,$abs_e,$dis_e));
    }
    // (3)[as] -- [ds] --- [ae] -- [de]
    else if ($abs_s < $dis_s && $abs_e < $dis_e) {
        return array(schedule($d,$abs_e,$dis_e));
    }
    // (4) [ds]---[as]--- [de]--- [ae]
    else if ($abs_s > $dis_s && $abs_s < $dis_e && $abs_e > $dis_e) {
        return array(schedule($d,$dis_s,$abs_s));
    }
    return array($d);
}

// move through all the entries of one day of schedule, and change
function updateDaySchedule($day, $absence){
    $n = array();
    foreach($day as $avail){
        // intersect availability with absence
        $a = updateAvailability($avail,$absence);
        // append new entries
        $n = array_merge($n, $a);
    }
    return $n;
}    

function removeSessionsFromSchedule($schedule, $remove) {
    if (!checkValidScheduleInput($schedule,$remove) 
        return $schedule;
    foreach($remove as $day => $absences) {
        // only update matching schedule day
        if (isset($schedule[$day])) {
            foreach ($absences as $abs)
                $schedule[$day] = updateDaySchedule($schedule[$day], $abs);
        }
    }
    return $schedule;
}

?>

There's still some room for improvement:

• the $dis_s, $dis_e, etc. values in updateAvailability are recomputed each time, whereas some could be computed once, and passed in as parameter to the function. It may not be worth the hassle though.

• the 'heure_debut' etc. constants could be made as defined constants:

  define('HD','heure_debut');

  This avoid possible typos (php will tell you if a constant is mispelled, but it won't tell you for a string literal), and make it easier for refactoring if the key names have to change.

Answer 6

The recursive nature of the function is your problem, nothing else in your function takes much processing power, so this should be quite fast. You really need to find a way to do this processing without recursing.