Online PHP editor | perf for EFHJQ

<?php declare(strict_types=1); /** * Value Object Segment — неизменяемый сегмент с флагами принадлежности. * * @property-read int $start * @property-read int $end * @property-read array $flags */ final class Segment { /** @var int */ private $start; /** @var int */ private $end; /** @var string[] */ private $flags; /** * @param int $start Начало интервала (включительно) * @param int $end Конец интервала (включительно) * @param string[] $flags Флаги принадлежности (только 'A' и/или 'B') * * @throws InvalidArgumentException если start > end или переданы недопустимые флаги */ public function __construct(int $start, int $end, array $flags) { if ($start > $end) { throw new \InvalidArgumentException( \sprintf('Начало сегмента (%d) не может быть больше конца (%d)', $start, $end) ); } $allowedFlags = ['A', 'B']; $normalizedFlags = []; foreach ($flags as $flag) { if (!\is_string($flag) || !\in_array($flag, $allowedFlags, true)) { throw new \InvalidArgumentException( \sprintf('Недопустимый флаг "%s". Разрешены только "A" и "B"', \is_scalar($flag) ? $flag : \gettype($flag)) ); } $normalizedFlags[] = $flag; } if (empty($normalizedFlags)) { throw new \InvalidArgumentException('Сегмент должен иметь хотя бы один флаг'); } // Упорядочиваем флаги для консистентности сравнения \sort($normalizedFlags); $this->flags = $normalizedFlags; $this->start = $start; $this->end = $end; } public function getStart(): int { return $this->start; } public function getEnd(): int { return $this->end; } /** * @return string[] Флаги (отсортированные) */ public function getFlags(): array { return $this->flags; } /** * Длина сегмента (количество целых точек) = end - start + 1 */ public function getLength(): int { return $this->end - $this->start + 1; } public function hasFlag(string $flag): bool { return \in_array($flag, $this->flags, true); } public function __toString(): string { return \sprintf('Segment(%d, %d, [%s])', $this->start, $this->end, \implode(',', $this->flags)); } } /** * Интерфейс алгоритма наложения интервалов. */ interface OverlapAlgorithmInterface { /** * Обрабатывает два набора интервалов и возвращает массив сегментов Segment[]. * * @param int[][] $intervalsA Массив интервалов A, каждый элемент — [start, end] * @param int[][] $intervalsB Массив интервалов B * @return Segment[] */ public function process(array $intervalsA, array $intervalsB): array; } /** * Стандартная реализация алгоритма наложения с дублированием границ. * * Логика: * 1. При $normalize=true каждый входной массив предварительно объединяет * пересекающиеся и соприкасающиеся интервалы. * 2. Из каждого интервала A вычитаются все интервалы B → чистые куски A. * 3. Из каждого интервала B вычитаются все интервалы A → чистые куски B. * 4. Находятся все попарные пересечения A∩B. * 5. Все куски собираются в Segment[], дубликаты удаляются, результат сортируется. */ final class DefaultOverlapAlgorithm implements OverlapAlgorithmInterface { /** @var bool */ private $normalize; /** * @param bool $normalize Нужно ли предварительно объединять пересекающиеся/касающиеся интервалы */ public function __construct(bool $normalize = true) { $this->normalize = $normalize; } /** * {@inheritdoc} */ public function process(array $intervalsA, array $intervalsB): array { $A = $intervalsA; $B = $intervalsB; if ($this->normalize) { $A = $this->normalizeIntervals($A); $B = $this->normalizeIntervals($B); } $cleanA = []; foreach ($A as $aInterval) { foreach ($this->subtractIntervals($aInterval, $B) as $piece) { $cleanA[] = $piece; } } $cleanB = []; foreach ($B as $bInterval) { foreach ($this->subtractIntervals($bInterval, $A) as $piece) { $cleanB[] = $piece; } } $intersections = $this->intersectIntervals($A, $B); // Собираем сегменты $segments = []; foreach ($cleanA as $int) { $segments[] = new Segment($int[0], $int[1], ['A']); } foreach ($cleanB as $int) { $segments[] = new Segment($int[0], $int[1], ['B']); } foreach ($intersections as $int) { $segments[] = new Segment($int[0], $int[1], ['A', 'B']); } // Удаление дубликатов (одинаковые начало, конец и флаги) $unique = []; foreach ($segments as $seg) { $key = $seg->getStart() . '_' . $seg->getEnd() . '_' . \implode(',', $seg->getFlags()); if (!isset($unique[$key])) { $unique[$key] = $seg; } } $segments = \array_values($unique); // Сортировка: сначала по start, затем по end, затем по флагам \usort($segments, static function (Segment $a, Segment $b): int { if ($a->getStart() !== $b->getStart()) { return $a->getStart() - $b->getStart(); } if ($a->getEnd() !== $b->getEnd()) { return $a->getEnd() - $b->getEnd(); } return \strcmp(\implode(',', $a->getFlags()), \implode(',', $b->getFlags())); }); return $segments; } /** * Нормализация: сортировка по start и объединение пересекающихся/касающихся интервалов. * * @param int[][] $intervals * @return int[][] */ private function normalizeIntervals(array $intervals): array { if (empty($intervals)) { return []; } // Сортировка по началу \usort($intervals, static function (array $a, array $b): int { return $a[0] - $b[0]; }); $merged = []; foreach ($intervals as $int) { if (empty($merged)) { $merged[] = $int; continue; } $last = &$merged[\count($merged) - 1]; // Касающиеся считаются объединяемыми: [10,20] и [21,30] -> [10,30] if ($int[0] <= $last[1] + 1) { if ($int[1] > $last[1]) { $last[1] = $int[1]; } } else { $merged[] = $int; } } return $merged; } /** * Вычитание набора интервалов из одного интервала. * Возвращает части $interval, не попавшие ни в один из $subtrahends, * с дублированием граничных точек. * * @param int[] $interval [start, end] * @param int[][] $subtrahends Массив вычитаемых интервалов (отсортированных, без пересечений) * @return int[][] Массив интервалов [start, end] */ private function subtractIntervals(array $interval, array $subtrahends): array { $pieces = [$interval]; foreach ($subtrahends as $sub) { $newPieces = []; foreach ($pieces as $piece) { $overlapStart = \max($piece[0], $sub[0]); $overlapEnd = \min($piece[1], $sub[1]); if ($overlapStart <= $overlapEnd) { // Есть пересечение – отрезаем левую и правую части if ($piece[0] < $overlapStart) { $newPieces[] = [$piece[0], $overlapStart]; } if ($overlapEnd < $piece[1]) { $newPieces[] = [$overlapEnd, $piece[1]]; } // Полное поглощение куска – ничего не добавляем } else { // Пересечения нет, кусок остаётся как есть $newPieces[] = $piece; } } $pieces = $newPieces; } return $pieces; } /** * Попарные пересечения двух массивов интервалов. * * @param int[][] $A * @param int[][] $B * @return int[][] */ private function intersectIntervals(array $A, array $B): array { $result = []; foreach ($A as $a) { foreach ($B as $b) { $start = \max($a[0], $b[0]); $end = \min($a[1], $b[1]); if ($start <= $end) { $result[] = [$start, $end]; } } } return $result; } } /** * Менеджер для вычисления и предоставления результатов наложения интервалов. */ final class IntervalOverlapManager { /** @var OverlapAlgorithmInterface */ private $algorithm; /** @var Segment[] */ private $segments = []; /** @var int[][] Оригинальный набор A */ private $originalA = []; /** @var int[][] Оригинальный набор B */ private $originalB = []; /** * @param OverlapAlgorithmInterface|null $algorithm Алгоритм (если null – стандартный с нормализацией) */ public function __construct(?OverlapAlgorithmInterface $algorithm = null) { $this->algorithm = $algorithm ?? new DefaultOverlapAlgorithm(); } /** * Запуск вычислений. * * @param int[][] $intervalsA * @param int[][] $intervalsB * @return self */ public function calculate(array $intervalsA, array $intervalsB): self { $this->originalA = $intervalsA; $this->originalB = $intervalsB; $this->segments = $this->algorithm->process($intervalsA, $intervalsB); return $this; } /** * @return Segment[] Все сегменты разбиения */ public function getSegments(): array { return $this->segments; } /** * @return Segment[] Сегменты пересечения (флаги ['A','B']) */ public function getIntersections(): array { return \array_values(\array_filter($this->segments, static function (Segment $s): bool { return $s->getFlags() === ['A', 'B']; })); } /** * @return Segment[] Сегменты только A (флаг ['A']) */ public function getUniqueA(): array { return \array_values(\array_filter($this->segments, static function (Segment $s): bool { return $s->getFlags() === ['A']; })); } /** * @return Segment[] Сегменты только B (флаг ['B']) */ public function getUniqueB(): array { return \array_values(\array_filter($this->segments, static function (Segment $s): bool { return $s->getFlags() === ['B']; })); } /** * «Дыры» — промежутки между объединением всех исходных интервалов. * Объединение строится с той же логикой, что и нормализация. * * @return int[][] Массив [start, end] */ public function getHoles(): array { $all = \array_merge($this->originalA, $this->originalB); $united = $this->normalizeIntervals($all); $holes = []; for ($i = 0, $c = \count($united) - 1; $i < $c; ++$i) { $gapStart = $united[$i][1] + 1; $gapEnd = $united[$i + 1][0] - 1; if ($gapStart <= $gapEnd) { $holes[] = [$gapStart, $gapEnd]; } } return $holes; } /** * Количество сегментов (с учётом дублирующихся границ). */ public function count(): int { return \count($this->segments); } /** * Сумма длин всех сегментов. Из-за дублирования границ может превышать реальную длину покрытия. */ public function totalDuration(): int { $sum = 0; foreach ($this->segments as $seg) { $sum += $seg->getLength(); } return $sum; } /** * Объединение всех покрытых чисел (без повторов, одна нормализованная картина). * * @return int[][] */ public function getUnion(): array { $all = \array_merge($this->originalA, $this->originalB); return $this->normalizeIntervals($all); } /** * Вспомогательный метод нормализации (аналогичен используемому в алгоритме). * * @param int[][] $intervals * @return int[][] */ private function normalizeIntervals(array $intervals): array { if (empty($intervals)) { return []; } \usort($intervals, static function (array $a, array $b): int { return $a[0] - $b[0]; }); $merged = []; foreach ($intervals as $int) { if (empty($merged)) { $merged[] = $int; continue; } $last = &$merged[\count($merged) - 1]; if ($int[0] <= $last[1] + 1) { if ($int[1] > $last[1]) { $last[1] = $int[1]; } } else { $merged[] = $int; } } return $merged; } } // ------------------------------------------------------- // Пример использования и проверка // ------------------------------------------------------- $manager = new IntervalOverlapManager(new DefaultOverlapAlgorithm(true)); $manager->calculate( [[10, 30]], // A [[20, 40]] // B ); $segments = $manager->getSegments(); // Ожидаемый порядок (по start): // Segment(10, 20, ['A']) // Segment(20, 30, ['A','B']) // Segment(30, 40, ['B']) echo "Сегменты:\n"; foreach ($segments as $seg) { echo $seg . "\n"; } echo "\nПересечения (AB):\n"; foreach ($manager->getIntersections() as $seg) { echo $seg . "\n"; } echo "\nУникальные A:\n"; foreach ($manager->getUniqueA() as $seg) { echo $seg . "\n"; } echo "\nУникальные B:\n"; foreach ($manager->getUniqueB() as $seg) { echo $seg . "\n"; } echo "\nОбщая сумма длин сегментов (totalDuration): " . $manager->totalDuration() . "\n"; echo "Количество сегментов: " . $manager->count() . "\n"; // Проверка дыр $manager2 = new IntervalOverlapManager(new DefaultOverlapAlgorithm(true)); $manager2->calculate( [[10, 15]], // A [[20, 25]] // B ); echo "\nДыры (A [10,15], B [20,25]):\n"; foreach ($manager2->getHoles() as $hole) { echo '[' . $hole[0] . ', ' . $hole[1] . "]\n"; } // Проверка с нормализацией A: [[10,20],[15,30]] -> [10,30] $manager3 = new IntervalOverlapManager(new DefaultOverlapAlgorithm(true)); $manager3->calculate( [[10, 20], [15, 30]], [[20, 40]] ); echo "\nС нормализацией (A: [10,20],[15,30]; B: [20,40]):\n"; foreach ($manager3->getSegments() as $seg) { echo $seg . "\n"; } // Union проверка echo "\nОбъединение покрытия (Union):\n"; foreach ($manager3->getUnion() as $int) { echo '[' . $int[0] . ', ' . $int[1] . "]\n"; }

Version	System time (s)	User time (s)	Memory (MiB)
8.5.3	0.033	0.007	16.73
8.5.2	0.029	0.011	16.73
8.5.1	0.032	0.008	16.73
8.5.0	0.012	0.004	16.75
8.4.18	0.034	0.009	19.62
8.4.17	0.031	0.010	19.69
8.4.16	0.035	0.009	19.80
8.4.15	0.035	0.008	19.64
8.4.14	0.037	0.010	18.00
8.4.13	0.034	0.005	17.93
8.4.12	0.035	0.012	17.92
8.4.11	0.030	0.010	18.03
8.4.10	0.033	0.006	17.94
8.4.9	0.039	0.007	18.16
8.4.8	0.037	0.009	18.04
8.4.7	0.035	0.012	18.02
8.4.6	0.040	0.011	17.78
8.4.5	0.031	0.009	17.90
8.4.4	0.039	0.007	17.87
8.4.3	0.035	0.008	17.80
8.4.2	0.034	0.008	17.88
8.4.1	0.033	0.011	17.93
8.3.30	0.033	0.010	18.32
8.3.29	0.036	0.015	18.65
8.3.28	0.032	0.008	18.66
8.3.27	0.028	0.010	16.86
8.3.26	0.015	0.005	16.78
8.3.25	0.018	0.008	16.73
8.3.24	0.036	0.009	16.81
8.3.23	0.032	0.012	16.77
8.3.22	0.038	0.010	16.81
8.3.21	0.038	0.011	16.88
8.3.20	0.029	0.013	16.88
8.3.19	0.038	0.007	16.73
8.3.18	0.038	0.006	16.82
8.3.17	0.037	0.004	16.86
8.3.16	0.018	0.004	16.98
8.3.15	0.036	0.008	16.73
8.3.14	0.025	0.005	16.79
8.3.13	0.020	0.008	16.78
8.3.12	0.016	0.003	16.98
8.3.11	0.028	0.008	16.80
8.3.10	0.039	0.006	16.86
8.3.9	0.032	0.009	16.73
8.3.8	0.023	0.002	16.82
8.3.7	0.015	0.006	16.80
8.3.6	0.017	0.005	16.97
8.3.5	0.034	0.009	16.82
8.3.4	0.036	0.008	18.10
8.3.3	0.028	0.007	18.10
8.3.2	0.022	0.013	18.10
8.3.1	0.026	0.011	18.04
8.3.0	0.029	0.009	18.02