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

Мы задаём диапазон двумя битмапами: в первой значения битов, во второй - маска значащих битов первой битмапы.
Если в маске бит равен 0, то в этой позиции бит может быть любым.
Если в маске бит равен 1, то в этой позиции бит должен быть таким же, как значение бита в первой битмапе в той же позиции.

Пример:

Код (Text):

1.  
2. Value : 0110_1100
3. Mask  : 0111_1101
4. =================
5. Range : ?110_11?0
6.  

Проверить число на вхождение в диапазон можно следующим образом:

Код (C++):

1.  
2. struct Range
3. {
4.     size_t value;
5.     size_t mask;
6.  
7.     bool isMatches(size_t desired) const
8.     {
9.         return (desired & mask) == (value & mask);
10.     }
11. };
12.  
13. ...
14.  
15. Range range{};
16. // ?110_1??1:
17. range.value = 0b01101001;
18. range.mask  = 0b01111001;
19.  
20. assert(range.isMatches(0b01111001) == false);
21. assert(range.isMatches(0b11101111) == true);
22.  

Можно ли переписать isMatches, чтобы она проверяла не конкретное число, а интервал чисел [begin, begin + size), что хотя бы одно из чисел из интервала попало в диапазон, за константное время, не зависящее от size?

Код (C++):

1.  
2. struct Range
3. {
4.     size_t value;
5.     size_t mask;
6.  
7.     // Проверяем [begin, begin + size):
8.     bool isIntersects(size_t begin, size_t size) const
9.     {
10.         const auto end = begin + size - 1;
11.         return ???;
12.     }
13. };
14.  

 

Использовать begin..end как диапазон и проверять принадлежность ему всех валидных value.
Например, при использовании указанной маски ?110_1??1, понадобится максимум 8 сравнений при любых begin..size.

Да, и value в структуре можно сразу хранить как value & mask, тогда не надо будет делать value & mask каждый раз при сравнениях.

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

Алгоритм перебора value может быть такой:
Берем самый старший нефиксированный бит, устанавливаем его в 1, остальные нефиксированные (младшие) биты в 0. Если значение > end - конец, диапазоны не пересекаются. Иначе, устанавливаем его в 0, остальные нефиксированные (младшие) - в 1. Если значение < begin - конец, диапазоны не пересекаются. Иначе обнуляем этот бит, берем следующий нефиксированный бит и повторяем цикл.

 

Имеешь в виду, перебрать все возможные комбинации вместо знаков вопроса (3 знака в маске = 2^3 = 8)? Если да, то в случае 64х-битных масок перебрать все комбинации будет невозможно.

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

Если правильно понял, в твоём алгоритме понадобится 2 * (sizeof(mask) * 8) сравнений? Но ведь это покроет не все возможные комбинации.

 

А все и не нужно, достаточно экстремальные.
Если у нас маска x??x???x, то x00x000x - это минимальное число в этом множестве, а x11x111x - максимальное. Получается, даже цикл не нужон, двух сравнений должно хватить

Да, вроде правильно все:

Код (Text):

1.  
2. value   B8  1011 1000
3. mask    CD  1100 1101
4. min     88  1000 1000
5. max     BA  1011 1010
6.             10xx 10x0
7.         88  1000 1000
8.         8A  1000 1010
9.         98  1001 1000
10.         9A  1001 1010
11.         A8  1010 1000
12.         AA  1010 1010
13.         B8  1011 1000
14.         BA  1011 1010
15.  

 

rmn, только сейчас дошли руки проверить.

Если я правильно понял, проверка должна выглядеть так:

Код (C):

1.  
2. bool isIntersects(uint64_t begin, uint64_t end, BitRange<uint64_t> range)
3. {
4.     const auto lowestRange = range.baseAndMask(); // Все произвольные биты сброшены
5.     const auto highestRange = range.baseAndMask() | ~range.mask(); // Взводим все произвольные биты
6.     return (lowestRange <= begin) && (end <= highestRange);
7. }
8.  

Проверим:

Код (Text):

1.  
2. 0000_0000 begin
3. 0000_0001 end
4.  
5. 0000_0001 base
6. 0000_0001 mask
7. =====================
8. ????_???1 range = (base & mask)
9. 0000_0001 base & mask
10.  
11. 0000_0001 base & mask (lowest)
12. 1111_1111 (base & mask) | ~mask (highest)
13.  

isIntersects вернёт false, т.к. begin у нас меньше, чем (base & mask), а должен вернуть true, т.к. end подпадает под критерий.

 

