Online PHP editor | perf for cRJXG

<?php $dates[] = array("date" => "2016-02-18 02:00:00", "duration" => "600"); // 10 mins $dates[] = array("date" => "2016-02-18 02:05:00", "duration" => "300"); // 5 mins $dates[] = array("date" => "2016-02-18 02:10:00", "duration" => "600"); $dates[] = array("date" => "2016-02-18 02:15:00", "duration" => "300"); $dates[] = array("date" => "2016-02-18 02:20:00", "duration" => "600"); $dates[] = array("date" => "2016-02-18 02:25:00", "duration" => "300"); $dates[] = array("date" => "2016-02-18 02:30:00", "duration" => "600"); $alreadyChosenDates[] = array("date" => "2016-02-18 02:10:00", "duration" => "600"); class ScheduleList { /** * A list of all the dates that: * 1) After the 'chosen' start date * 2) Do not overlap with any 'chosen' date * * @var array $candidates */ private $candidates = array(); /** * Any date record we didn't use. * * @var array $unused */ private $unused = array(); /** * List of dates that must be included in the 'final' list. * The earliest date is assumed to be a start date and everything must be later. * * @var array $chosen */ private $chosen = array(); /** * Ordered list of `none overlapping' dates from the chosen and candidates * * @var array $final */ private $final = array(); /** * These are the date lists. * They will be converted, sorted and filters as required. * * @param array $chosenDates * @param array $candidateDates * @return void */ public function __construct(array $chosenDates, array $candidateDates) { // convert and sort foreach ($chosenDates as $when) { $this->chosen[] = $this->makeDateRange($when); } if (count($this->chosen) > 1) { // sort them so we can easily compare against them usort($this->chosen, function ($when1, $when2) { return $when1['startTime'] - $when2['startTime']; }); } // add chosen to the final list $this->final = $this->chosen; // convert, sort and filter the candidates $this->convertCandidates($candidateDates); } /** * Add the candidates to the final list * * Known conditions: * o Both lists are in start date order * o No candidates overlap with any chosen date * o The candidates may overlap with each other - Hmm... need to check... * * Note: The '$this->isOverlapsAny' method - as it is used a lot will be expensive (O(n^2)) * I can think of ways to reduce that - will happen when it is refactored ;-/ * * @return array */ public function generateList() { // first candidate MUST be the closest to the first chosen date due to sorting. $this->final[] = array_shift($this->candidates); // move it to the final list // Add the remaining candidates checking for overlaps as we do so... foreach ($this->candidates as $candidate) { if ($this->isOverlapAny($candidate, $this->final)) { $this->unused[] = $candidate; } else { $this->final[] = $candidate; } } // sort final by start times - makes it easy to reason about usort($this->final, function ($when1, $when2) { return $when1['startTime'] - $when2['startTime']; }); return $this->final; } /* * Convert each date to a dateRange that is easier to check and display * * o Check each candidate date for ovelapping with any of the 'chosen dates' * o Check if before first chosen start data. */ protected function convertCandidates(array $candidateDates) { foreach ($candidateDates as $idx => $when) { $candidate = $this->makeDateRange($when); // overlaps with any chosen then ignore it if ($this->isOverlapAny($candidate, $this->chosen)) { // ignore it $this->unused[] = $candidate; // record failed ones so easy to check continue; } // ignore if before first chosen start time if ($candidate['endTime'] <= $this->chosen[0]['startTime']) { $this->unused[] = $candidate; // record failed ones so easy to check continue; } $this->candidates[] = $candidate; } // sort candidates by start times - makes it easy to reason about usort($this->candidates, function ($when1, $when2) { return $when1['startTime'] - $when2['startTime']; }); } /** * Convert to UNIX timestamp as seconds will make the calculations easier * * The result has: * 1) the time as a date object - I can do calculations / format it whatever * 2) startTime as epoch seconds * 3) endTime as epoch seconds * * @param array $when * * @return array */ public function makeDateRange(array $when) { $dt = \DateTime::createFromFormat('Y-m-d H:i:s', $when['date']); $result = array(); $result['when'] = $dt; $result['duration'] = (int) $when['duration']; $result['startTime'] = (int) $dt->format('U'); $result['endTime'] = (int) $result['startTime'] + $when['duration']; return $result; } /** * if start is after other end OR end is before other start then they don't overlap * * Easiest way is to check that they don't overlap and reverse the result */ public function isOverlap($when1, $when2) { return ! ( $when1['endTime'] <= $when2['startTime'] || $when1['startTime'] >= $when2['endTime']); } /** * Check if candidate overlaps any of the dates in the list * * @param array $candidate * @param array $whenList -- list of non-overlapping dates * * @return boolean true if overlaps */ function isOverlapAny($candidate, $whenList) { foreach ($whenList as $when) { if ($this->isOverlap($when, $candidate)) { // ignore it return true; } } return false; } /** * Show a date formatted for debugging purposes * * @param array $when * @return void */ public function displayWhen(array $when) { echo PHP_EOL, 'date: ', $when['when']->format('Y-m-d H:i:s'), ' len: ', $when['duration'], ' end: ', date('Y-m-d H:i:s', $when['endTime']), ' start: ', $when['startTime'], ' end: ', $when['endTime']; } /* * `Getters` so you can see what happened */ public function getChosen() { return $this->chosen; } public function getUnused() { return $this->unused; } public function getCandidates() { return $this->candidates; } public function getFinal() { return $this->final; } /** * properties - for those of us that like them */ public function __get($name) { if (property_exists($this, $name)) { return $this->$name; } return null; } } $datesListGenerator = new ScheduleList($alreadyChosenDates, $dates); $final = $datesListGenerator->generateList(); foreach ($datesListGenerator->getUnused() as $when) { $datesListGenerator->displayWhen($when); }

