Блог

Есть ли метод, более быстрый по производительности, чем выполнение этого:

 var value = 2432; 

if (value >= 20 amp;amp; value <= 31) return true;
else if (value >= 45 amp;amp; value <= 47) return true;
else if (value >= 82 amp;amp; value <= 86) return true;
...
else if (value >= 1052 amp;amp; value <= 1065) return true;
else if (value >= 2400 amp;amp; value <= 2500) return true;
 

Условные операторы содержат числа, которые не входят в шаблон. Их число достигает 65 000. Кроме того, диапазоны являются переменными и не пересекаются друг с другом. Диапазон хранится в базе данных SQL:

 columns: from, to
rows: [21, 59], [92, 280], etc...
 

Изначально я думал о создании таблицы поиска, содержащей все числа между диапазонами (например, [20, 21, 21, 23, ... 31, -> 45, 46 47] ).

Есть ли лучший способ?

Так что, если диапазоны уникальны и не пересекаются друг с другом. Самый быстрый способ проверить, я вижу, чтобы быть следующим алго:

1. составьте список пар [начало, конец] или просто используйте два отдельных списка для начальных и конечных точек.
2. сортируйте их(это можно было бы сделать очень легко на стороне SQL)
3. используя двоичный поиск, найдите первое start значение, которое больше вашего номера ссылки
4. предыдущий пункт дает вам только один диапазон, который вы должны сверить со своим справочным номером.

Если сортировка выполняется на стороне БД, то этот алгоритм будет O(logN), что достаточно быстро.

Вы могли бы создать массив [start, end] массивов:

 const ranges = [
    [20, 31],
    [45, 47],
    [82, 86],
    // …
    [1052, 1065],
    [2400, 2500]
  ];
 

Затем используйте Array.prototype.find или Array.prototype.some , чтобы найти диапазон, value в котором находится a (например let value = 2432; ):

 ranges.find(([start, end]) => value >= start amp;amp; value <= end); // Returns `[2400, 2500]`, which is the range the value is in, or
!!ranges.find(([start, end]) => value >= start amp;amp; value <= end); // Returns `true`, since the value is in a range, or
ranges.some(([start, end]) => value >= start amp;amp; value <= end); // Returns `true`, since the value is in a range, or
 

Вы, безусловно, можете уменьшить количество условных операторов, которые вам нужно написать.

Предполагая , что ваши массивы «от-до» поступают с сервера в форме [ [n1, n2], [n3, n4], ... ] , вы можете перебирать каждый из ваших диапазонов и return из функции, как только у вас будет совпадение, или возвращать false в противном случае:

 let ranges = [ [20, 31], [45, 47] ];
let valueInRange = 46;
let valueNotInRange = 33;

function isValInRange(value, rangeArr) {
    for(let i = 0; i < rangeArr.length; i  ) {
        if(value >= rangeArr[0] amp;amp; value <= rangeArr[1]) {
            return true;
    }
    return false;
}

console.log(isValInRange(valueInRange, ranges)); //true
console.log(isValInRange(valueNotInRange, ranges)); //false
 

Если вы можете выполнить запрос в sql и нет пересечения, то просто создайте таблицу со всеми возможными значениями от 1 до 65000 и укажите столбец bool, если число допустимо с индексами. Вы действительно получаете удар только по производительности обновления с точки зрения производительности. В этом случае сделайте:

 Value isRange
1     true
 

ВЫБЕРИТЕ * ИЗ таблицы диапазонов, где Значение = @Значение и isRange = true

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

Вы часто обновляетесь?

Если вы собираетесь проверять эти значения значительно чаще, чем будете обновлять их, одним из вариантов было бы построить дерево с диапазонами и искать его немного быстрее, чем повторять все варианты. Однако вы захотите сохранить дерево сбалансированным, иначе это не принесет вам большой пользы.

 /*
  Construct this dynamically
  min: range minimum
  max: range maximum
  lt: node for ranges less than this range
  gt: node for ranges greater than this range
  I'd probably make a class for this.
*/
const ranges = {
  min: 82,
  max: 86,
  lt: {
    min: 45,
    max: 47,
    lt: {
      min: 20,
      max: 31
    }
  },
  gt: {
    min: 2400,
    max: 2500,
    lt: {
      min: 1052,
      max: 1065
    }
  }
};

function lookup(value) {
  let current = ranges;
  while (current) {
    if (value < current.min) {
      current = current.<
    } else if (value > current.max) {
      current = current.>
    } else {
      return true;
    }
  }
  return false;
}
 

Это, по сути, делает это для ценности:

1. Перейдите на средний диапазон.
2. Если текущий узел равен нулю, верните значение false (значение не находится ни в каком диапазоне).
3. Если значение находится в текущем диапазоне, верните значение true (значение находится в диапазоне).
4. Если значение меньше текущего минимального значения, перейдите в средний диапазон меньше текущего и вернитесь к шагу 2.
5. Если значение больше максимального значения тока, перейдите в средний диапазон, превышающий текущий, и вернитесь к шагу 2.