Лучший Алгоритм поиска пересечения между 2 Интервалы

-1

У меня есть таблица в базе данных под названием Control:Лучший Алгоритм поиска пересечения между 2 Интервалы

Структура таблицы:

Id | Имя | MinValue (десятичный) | MaxValue (десятичное)

У меня есть некоторые ограничения на эту таблицу, один из его ограничений нет: нет перекрестков.

Пример: если таблица имеет некоторые значения следующим образом:

Row1: 1 | Test1 | 1.3 | 2.5 // действует
row2: 2 | Test2 | 3,3 | 4.5 // действует
row3: 3 | Test3 | 5 | 6 // действует

Теперь, если я хочу, чтобы добавить новую запись, она не должна пересекаться с какой-либо другой строки

Пример:

row4: 4 | Test4 | 5.1 | 10 // не имеет значения номер с 5 до 6 зарезервирован
row5: 5 | Test5 | 1.0 | 1,4 // не действует, поскольку слот от 1,3 до 2,5 зарезервирован

Я использую этот код, и он работал отлично, но мне интересно, если есть лучшее решение, и более эффективным:

var allRows = db.Control.ToList(); 
var minValue = control.MinimumValue; 
var maxValue = control.MaximumValue; 
bool flag = true; 
foreach(var row in allRows) 
{ 
    for(var i = minValue; i <= maxValue && flag ; i = decimal.Add(i , (decimal) 0.01)) 
    { 
     if(i >= row.MinimumValue && i <= row.MaximumValue) 
     { 
      flag = false; 
      min = row.MinimumValue; 
      max = row.MaximumValue; 
      break; 
     } 
    } 
} 

if (flag) 
{ 
    //add 
} 
else 
{ 
    //intersection 
}

Любые предложения?

источник

2016-10-02 BaDr Amer

Eсть нет такой вещи, как «пересечение между двумя точками». Точка - это почти единственное геометрическое понятие, которое не может пересекаться с другим. –

Внутренний цикл не имеет смысла, есть перекрытие, если minValue row.minValue. Выводит его из O (n * m) в O (n). Вы также можете оптимизировать его до O (log (n)) с помощью SortedList. –

не работал, @HansPassant –

Давайте предположим, что это объект, который вы пытаетесь добавить:

var control = new Control() 
{ 
    Name = 'name', 
    MinValue = 5, 
    MaxValue = 6 
};

Вы можете сделать следующее:

var biggerThanMinValue = db.Control.Count(x => x.MinValue >= control.MinValue) != 0; 
var biggerThanMaxValue = db.Control.Count(x => x.MaxValue >= control.MaxValue) != 0; 
if (!biggerThanMinValue && !biggerThanMinValue) 
{ 
    db.Control.Add(control); // or whatever your add operation is 
}

Поступая таким образом вам:

делать НЕ загрузить всю таблицу в памяти -> коэффициенты увеличения производительности, времени и трафика
позволяют базе данных использовать свои структуры данных/алгоритмы для проверки того, что элемент может быть добавлен (db должен иметь возможность оптимизировать этот запрос) -> другое усиление производительности (cpu + time)
имеет более четкий код доступа
есть меньше кода для проверки

Редактирование: Я полагаю, вы также можете попросить базу данных отсортировать таблицу по минимальному/максимальному значению, а затем выполнить некоторую проверку (1 или 2 ifs), но первый подход лучше, imo.

источник

2016-10-02 10:47:56 hiho

не работает, не улавливает все случаи: например: , если таблица содержит MinValue = 7 и MaxValue = 9 и я хочу, чтобы добавить MinValue = 10 и maxValue = 12 Что происходит в соответствии с вашим решением? –

Я обновил свой ответ – hiho

Я думаю, что это вопрос O(LogN) ...

Держите сегменты, заказанные их начальное значение.
в действительном списке s[i].end < s[i+1].start для любого i

при вставке нового сегмента, найти его положение (тот, которые начинаются ближе всего (но меньше), чем ваш новый сегмент) называют его i

if((seg[i-1].end < new.start) && (seg[i+1].start > new.end)) 
    //OK to insert 
else 
    // intersect

источник

2016-10-02 10:53:30

Я не понял ваше утверждение «Держать сегменты по их стартовому значению» Что вы имели в виду по сегменту? содержит ли оно десятичное значение? –

добавлено «Упорядочено», чтобы уточнить мое намерение. Спасибо за комментарий –

Лучший Алгоритм поиска пересечения между 2 Интервалы

ответ

Смежные вопросы