php - 时间相关算法的性能

Question

我有一个函数接受 2 个数组($schedule、$remove)，它们都是包含时间的天数数组，它将从日程表中删除时间。

现在，如果我有 1 到 20 个用户，此功能可以正常工作，它需要 2-4 秒来生成日历，这很好，但是当有 20 个以上的用户有很多计划条目时，它会达到 15 秒以上。

我正在使用 CodeIgniter，我在经常调用它的助手中有这个函数。

所以我想知道你们是否可以看到任何更好的方法来处理我的问题或我对算法所做的调整以使其更快。

注意:在我下面的代码中，我看到的最大问题是递归调用和每次修改结构时循环的中断。

我在两个数组上循环并进行测试以查看缺失是否在可用性的内部/重叠/相等/外部，然后如果结构被修改则调用函数，如果没有返回最终结构。

注2:

在本地 Apache 崩溃，因为递归函数有时被调用超过 100 次。

这是我的代码:

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

相关助手

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

我传递的数组示例:

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

对于第二个数组:

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

结果数组将是:

$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

我不明白为什么需要指数时间递归来执行此任务。您可以通过嵌套循环使用 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