Распространение диапазонов номеров

Question

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

Учитывая набор диапазонов чисел, то есть 1-1000, 1500-1600, довольно просто создать mysql, где условие для выбора записей, которые находятся между этими значениями.

т.е. вы бы просто сделать:

WHERE (lft BETWEEN 1 and 1000) OR (lft BETWEEN 1500-1600). Однако, если вы хотите включить НЕ МЕЖДУ.

Например, если определить несколько правил, как ...

• ПОЗВОЛЯЮТ МЕЖДУ 1 - 1000
• ПОЗВОЛЯЮТ МЕЖДУ 1500 - 1600
• ПОЗВОЛЯЮТ МЕЖДУ 1250 - 1300
• ОТРИЦАТЬ МЕЖДУ 25 - 50

Как слить эти правила, чтобы эффективно генерировать условие WHERE. Мне хотелось бы, чтобы ГДЕ нужно было вскрыть ALLOW BETWEEN 1 - 1000, чтобы создать пробел в нем. Чтобы это стало 1-24 и 51-1000. Поскольку правило DENY определено после первого правила, оно «перезаписывает» предыдущие правила.

В качестве другого примера, Скажите, что у вас есть

• ПОЗВОЛЯЮТ МЕЖДУ 5 - 15
• ОТРИЦАТЬ МЕЖДУ 10 - 50
• ПОЗВОЛЯЮТ МЕЖДУ 45 - 60

Тогда я хотел бы для создания условия ГДЕ, которое позволило бы мне:

WHERE (lft BETWEEN 5 and 9) OR (lft BETWEEN 45 and 60).

Notes (редактирование)

• Кроме того, максимальный диапазон, который когда-либо разрешено 1 - 5600000. (который будет 'Земля'), то есть. Разрешить все на Земле.
• Диапазоны чисел на самом деле являются значениями LEFT в модели NESTED SET. Это не уникальные ключи. Вы можете прочитать, почему я хочу сделать это в этом вопросе, который я задал ранее. https://stackoverflow.com/questions/6020553/generating-a-mysql-between-where-condition-based-on-an-access-ruleset
• Возможное важное замечание на мой номер в диапазоне я, возможно, не следовало бы использовать образец пример, который я сделал, но один важное замечание о природе числа диапазонов является то, что диапазоны должны фактически всегда полностью потреблять или потребляется по предыдущему правилу. Например, я использовал пример выше, 10-50 разрешить и отклонить 45-60. На самом деле это никогда не произойдет в моем наборе данных. На самом деле это будет allow 10-50, тогда DENY придется либо полностью поглотить этот диапазон, т. Е. 34-38. ИЛИ, полностью потребляют предыдущее правило. 9-51. Это потому, что диапазоны на самом деле представляют значения lft и rgt во вложенной модели модели, и вы не можете иметь перекрытия, как я представил.

Я не думал упоминать это, задавая вопрос, но, увидев рабочий пример кода ниже, я вижу, что эта заметка на самом деле важна.

(Отредактированный пример MySQL, чтобы включить или вместо AND, как в комментарии ниже)

Answer 1

Честно говоря, зачем беспокоиться? До тех пор, пока ключ вы запрашивая против индексируется, просто поставить несколько запросов там:

WHERE (foo BETWEEN 1 AND 1000 
     OR foo BETWEEN 1500 AND 1600 
     OR foo BETWEEN 1250 AND 1300 
    ) AND (
     foo NOT BETWEEN 25 AND 50 
    ) 

Вы можете СЖАТИЕ небольшого битой эффективности пути создания прозектора, но я бы вопрос, если это стоит. Все элементы предложения WHERE будут отключены от индекса, поэтому вы не предотвращаете какую-либо сложную операцию (это означает, что вы не останавливаете сканирование полного стола, делая это).

Поэтому, вместо того, чтобы тратить время на создание системы, чтобы сделать это за вас, просто реализуйте простое решение (OR соединять «Разрешения» и AND вместе с Denys) и перейти к более важным вещам. Тогда, если это станет проблемой позже, перейдите затем. Но я действительно не думаю, что это когда-нибудь станет слишком большой проблемой ...

Редактировать Хорошо, вот очень простой алгоритм для этого. Он использует строки в качестве хранилища данных, так что это достаточно эффективно для небольших чисел (ниже 1 миллион):

