Быстрая проверка на пересечение диапазонов

Далее называемое ТС диапазоном, я назову множеством - {}.
Меня данное определение ТС запутывает (корректность?).

Без гарантий:
Лучше логарифма..., единиц..., только в обратную сторону.

Установим в элементе {e} биты, допускающие изменения,
соотв. битам begin.
Это будет к begin ближайший (<) или ближайший (>),
но не факт, что ближайший вообще.

ЕСЛИ {e} >= begin ТО
ЕСЛИ {e} <= (begin + size) ТО пересечение найдено: выход. кЕСЛИ
ИНАЧЕ найдем ближайший (>): {e} = {e} '+' {1}
'+' естественно ТОЛЬКО по битам допускающим изменения.
ЕСЛИ {e} <= (begin + size) ТО пересечение найдено: выход. кЕСЛИ
кЕСЛИ
пересечение не найдено: выход.

P.S. Я в си и вообще в скриптах "не копенгаген", а на Asm
и сами можете проверить - ваша же задача.

--- Сообщение объединено, 9 мар 2023 ---

Ошибся - нашел контрпримеры - не получаются ближайшие так просто.

 

а что мешает изменить принцип маски и тем самым получить более простое да быстрое решение? тормознутая маска - это ж совсем дно

 

Может быть искать ближайший итерационно: делением пополам оставшегося подмножества {}, но там опять же логарифм(((.

 

UbIvItS,
Ну, давай, обгони мой пример по скорости. А то я вообще не понимаю, что такое "тормознутая маска" и как изменить ее принцип

Можно псевдокодом и для 4-битных чисел, чтобы многабуков не читать.
Вот множество (value 1100, mask 1100):
1100
1101
1110
1111
Проверяемый диапазон: begin 0001, end 0100.

Как тут будет выглядеть "быстрая" маска?

 

rmn, ну - во1ых отказываемся от value и у нас что за задача? выяснить есть ли пересечения. задаём маски и определяем расстояние..
M1 = [m1] [m2] [m3] [m4] // mask 1
M2 = [m21] [m22] [m23] [m24] // mask 2
max_domain = new dom(4) // dom is 4-bit number
min_domain = new dom(4)
sub = new dom(4)
D = [d1] [d2] [d3] [d4]
tst = [t1] [t2] [t3] [t4]
=======
rst1 = M1 ^ tst
rst2 = M2 ^ tst
max_domain(i) = max(rst1, rst2, i) | i=1..4
min_domain(i) = min(rst1, rst2, i) | i=1..4
sub(i) = max_domain(i) - min_domain(i) | i=1..4
[sub(i) > get_domain(D, i)] then NoIntersect() | i=1..4
otherwise GotIntersect();
>>>>>>>>>>>>
для начала как-то так

 

UbIvItS,
а теперь конкретные нули и единички проставь вместо переменных для множества выше, чтобы видно было, что оно работает

 

неа, пущай другие ставят, кому оное требуется

 

А, ну тогда понятно

 

а что тебе собсно не по нраву? обычный скучно-линейный алго. иль ошибку узрел?

 

Пока я не узрел, что он вообще способен решить поставленную задачу. Больше смахивает на какую-то псевдонаучную х.ету

 

Тебе что именно непонятно?

 

Непонятно, чему должны быть равны M1 ,M2, min_domain, max_domain, D, tst, sub, чтобы определить принадлежность элементов множества
1100
1101
1110
1111
диапазону 0001..0100.

И, что самое главное: как M1, M2, min_domain, max_domain, D, tst и sub должны быть получены из пары 1100 & 1100.

Вот такая малость, остальное, вроде, понятно

 

rmn, схема ТС приводит к проблемам, поэтому я и предложил другую схему. подходит ли ему эта другая схема - Вопрос. и, конечно, входные данные несовместимые.

M1 и М2 - ручной ввод, задаёт маски фильтрации.
D - ручной ввод, задаёт расстояние между векторами.
tst - ручной ввод, алго проверяет наличие этого вектора в двух множествах. вектор tst принадлежит двум множествам, если расстояние между векторами rst1 & rst2 < D.

вот отображение tst для каждого множества.

 

UbIvItS,
А, ну то есть, твой мотор решает какую-то твою, не имеющую никакого отношения к ТС задачу. Ясно, понятно

 

rmn, проверил со всеми правками (RangeBits, поменял местами min/max, добавил проверку на mask == 0) - и не работает :\
Проверь на входных данных:

Код (C):

1.  
2. 0000_0000 begin
3. 0000_0001 end
4.  
5. 0000_0001 value
6. 0000_0001 mask
7. ============
8. ????_???1 range
9.  

Должно вернуть true, твой вариант возвращает false.

 

Эх... придется все-таки компилить...

--- Сообщение объединено, 10 мар 2023 ---

HoShiMin,
В функции MaybeIntersects должно быть && (range->value <= end)

--- Сообщение объединено, 10 мар 2023 ---

Так же, раз нам экстремальные значения множества известны, можно немного ускориться, написав в Intersects:

Код (C):

1.  
2.     ...
3.     result = Range_ComparePoint (range->value /* minPoint */, begin, end);
4.  
5.     if (result < 0)
6.         return false;
7.  
8.     if (result == 0)
9.         return true;
10.  
11.     result = Range_ComparePoint (range->value | ~range->mask /* maxPoint */, begin, end);
12.     ...
13.  

 

Че там проверять, конкретно в этом случае, если size >= 1, то сразу true.
Если size = 0, то инвертировать (begin^value) & 1
А если например, младший еденичный бит маски(И бит value в нём =1) весит больше чем, begin+size, то сразу 0
ну и т.д.

 

HoShiMin, так ты конкретизируй, где именно тебе весь этот маскарад нужен.

 

В x86 у нас есть набор MTRR-регистров, определяющих, какой тип кэширования будет иметь память:


Если выполняется условие (Addr & MTRR.PhysMask) == (MTRR.PhysBase & MTRR.PhysMask), значит к адресу применяется тип MTRR.Type.

Мне надо составить таблички трансляций в EPT, а для этого необходимо каждой страничке прописать её тип.
Сейчас это выглядит так:


Мы бежим по каждой страничке и получаем для неё тип на 49й и 60й строчках, проверяя каждую страничку той функцией для каждого MTRR, а затем "смешиваем" совпавшие типы.



Хочется немного оптимизировать: посчитать один раз тип, например для одного PDPTE или сразу для одного PDE, а для этого и необходимо искать такие пересечения, как в первом посте.

 

HoShiMin, и какие паттерны маски наиболее вероятны в твоём случае?