Version	System time (s)	User time (s)	Memory (MiB)
8.3.6	0.011	0.007	17.00
8.3.5	0.013	0.007	18.07
8.3.4	0.004	0.011	19.07
8.3.3	0.013	0.003	18.90
8.3.2	0.004	0.004	19.02
8.3.1	0.008	0.000	21.95
8.3.0	0.004	0.004	19.50
8.2.18	0.009	0.009	16.47
8.2.17	0.007	0.011	22.96
8.2.16	0.011	0.004	20.52
8.2.15	0.005	0.003	24.18
8.2.14	0.004	0.004	24.66
8.2.13	0.011	0.003	26.16
8.2.12	0.006	0.003	18.96
8.2.11	0.016	0.003	20.64
8.2.10	0.009	0.003	18.28
8.2.9	0.005	0.003	17.94
8.2.8	0.000	0.008	20.52
8.2.7	0.009	0.000	18.15
8.2.6	0.000	0.008	18.16
8.2.5	0.000	0.009	18.34
8.2.4	0.003	0.006	20.39
8.2.3	0.003	0.006	19.49
8.2.2	0.003	0.005	18.14
8.2.1	0.004	0.004	18.26
8.2.0	0.005	0.003	17.95
8.1.28	0.014	0.007	25.92
8.1.27	0.005	0.003	22.23
8.1.26	0.005	0.003	26.35
8.1.25	0.000	0.008	28.09
8.1.24	0.010	0.006	23.88
8.1.23	0.009	0.003	20.99
8.1.22	0.005	0.003	18.04
8.1.21	0.000	0.008	18.90
8.1.20	0.004	0.004	17.60
8.1.19	0.000	0.010	17.48
8.1.18	0.005	0.003	18.10
8.1.17	0.005	0.003	18.72
8.1.16	0.006	0.003	20.67
8.1.15	0.003	0.006	22.09
8.1.14	0.000	0.008	19.77
8.1.13	0.004	0.004	17.85
8.1.12	0.003	0.007	17.57
8.1.11	0.000	0.008	17.55
8.1.10	0.006	0.006	17.65
8.1.9	0.004	0.004	17.55
8.1.8	0.004	0.004	17.65
8.1.7	0.004	0.004	17.66
8.1.6	0.000	0.008	17.71
8.1.5	0.006	0.003	17.64
8.1.4	0.005	0.003	17.66
8.1.3	0.004	0.004	17.81
8.1.2	0.003	0.005	17.86
8.1.1	0.004	0.004	17.65
8.1.0	0.000	0.008	17.76
8.0.30	0.007	0.000	20.23
8.0.29	0.006	0.003	16.88
8.0.28	0.003	0.003	18.62
8.0.27	0.004	0.004	17.41
8.0.26	0.005	0.002	17.34
8.0.25	0.007	0.000	17.29
8.0.24	0.007	0.000	17.28
8.0.23	0.004	0.004	17.16
8.0.22	0.002	0.005	17.20
8.0.21	0.004	0.004	17.25
8.0.20	0.000	0.006	17.12
8.0.19	0.004	0.004	17.17
8.0.18	0.004	0.007	17.23
8.0.17	0.004	0.004	17.07
8.0.16	0.000	0.007	17.18
8.0.15	0.005	0.003	17.17
8.0.14	0.005	0.002	17.19
8.0.13	0.003	0.003	13.62
8.0.12	0.000	0.008	17.20
8.0.11	0.003	0.005	17.15
8.0.10	0.004	0.004	17.13
8.0.9	0.000	0.008	17.22
8.0.8	0.003	0.012	17.14
8.0.7	0.006	0.003	17.28
8.0.6	0.000	0.008	17.20
8.0.5	0.005	0.003	17.20
8.0.3	0.010	0.010	17.31
8.0.2	0.010	0.011	17.40
8.0.1	0.000	0.007	17.46
8.0.0	0.013	0.006	17.11
7.4.33	0.005	0.000	15.55
7.4.32	0.006	0.000	16.74
7.4.30	0.000	0.007	16.66
7.4.29	0.000	0.007	16.72
7.4.28	0.004	0.004	16.75
7.4.27	0.003	0.003	16.72
7.4.26	0.004	0.004	16.64
7.4.25	0.000	0.008	16.55
7.4.24	0.000	0.007	16.76
7.4.23	0.003	0.003	16.46
7.4.22	0.007	0.011	16.73
7.4.21	0.011	0.007	16.69
7.4.20	0.006	0.003	16.69
7.4.16	0.009	0.008	16.71
7.4.15	0.015	0.003	17.40
7.4.14	0.013	0.006	17.86
7.4.13	0.008	0.013	16.78
7.4.12	0.008	0.013	16.69
7.4.11	0.019	0.007	16.79
7.4.10	0.015	0.004	16.80
7.4.9	0.009	0.009	16.72
7.4.8	0.013	0.010	19.39
7.4.7	0.011	0.005	16.56
7.4.6	0.014	0.003	16.82
7.4.5	0.003	0.011	16.74
7.4.4	0.015	0.011	16.63
7.4.3	0.004	0.015	16.78
7.4.0	0.003	0.012	15.26
7.3.33	0.000	0.005	13.50
7.3.32	0.006	0.000	13.37
7.3.31	0.000	0.008	16.67
7.3.30	0.000	0.007	16.42
7.3.29	0.005	0.002	16.51
7.3.28	0.012	0.008	16.48
7.3.27	0.007	0.014	17.40
7.3.26	0.010	0.008	16.65
7.3.25	0.011	0.007	16.71
7.3.24	0.013	0.008	16.75
7.3.23	0.009	0.009	16.71
7.3.21	0.015	0.003	16.45
7.3.20	0.011	0.007	16.68
7.3.19	0.012	0.012	16.67
7.3.18	0.009	0.008	16.55
7.3.17	0.012	0.006	16.70
7.3.16	0.006	0.011	16.73
7.2.33	0.013	0.006	16.82
7.2.32	0.016	0.003	16.59
7.2.31	0.007	0.011	17.11
7.2.30	0.013	0.013	16.77
7.2.29	0.010	0.010	17.06
7.2.6	0.004	0.009	17.17
7.2.5	0.003	0.010	16.92
7.2.0	0.000	0.016	19.35
7.1.20	0.011	0.004	15.88
7.1.7	0.005	0.002	17.14
7.1.6	0.009	0.006	17.41
7.1.0	0.000	0.080	22.36
7.0.20	0.007	0.007	15.20
7.0.13	0.017	0.053	22.03
7.0.12	0.013	0.050	22.04
7.0.11	0.007	0.060	22.07
7.0.10	0.000	0.060	22.13
7.0.9	0.007	0.057	21.99
7.0.8	0.003	0.060	22.12
7.0.7	0.010	0.053	21.98
7.0.6	0.010	0.053	21.97
7.0.5	0.010	0.060	22.16
7.0.4	0.010	0.060	22.11
7.0.3	0.007	0.057	21.98
7.0.2	0.010	0.057	22.05
7.0.1	0.003	0.063	22.07
7.0.0	0.013	0.053	21.98
5.6.28	0.007	0.057	21.13
5.6.27	0.000	0.067	21.09
5.6.26	0.013	0.053	21.13
5.6.25	0.007	0.057	21.13
5.6.24	0.000	0.067	20.98
5.6.23	0.003	0.060	20.83
5.6.22	0.007	0.057	21.02
5.6.21	0.020	0.047	20.99
5.6.20	0.013	0.053	21.07
5.6.19	0.013	0.080	21.08
5.6.18	0.000	0.060	21.08
5.6.17	0.007	0.057	20.95
5.6.16	0.003	0.067	21.11
5.6.15	0.010	0.060	21.05
5.6.14	0.007	0.067	21.13
5.6.13	0.010	0.057	21.13
5.6.12	0.010	0.067	20.90
5.6.11	0.013	0.057	21.04
5.6.10	0.010	0.077	20.88
5.6.9	0.010	0.057	20.77
5.6.8	0.007	0.053	20.18
5.6.7	0.010	0.050	20.36
5.6.6	0.017	0.053	20.21
5.6.5	0.007	0.053	20.28
5.6.4	0.003	0.070	20.34
5.6.3	0.007	0.060	20.33
5.6.2	0.007	0.060	20.32
5.6.1	0.003	0.060	20.42
5.6.0	0.010	0.070	20.26