class Dissector { 
    protected $range = ''; 
    public function allow($low, $high) { 
     $this->replaceWith($low, $high, '1'); 
    } 
    public function deny($low, $high) { 
     $this->replaceWith($low, $high, '0'); 
    } 
    public function findRanges() { 
     $matches = array(); 
     preg_match_all(
      '/(?<!1)1+(?!1)/', 
      $this->range, 
      $matches, 
      PREG_OFFSET_CAPTURE 
     ); 
     return $this->decodeRanges($matches[0]); 
    } 
    public function generateSql($field) { 
     $ranges = $this->findRanges(); 
     $where = array(); 
     foreach ($ranges as $range) { 
      $where[] = sprintf(
       '%s BETWEEN %d AND %d', 
       $field, 
       $range['from'], 
       $range['to'] 
      ); 
     } 
     return implode(' OR ', $where); 
    } 
    protected function decodeRanges(array $matches) { 
     $range = array(); 
     foreach ($matches as $match) { 
      $range[] = array(
       'from' => $match[1] + 1, 
       'to' => ($match[1] + strlen($match[0])) 
      ); 
     } 
     return $range; 
    } 
    protected function normalizeLengthTo($size) { 
     if (strlen($this->range) < $size) { 
      $this->range = str_pad($this->range, $size, '0'); 
     } 
    } 
    protected function replaceWith($low, $high, $character) { 
     $this->normalizeLengthTo($high); 
     $length = $high - $low + 1; 
     $stub = str_repeat($character, $length); 
     $this->range = substr_replace($this->range, $stub, $low - 1, $length); 
    } 
} 

Использование:

$d = new Dissector(); 
$d->allow(1, 10); 
$d->deny(5, 15); 
$d->allow(10, 20); 
var_dump($d->findRanges()); 
var_dump($d->generateSql('foo')); 

Формирует:

array(2) { 
    [0]=> 
    array(2) { 
    ["from"]=> 
    int(1) 
    ["to"]=> 
    int(4) 
    } 
    [1]=> 
    array(2) { 
    ["from"]=> 
    int(10) 
    ["to"]=> 
    int(20) 
    } 
} 
string(44) "foo BETWEEN 1 AND 4 OR foo BETWEEN 10 AND 20" 

Answer 2

Я обрабатывал бы инструкции по одному, создавая список номеров, которые должны быть включены. Затем, наконец, переведем этот список в набор диапазонов для предложения where. Вот несколько псевдокодов:

$numbers = array(); 
foreach (conditions as $condition) { 
    if ($condition is include) { 
     for ($i = $condition.start; $i <= $condition.end; $i++) { 
      $numbers[$i] = true; 
     } 
    } else { 
     for ($i = $condition.start; $i <= $condition.end; $i++) { 
      unset($numbers[$i]); 
     } 
    } 
} 
ksort($numbers); 

Answer 3

Я провел немного время, пытаясь решить это (это аккуратная проблема), и придумал это. Это не является оптимальным, при этом я не гарантирует, что это прекрасно, но это, возможно, вы начали:

<?php 

/*$cond = array(
    array('a', 5, 15), 
    array('d', 9, 50), 
    array('a', 45, 60) 
);*/ 

$cond = array(
    array('a', 1, 1000), 
    array('a', 1500, 1600), 
    array('a', 1250, 1300), 
    array('d', 25, 50) 
); 

$allow = array(); 

function merge_and_sort(&$allow) 
{ 
    usort($allow, function($arr1, $arr2) 
    { 
     if ($arr1[0] > $arr2[0]) 
     { 
      return 1; 
     } 
     else 
     { 
      return -1; 
     } 
    }); 

    $prev = false; 

    for ($i = 0; $i < count($allow); $i++) 
    { 
     $c = $allow[$i]; 
     if ($i > 0 && $allow[$i][0] < $allow[$i - 1][1]) 
     { 
      if ($allow[$i][1] <= $allow[$i - 1][1]) 
      { 
       unset($allow[$i]); 
      } 
      else 
      { 
       $allow[$i - 1][1] = $allow[$i][1]; 
       unset($allow[$i]); 
      } 
     } 
    } 

    usort($allow, function($arr1, $arr2) 
    { 
     if ($arr1[0] > $arr2[0]) 
     { 
      return 1; 
     } 
     else 
     { 
      return -1; 
     } 
    }); 
} 

function remove_cond(&$allow, $start, $end) 
{ 
    for ($i = 0; $i < count($allow); $i++) 
    { 
     if ($start > $allow[$i][0]) 
     { 
      if ($end <= $allow[$i][1]) 
      { 
       $temp = $allow[$i][1]; 
       $allow[$i][1] = $start; 
       $allow []= array($end, $temp); 
      } 
      else 
      { 
       $found = false; 
       for ($j = $i + 1; $j < count($allow); $j++) 
       { 
        if ($end >= $allow[$j][0] && $end < $allow[$j][1]) 
        { 
         $found = true; 
         $allow[$j][0] = $end; 
        } 
        else 
        { 
         unset($allow[$j]); 
        } 
       } 

       if (!$found) 
       { 
        $allow[$i][1] = $start; 
       } 
      } 
     } 
    } 
} 

foreach ($cond as $c) 
{ 
    if ($c[0] == "a") 
    { 
     $allow []= array($c[1], $c[2]); 

     merge_and_sort($allow); 
    } 
    else 
    { 
     remove_cond($allow, $c[1], $c[2]); 
     merge_and_sort($allow); 
    } 
} 

var_dump($allow); 

Последние var_dump выходы:

