2

最適化したい数値範囲が設定されています。

初期値の簡単な例を次に示します。

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

最適化後の出力として期待するもの:

Start    End
1        2
9        12
60       88

これらは、MySQL データベースに保存されている Modified Preorder Tree Traversal (Nested Set) データからのleftとの値です。right非アクティブなブランチを結果から除外するためにそれらを使用していますが、現在は範囲をまったく最適化していません。使用前に範囲を最適化することで、パフォーマンスが向上する可能性があると考えました。

より詳しい情報

NOT BETWEEN値は、句を使用してツリー内の非アクティブなブランチを除外するためのクエリに渡されます。最小限の範囲セットを使用することで、そのクエリのパフォーマンスを最適化できると考えました。

4

4 に答える 4

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 を作成したり、データを別のテーブルに移動したり、行を削除したりできます。

注: なぜこの「最適化」を行っているのかよくわかりません。

EDIT：
クエリは次のように書き直すことができます

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) のインデックスが存在する場合はそれを使用します。

于 2011-04-07T08:05:29.573 に答える
2

それらをソートされたリストに入れます。並べ替えられたリストのどの要素が範囲の開始を表し、どの要素が範囲の終了を表すかをマークします。最初に値に基づいてリストを並べ替えます。ただし、範囲の開始が範囲の終了よりも前に来るようにしてください。(これには、特定のキーでソートできる何らかの構造が含まれる可能性があります。php の詳細はわかりません。)

次に、リストを最初から最後までトラバースします。カウンターをキープしcます。範囲の開始を渡すと、インクリメントしますc。範囲の終わりを過ぎると、デクリメントしますc。

c0 から 1 になると、それが最終セットの範囲の開始です。がc1 から 0 になると、それが範囲の終わりです。

編集::データベーステーブルのどこかにすでに範囲がある場合は、おそらくSQLクエリを構築して上記の最初のステップを実行できます(繰り返しますが、範囲の開始点が範囲の終了点の前に返されるようにします)。

于 2011-04-06T14:16:29.170 に答える
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 に答える
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 に答える