HoShiMin,
Проверка диапазонов на пересечение, это (min <= end && max >= begin), вообще-то. Это вам не расты с петонами хвалить на форумах

Код (C):

1.  
2. bool intersects (uint32_t value, uint32_t mask, uint32_t begin, uint32_t end)
3. {
4.     return ((value | ~mask) >= begin) && ((value & mask) <= end);
5. }
6.  

 

rmn, но тоже не работает:

Код (Text):

1.  
2. 0000_0000 begin
3. 0000_0001 end
4.  
5. 0000_0010 value
6. 0000_0000 mask
7. ==============
8. ????_???? range
9. 0000_0010 (value | mask)
10. 0000_0010 (value & ~mask)
11.  

Не выполняется условие (value & ~mask) <= end, intersects возвращает false, а должен true

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

Пример тестов:

Код (C):

1.  
2. template <typename BaseType>
3. bool isMatches(BaseType addr, BaseType base, BaseType mask)
4. {
5.     return (addr & mask) == (base & mask);
6. }
7.  
8. template <typename BaseType>
9. class BitRange
10. {
11. private:
12.     BaseType m_base;
13.     BaseType m_mask;
14.     BaseType m_baseAndMask;
15.  
16. public:
17.     template <size_t size>
18.     static constexpr BitRange make(const char(&mask)[size]) noexcept
19.     {
20.         constexpr BaseType k_bitSize = sizeof(BaseType) * 8;
21.         BitRange bitMask{};
22.         BaseType delimCount = 0;
23.         for (auto i = 0; i < sizeof(mask); ++i)
24.         {
25.             switch (mask[i])
26.             {
27.             case '0':
28.             {
29.                 bitMask.m_base &= ~(BaseType(1) << BaseType(k_bitSize - (i - delimCount) - 1));
30.                 bitMask.m_mask |= BaseType(1) << BaseType(k_bitSize - (i - delimCount) - 1);
31.                 break;
32.             }
33.             case '1':
34.             {
35.                 bitMask.m_base |= BaseType(1) << BaseType(k_bitSize - (i - delimCount) - 1);
36.                 bitMask.m_mask |= BaseType(1) << BaseType(k_bitSize - (i - delimCount) - 1);
37.                 break;
38.             }
39.             case '?':
40.             {
41.                 bitMask.m_base &= ~(BaseType(1) << BaseType(k_bitSize - (i - delimCount) - 1));
42.                 bitMask.m_mask &= ~(BaseType(1) << BaseType(k_bitSize - (i - delimCount) - 1));
43.                 break;
44.             }
45.             case '\'':
46.             case ' ':
47.             case '_':
48.             {
49.                 ++delimCount;
50.                 break;
51.             }
52.             }
53.         }
54.  
55.         bitMask.m_baseAndMask = bitMask.m_base & bitMask.m_mask;
56.         return bitMask;
57.     }
58.  
59.     constexpr BitRange() noexcept
60.         : m_base(0)
61.         , m_mask(0)
62.         , m_baseAndMask(0)
63.     {
64.     }
65.  
66.     constexpr BitRange(BaseType base, BaseType mask) noexcept
67.         : m_base(base)
68.         , m_mask(mask)
69.         , m_baseAndMask(base & mask)
70.     {
71.     }
72.  
73.     constexpr BitRange& setBase(BaseType base) noexcept
74.     {
75.         m_base = base;
76.         m_baseAndMask = m_base & m_mask;
77.         return *this;
78.     }
79.  
80.     constexpr BitRange& setMask(BaseType mask) noexcept
81.     {
82.         m_mask = mask;
83.         m_baseAndMask = m_base & m_mask;
84.         return *this;
85.     }
86.  
87.     constexpr BaseType base() const noexcept
88.     {
89.         return m_base;
90.     }
91.  
92.     constexpr BaseType mask() const noexcept
93.     {
94.         return m_mask;
95.     }
96.  
97.     constexpr BaseType baseAndMask() const noexcept
98.     {
99.         return m_baseAndMask;
100.     }
101. };
102.  
103. bool isRangeMatches(unsigned long long begin, unsigned long long end, BitRange<unsigned long long> range)
104. {
105.     return ((range.base() | range.mask()) >= begin) && ((range.base() & ~range.mask()) <= end);
106. }
107.  
108. int main()
109. {
110.     constexpr auto k_testBitCount = 8ull;
111.     constexpr auto k_max = (1ull << k_testBitCount) - 1;
112.     constexpr auto k_addrFrom = 0ull;
113.     constexpr auto k_addrTo = k_max;
114.  
115.     static_assert(k_addrFrom <= k_addrTo);
116.     for (auto startAddr = k_addrFrom; startAddr <= k_addrTo; ++startAddr)
117.     {
118.         for (auto endAddr = startAddr + 1; endAddr <= k_addrTo; ++endAddr)
119.         {
120.             BitRange<unsigned long long> baseMask;
121.             for (auto base = 0ull; base <= k_max; ++base)
122.             {
123.                 baseMask.setBase(base);
124.                 for (auto mask = 0ull; mask <= k_max; ++mask)
125.                 {
126.                     baseMask.setMask(mask);
127.                     bool mustMatch = false;
128.                     for (auto addr = startAddr; addr <= endAddr; ++addr)
129.                     {
130.                         if (isMatches(addr, baseMask))
131.                         {
132.                             mustMatch = true;
133.                             break;
134.                         }
135.                     }
136.                     const bool matchesByTestAlgo = isRangeMatches(startAddr, endAddr, baseMask);
137.                     if (mustMatch != matchesByTestAlgo)
138.                     {
139.                         __debugbreak();
140.                         return -1;
141.                     }
142.                 }
143.             }
144.         }
145.     }
146.  
147.     return 0;
148. }
149.  

 