array(4) { 
    [0]=> 
    array(2) { 
    [0]=> 
    int(1) 
    [1]=> 
    int(25) 
    } 
    [1]=> 
    array(2) { 
    [0]=> 
    int(50) 
    [1]=> 
    int(1000) 
    } 
    [2]=> 
    array(2) { 
    [0]=> 
    int(1250) 
    [1]=> 
    int(1300) 
    } 
    [3]=> 
    array(2) { 
    [0]=> 
    int(1500) 
    [1]=> 
    int(1600) 
    } 
} 

Edited использовать первый пример вместо второго.

Answer 4

Я спросил у IRC и получил два ответа. Я собираюсь опубликовать их оба, чтобы другие люди могли выиграть (и чтобы я не потерял их, так как я подробно рассмотрю их в ближайшее время).

Пример 1 TML

<pre><?php 

$cond = array(
    array('a', 5, 15), 
    array('a', 5, 15), 
    array('d', 9, 50), 
    array('a', 45, 60), 
    array('a', 2, 70), 
    array('d', 1, 150), 
); 



function buildAcl($set) { 
    $allow = array(); 
    foreach($set as $acl) { 
     $range = range($acl[1], $acl[2]); 
     switch($acl[0]) { 
      case 'a': 
       $allow = array_unique(array_merge(array_values($allow), $range)); 
       break; 
      case 'd': 
       foreach($range as $entry) { 
        unset($allow[array_search($entry, $allow)]); 
       } 
     } 
    } 
    return $allow; 
} 

var_dump(buildAcl($cond)); 
var_dump(buildAcl(array(array('a', 5, 15), array('d', 10, 50), array('a', 45, 60)))); 

Пример 2 (matslin)

<?php 
$conds = array(
    array('a', 5, 15), 
    array('a', 5, 15), 
    array('d', 9, 50), 
    array('a', 45, 60), 
    array('a', 2, 70), 
    array('d', 1, 150), 
); 

$segments = array(); 

foreach($conds as $cond) 
{ 
    print($cond[0] . ': ' . $cond[1] . ' - ' . $cond[2] . "\n"); 
    if ($cond[0] == 'a') 
    { 
     $new_segments = array(); 
     $inserted = false; 
     $prev_segment = false; 

     foreach($segments as $segment) 
     { 
      if ($segment['begin'] > $cond[2]) 
      { 
       $new_segments[] = array('begin' => $cond[1], 'end' => $cond[2]); 
       $new_segments[] = $segment; 
       $inserted = true; 
       print("begun\n"); 
       continue; 
      } 

      if ($segment['end'] < $cond[1]) 
      { 
       print("end\n"); 
       $new_segments[] = $segment; 
       continue; 
      } 

      if ($cond[1] < $segment['begin']) 
      { 
       $segment['begin'] = $cond[1]; 
      } 

      if ($cond[2] > $segment['end']) 
      { 
       $segment['end'] = $cond[2]; 
      } 

      $inserted = true; 

      if (
       $prev_segment && 
       ($prev_segment['begin'] <= $segment['begin']) && 
       ($prev_segment['end'] >= $segment['end']) 
      ) 
      { 
       print("ignore identical\n"); 
       continue; 
      } 

      print("default\n"); 
      $prev_segment = $segment; 
      $new_segments[] = $segment; 
     } 

     if (!$inserted) 
     { 
      print("inserted at end\n"); 
      $new_segments[] = array('begin' => $cond[1], 'end' => $cond[2]); 
     } 

     $segments = $new_segments; 
     print("---\n"); 
    } 

    if ($cond[0] == 'd') 
    { 
     $new_segments = array(); 

     foreach($segments as $segment) 
     { 
      # not contained in segment 
      if ($segment['begin'] > $cond[2]) 
      { 
       print("delete segment is in front\n"); 
       $new_segments[] = $segment; 
       continue; 
      } 

      if ($segment['end'] < $cond[1]) 
      { 
       print("delete segment is behind\n"); 
       $new_segments[] = $segment; 
       continue; 
      } 

      # delete whole segment 
      if (
       ($segment['begin'] >= $cond[1]) && 
       ($segment['end'] <= $cond[2]) 
      ) 
      { 
       print("delete whole segment\n"); 
       continue; 
      } 

      # delete starts at boundary 
      if ($cond[1] <= $segment['begin']) 
      { 
       print("delete at boundary start\n"); 
       $segment['begin'] = $cond[2]; 
       $new_segments[] = $segment; 
       continue; 
      } 
      # delete ends at boundary 
      if ($cond[2] >= $segment['end']) 
      { 
       print("delete at boundary end\n"); 
       $segment['end'] = $cond[1]; 
       $new_segments[] = $segment; 
       continue; 
      } 

      # split into two segments 
      print("split into two\n"); 
      $segment_pre = array('begin' => $segment['begin'], 'end' => $cond[1]); 
      $segment_post = array('begin' => $cond[2], 'end' => $segment['end']); 

      $new_segments[] = $segment_pre; 
      $new_segments[] = $segment_post; 
     } 

     print("--\n"); 
     $segments = $new_segments; 
    } 

    print("----\n"); 
    var_dump($segments); 
    print("----\n"); 
} 

var_dump($segments);