Производительность с временным алгоритмом

Ответ 1

Приведенный ниже код дает тот же результат для данного образца, но я не тестировал все возможные случаи.

Рабочая демонстрация

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);

Ответ 2

Я не понимаю, зачем вам нужна экспоненциальная рекурсия времени для выполнения этой задачи. Вы можете уйти с решением O (r * e ^ 2) (где e - среднее количество доступности/абсорбции в день, а r - размер удаленных времен) через вложенный цикл. Псевдокод ниже:

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

Ответ 3

Если вы не хотите добавлять рекурсию к своей функции, вам нужно преобразовать ее сначала в секунды доступной матрицы массива расписания. Здесь идея:

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 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;
}

Я пока не тестировал производительность, поэтому вы можете попробовать этот код на своем. Я надеюсь, что это сработает.

Ответ 4

Я думаю, что jma127 находится на правильном пути с их псевдокодом. Позвольте мне дополнить свой ответ некоторыми комментариями.

Ваша основная структура состоит в том, чтобы зацикливать записи $schedule, а затем для каждого из них вывести соответствующую запись из $remove и внести некоторые изменения. Как только произойдет изменение, вы выйдете из цикла и начните заново. Структура управления, которую вы используете для начала снова, - это рекурсивный вызов. Когда вы начинаете заново, вы повторяете все записи $schedule, которые вы уже отметили, и больше не нужно изменять.

Массив $schedule и массив $remove связаны через общие индексы. Для данного индекса i, $remove[i] влияет только на $schedule[i] и никакой другой части. Если нет записи $remove[i], то $schedule[i] не изменяется. Таким образом, jma127 имеет право реструктурировать цикл для итерации сначала через записи $remove и иметь внутренний кодовый блок для объединения записей $remove[i] и $schedule[i]. Нет необходимости в рекурсии. Не нужно многократно повторять процедуру $schedule.

Я считаю, что это основная причина, по которой ваш код замедляется по мере увеличения количества записей.

Для заданных дневных записей в $remove и $schedule способ их объединения основан на времени начала и времени окончания. jma127 имеет право указать, что если сортировать записи дня по времени (время начала и второе время), вы можете сделать один проход через два массива и в конечном итоге правильный результат. Нет необходимости в рекурсии или повторном цикле.

Я считаю, что это вторичная причина, по которой ваш код становится медленным.

Еще одна вещь, которую я замечаю о вашем коде, - это то, что вы часто помещаете код внутри цикла, на который не влияет цикл. Было бы немного более эффективным, чтобы вывести его за пределы цикла. Например, проверка достоверности для $remove и $schedule:

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

повторяется каждый раз, когда процедура вызывается рекурсивно. Вместо этого вы можете перенести эту проверку на внешнюю функцию, которая вызывает внутреннюю функцию, а внутренней функции не потребуется снова проверять $remove и $schedule:

function removeSessionsFromSchedule_outer($schedule, $remove) {

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

    return $schedule;
}

Аналогично,

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

можно переписать как:

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

Еще одна незначительная неэффективность заключается в том, что ваши структуры данных не содержат данных в нужном формате. Вместо получения структуры с данными вроде:

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

и каждый раз во время цикла, делая преобразование данных, например:

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

Как насчет того, чтобы ваш обратный вызов конвертировал сами данные:

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

Еще одна небольшая деталь заключается в том, что вы используете синтаксис типа 2012-11-14 и 16:00. PHP рассматривает их как строки, но ваш код будет более понятным, если вы поместите их в кавычки, чтобы они поняли, что это строки. См. Почему $foo [bar] не так? в PHP documenation Массивы.

Я не буду пытаться переписать код, чтобы внести все эти изменения. Я подозреваю, что вы можете это понять, глядя на мои комментарии и jma127.

Ответ 5

У вас есть график доступности, реализованный как 2D-массив в день и номер входа, и график отсутствия, реализованный таким же образом, как отсортированный по времени, так и желание обновить сначала, используя второй.

Оба массива индексируются одинаково по их основному размеру (используя даты), поэтому мы можем безопасно работать над каждой из этих строк, не опасаясь модифицировать остальные массивы.

За данный день:

В течение дня самый простой способ сделать это - пропустить все записи $remove и для каждого совпадения на employee_id, проверить время и соответствующим образом изменить расписание (то, что вы уже реализовали, чтобы мы могли повторно использовать некоторые его). Вы хотите сохранить график дня в порядке времени. Исходные массивы хорошо отсортированы, и если мы сохраним модификацию в новом массиве в порядке создания, нам не придется сортировать его впоследствии.

<?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;
}

?>

Там еще есть место для улучшения:

• значения $dis_s, $dis_e и т.д. в updateAvailability пересчитываются каждый раз, тогда как некоторые могут быть вычислены один раз и переданы как параметр функции. Возможно, это не стоит хлопот.

• константы 'heure_debut' и т.д. могут быть выполнены как определенные константы:

  define('HD','heure_debut');

  Это предотвратит возможные опечатки (php сообщит вам, если константа неверно указана, но она не сообщит вам строковый литерал) и упростите рефакторинг, если имена ключей должны измениться.

Ответ 6

Рекурсивный характер функции - это ваша проблема, ничто другое в вашей функции не требует большой вычислительной мощности, поэтому это должно быть довольно быстро. Вам действительно нужно найти способ сделать эту обработку без рекурсии.