HoShiMin,
Я пофиксил там. Надо OR с инвертированной маской и AND с обычной.

 

rmn, проверил с новым, тоже не работает:

Код (Text):

1.  
2. 0000_0001 begin
3. 0000_0010 end
4.  
5. 0000_0000 value
6. 0000_0011 mask
7. =============
8. ????_??00 range
9. 1111_1100 (value | ~mask)
10. 0000_0000 (value & mask)
11.  

Оба условия выполняются, intersects возвращает true, но должен false

 

Ну, по крайней мере, если функция вернет false, диапазоны точно не пересекаются Можешь оставить ее как maybe_intersects() для быстрой проверки на первом шаге и если она вернет true, тогда уже делать долгую проверку в цикле.

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

Держи говнокода для тестов

Код (C):

1.  
2. typedef uint32_t    RangeType;
3. #define RangeBits   (sizeof(RangeType) * 8)
4.  
5. typedef struct _Range
6. {
7.     uint8_t shift_table[RangeBits];
8.     uint32_t maskSize;  /* количество нулей в маске */
9.     RangeType value;
10.     RangeType mask;
11. }Range;
12.  
13. static void Range_MakeShiftTable (Range* range, uint32_t mask)
14. {
15.     uint32_t i, j;
16.    
17.     for (i=0, j=0; i<32; i++)
18.     {
19.         if (!(mask & 1))
20.         {
21.             range->shift_table[j] = (uint8_t)(i - j);
22.             j++;
23.         }
24.        
25.         mask >>= 1;
26.     }
27.    
28.     range->maskSize = j;
29. }
30.  
31. static RangeType Range_ValueToPoint (Range* range, RangeType value)
32. {
33.     uint32_t i;
34.     RangeType point;
35.    
36.     for (i = 0, point = range->value; i < range->maskSize; i++)
37.         point |= (value & (1 << i)) << range->shift_table[i];
38.    
39.     return point;
40. }
41.  
42. static int Range_ComparePoint (RangeType value, RangeType begin, RangeType end)
43. {
44.     return ((value < begin) ? -1 : ((value > end) ? 1 : 0));
45. }
46.  
47. static bool Range_LongTest (Range* range, RangeType begin, RangeType end)
48. {
49.     RangeType minValue, maxValue, value;
50.     int result;
51.  
52.     minValue = 0;
53.     maxValue = (1 << range->maskSize) - 1;
54.  
55.     result = Range_ComparePoint (Range_ValueToPoint (range, minValue), begin, end);
56.  
57.     if (result < 0)
58.         return false;
59.  
60.     if (result == 0)
61.         return true;
62.  
63.     result = Range_ComparePoint (Range_ValueToPoint (range, maxValue), begin, end);
64.  
65.     if (result > 0)
66.         return false;
67.  
68.     if (result == 0)
69.         return true;
70.  
71.     while ((maxValue - minValue) > 1)
72.     {
73.         value = minValue + (maxValue - minValue) / 2;
74.  
75.         result = Range_ComparePoint (Range_ValueToPoint (range, value), begin, end);
76.  
77.         if (result == 0)
78.             return true;
79.  
80.         if (result < 0)
81.             maxValue = value;
82.         else
83.             minValue = value;
84.     }
85.  
86.     return false;
87. }
88.  
89. static bool Range_MaybeIntersects (Range* range, RangeType begin, RangeType end)
90. {
91.     return ((range->value | ~mask) >= begin && (range->value < end));
92. }
93.  
94. void Range_Init (Range* range, RangeType value, RangeType mask)
95. {
96.     range->value = value & mask;
97.     range->mask = mask;
98.    
99.     Range_MakeShiftTable (range, mask);
100. }
101.  
102. bool Range_Intersects (Range* range, RangeType begin, RangeType end)
103. {
104.     if (begin > end)
105.     {
106.         begin ^= end;
107.         end ^= begin;
108.         begin ^= end;
109.     }
110.    
111.     return (Range_MaybeIntersects (range, begin, end) ? Range_LongTest (range, begin, end) : false);
112. }
113.  

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

