Performance with time related algorithm
algorithm, merging-data, performance, php
Solution
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);
Problem
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) ) ) ```