数字范围优化

Question

我有一组数字范围，我想优化。

这里的初始值的一个简单的例子：

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

我期待什么作为输出优化后：

Start End 
1  2 
9  12 
60  88 

这是改自预购树的遍历的left和right值（嵌套设置）存储在MySQL数据库中的数据。我使用它们从结果中排除不活动的分支，而目前我根本没有优化范围。我想我可能会从使用前优化范围获得性能提升。

---

MORE INFO

的值被传递到用于使用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 | 
+-------+------+ 

可以，当然，可以使用上面的SQL创建VIEW，将数据移动到另一个表或删除行。

注意：我不是很确定你为什么要做这个'优化'。

编辑：
查询可以改写为

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选择VS初级/相关子查询的存在），因此性能可能会有所不同。如果存在，这两个查询将在（开始，结束）上使用索引。

Answer 2

把它们放在一个排序列表中。标记排序列表中的哪些元素代表范围开始，哪些是范围结束。首先根据值对列表进行排序;但是，请确保范围始于范围结束之前。 （这可能会涉及某种结构，可以在给定的键上进行排序，我不知道php中的细节。）

现在，遍历从开始到结束的列表。保留一个计数器，c。当你通过一个范围开始，增量c。当你通过一个范围结束时，递减c。

当c从0变为1时，这是最终集合中范围的开始。当c从1变为0时，这是范围的结束。

编辑::如果你已经在某个地方的数据库表中的范围，你可能可以构造一个SQL查询来执行上面的第一步（再次确保范围起点在范围结束之前返回）点）。

Answer 3

这里有一个简单的实现：

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

See it in action。

Answer 4

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

) 

注：这并不适用于负整数工作！

或者使用这样的

$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 .= "</pre>"; 
echo $out; 

要在浏览器

Start End 
1  2 
9  12 
60  88