В

Код (C):

1.  
2. for (i=0, j=0; i<32; i++)
3.  

Должно быть

Код (C):

1.  
2. for (i=0, j=0; i<RangeBits; i++)
3.  

 

Без "заворачивания" вроде не "константное", а двоичные логарифмы просятся, точнее от кол-ва единиц в величине qnt=size+1.

 

1ым делом нужно чётко дать определение диапазону - это выглядит, ну, прям дико мутно..

по идее, тру тут возможен, лишь если desired == value.

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

обычно делают так

• return (desired & mask) == mask;

 

Не только:

Код (Text):

1.  
2. 0010_1000 value
3. 0010_1010 mask
4. =============
5. ??1?_1?0? range
6.  
7. 1010_1100 desired
8.  

desired != value, но значащие биты в desired и value совпадают, а незначащие мы игнорируем, поэтому isMatches вернёт true

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

Диапазон - это два числа. Первое число (value) - значения бит в каждой позиции, второе - маска, показывающая значащие биты в value: те биты, значения которых должны в точности совпадать со значениями битов в тех же позициях в проверяемом числе.
Пример:

Код (Text):

1.  
2. 0110_1100 value
3. 0111_1101 mask
4. ===========
5. ?110_11?0 range
6.  
7. ? - бит в числе, проверяемом на соответствие, может быть любым
8.  

Т.е.:
?110_11?0 - диапазон (красные биты должны совпадать, чёрные могут быть любыми)
0110_1110 - входит в диапазон, т.к. значащие биты совпадают
1110_1100 - тоже входит, т.к. значащие биты совпадают
0100_1100 - не входит, т.к. один из значащих бит (синий) не совпадает

Надо придумать способ без перебора и проверки всех возможных значений проверить, входит ли хотя бы одно число из интервала [begin, end] в диапазон range.

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

Хм, почему от количества именно единиц?

 

В последнем примере, что я дал, сложность O(log2(2^N)), где N - количество нулей в маске. 64 сравнения в худшем случае для uint64_t.

Вообще без переборов вряд ли возможно сделать.

 

В любом случае, это уже зависимость не от количества элементов во входном интервале, и потому хорошо) Вечером проверю

 

HoShiMin,
Добавь еще в начало intersects, что если mask == 0, то сразу return true.

 

так зачем тебе value нужен, можно же без него обойтись - тогда будешь иметь дело сугубо с маской и подмаску легче вычислять. к примеру, mask1 = [1001], mask2 = [1101] >> mask2 is subMask of mask1. вот по субмаскам и щимишь пересечения.

 

Не понял идею... А приведи пример?

 

ну, вот у тебя mask1 = [1001] & mask2 = [1101].. desired1 = [1111]
mask1 ^ desired1 = [0110], mask2 ^ desired1 = [0010] и устанавливаешь допустимое расстояние меж значениями. короче, всё упирается в выбор схемы маски.

 

Там в цикле надо minValue и maxValue местами поменять или условие изменить на result > 0:

Код (C):

1.  
2.        if (result < 0)
3.             minValue = value;
4.        else
5.             maxValue = value;
6.  

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

UbIvItS,
Ниче не понятно
У него value & mask задает разреженное множество (не диапазон) значений. Например, если mask == 0x00000001, то при value равном 0, это множество всех четных 32-битных чисел, а при value равном 1 - множество всех нечетных.
Надо проверить принадлежность любого из этих значений диапазону begin..end.