Оптимизация числового диапазона

Question

У меня есть набор числовых диапазонов, которые я хотел бы оптимизировать.

Вот простой пример начальных значений:

Start    End
9        12
1        2
60       88
10       11
79       80

То, что я ожидаю в качестве вывода после оптимизации:

Start    End
1        2
9        12
60       88

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

---

ДОПОЛНИТЕЛЬНАЯ ИНФОРМАЦИЯ

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

Answer 1

Вот SQL, который будет возвращать то, что вы хотите

mysql> CREATE TABLE sample (Start INT, End INT);

mysql> INSERT sample VALUES (9,12),(1,2),(60,88),(10,11),(79,80);

mysql> SELECT * 
    -> FROM sample s 
    -> WHERE NOT EXISTS (SELECT 1 
    ->                   FROM sample 
    ->                   WHERE s.Start > Start AND s.Start < End);
+-------+------+
| Start | End  |
+-------+------+
|     9 |   12 |
|     1 |    2 |
|    60 |   88 |
+-------+------+

Конечно, вы можете создать VIEW, переместить данные в другую таблицу или удалить строки, используя вышеуказанный SQL.

ПРИМЕЧАНИЕ: я не совсем уверен, почему вы делаете эту «оптимизацию».

РЕДАКТИРОВАТЬ:
Запрос может быть переписан как

SELECT s.* 
FROM sample s LEFT JOIN 
     sample s2 ON s.Start > s2.Start AND s.Start < s2.End 
WHERE s2.start IS NULL;

, что создаст другой план выполнения (2xsimple select против основного / зависимого подзапроса для EXISTS), поэтому производительность может отличаться.Оба запроса будут использовать индекс (Start, End), если он существует.

Answer 2

Поместите их в отсортированный список.Отметьте, какие элементы в отсортированном списке представляют начало диапазона, а какие - конец диапазона.Сначала отсортируйте список по значению;однако убедитесь, что диапазон начинается раньше, чем заканчивается диапазон.(Вероятно, это будет связано с некоторой структурой, которая может быть отсортирована по заданному ключу. Я не знаю подробностей в php.)

Теперь просмотрите список от начала до конца.Держите счетчик, c.Когда вы передаете начало диапазона, увеличивается c.Когда вы передаете конец диапазона, уменьшается c.

Когда c изменяется от 0 до 1, это начало диапазона в окончательном наборе.Когда c изменяется от 1 до 0, это конец диапазона.

EDIT :: Если у вас уже есть диапазоны в таблице базы данных, вы, вероятно, можете структурировать SQLзапрос на выполнение первого шага выше (опять же, убедитесь, что начальные точки диапазона возвращены перед конечными точками диапазона).

Answer 3

$ranges = array(
  array(9, 12),
  array(1, 2),
  array(60, 81),
  array(10, 11),
  array(79, 88),
  );

function optimizeRangeArray($r) {
  $flagarr = array();
  foreach ($r as $range => $bounds) {
    $flagarr = array_pad($flagarr, $bounds[1], false);
    for ($i = $bounds[0]-1; $i < $bounds[1]; $i++) $flagarr[$i] = true;
    }
  $res = array(); $min = 0; $max = 0; $laststate = false;
  $ctr = 0;
  foreach ($flagarr as $state) {
    if ($state != $laststate) {
      if ($state) $min = $ctr + 1;
      else {
        $max = $ctr;
        $res[] = array($min, $max);
        }
      $laststate = $state;
      }
    $ctr++;
    }
  $max = $ctr;
  $res[] = array($min, $max);
  return($res);
  }

print_r(optimizeRangeArray($ranges));

Вывод:

Array
(
    [0] => Array
        (
            [0] => 1
            [1] => 2
        )

    [1] => Array
        (
            [0] => 9
            [1] => 12
        )

    [2] => Array
        (
            [0] => 60
            [1] => 88
        )

)

Примечание: это не работает для отрицательных целых чисел!

Или используйте это так

<code>$rres = optimizeRangeArray($ranges);

$out = "<pre>Start    End<br />";
foreach($rres as $range=>$bounds) {
  $out .= str_pad($bounds[0], 9, ' ') . str_pad($bounds[1], 9, ' ') . "<br />";
  }
$out .= "

"; echo $ out;

Чтобы получить это в своем браузере

Start    End
1        2
9        12
60       88

Answer 4

Вот простая реализация:

// I picked this format because it's convenient for the solution
// and because it's very natural for a human to read/write
$ranges = array(
  9    =>    12,
  1    =>    2,
  60   =>    81,
  10   =>    11,
  79   =>    88);

ksort($ranges);
$count = count($ranges);
$prev = null; // holds the previous start-end pair

foreach($ranges as $start => $end) {
    // If this range overlaps or is adjacent to the previous one
    if ($prev !== null && $start <= $prev[1] + 1) {
        // Update the previous one (both in $prev and in $ranges)
        // to the union of its previous value and the current range
        $ranges[$prev[0]] = $prev[1] = max($end, $prev[1]);

        // Mark the current range as "deleted"
        $ranges[$start] = null;
        continue;
    }

    $prev = array($start, $end);
}

// Filter all "deleted" ranges out
$ranges = array_filter($ranges);

Ограничения / Примечания:

1. Границы диапазона должны быть достаточно малы, чтобы соответствовать int.
2. Этот пример некорректно удалит любой диапазон из конечного результата, если конечная граница равна 0. Если ваши данные могут законно содержать такой диапазон, предоставьте соответствующий обратный вызов для array_filter: function($item) { return $item === null; }.

увидеть его в действии .