2

我有一组想要优化的数值范围。

这是初始值的简单示例：

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

优化后我期望的输出：

Start    End
1        2
9        12
60       88

这些是存储在 MySQL 数据库中的修改后的先序树遍历（嵌套集）数据中的left和值。right我使用它们从结果中排除不活动的分支，并且目前根本没有优化范围。我想我可能会通过在使用前优化范围来获得性能提升。

更多信息

NOT BETWEEN使用子句将这些值传递到查询中以排除树中的非活动分支。我认为我可以通过使用最小范围集来优化该查询的性能。

4

4 回答 4

2

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

现在，从头到尾遍历列表。留个柜台，c。当您通过范围开始时，递增c. 当您通过范围结束时，递减c.

当c从 0 到 1 时，那是最后一组中一个范围的开始。当c从 1 变为 0 时，这是一个范围的结束。

编辑::如果您已经在某处的数据库表中有范围，您可能可以构建一个 SQL 查询来执行上述第一步（再次确保范围起点在范围终点之前返回）。

于 2011-04-06T14:16:29.170 回答
2

这是一个将返回您想要的内容的 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 select vs primary/dependent subquery for EXISTS），因此性能可能会有所不同。如果存在，两个查询都将使用 (Start, End) 上的索引。

于 2011-04-07T08:05:29.573 回答
0

这是一个简单的实现：

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

看到它在行动。

于 2011-04-06T14:22:42.423 回答
0 
$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
于 2011-04-06T14:24:49.473 回答