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

Тема в разделе "WASM.A&O", создана пользователем HoShiMin, 5 мар 2023.

Метки:
  1. HoShiMin

    HoShiMin Well-Known Member

    Публикаций:
    5
    Регистрация:
    17 дек 2016
    Сообщения:
    1.422
    Адрес:
    Россия, Нижний Новгород
    Мы задаём диапазон двумя битмапами: в первой значения битов, во второй - маска значащих битов первой битмапы.
    Если в маске бит равен 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.  
     
    Последнее редактирование: 5 мар 2023
  2. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.328
    Использовать begin..end как диапазон и проверять принадлежность ему всех валидных value.
    Например, при использовании указанной маски ?110_1??1, понадобится максимум 8 сравнений при любых begin..size.

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

    HoShiMin Well-Known Member

    Публикаций:
    5
    Регистрация:
    17 дек 2016
    Сообщения:
    1.422
    Адрес:
    Россия, Нижний Новгород
    Имеешь в виду, перебрать все возможные комбинации вместо знаков вопроса (3 знака в маске = 2^3 = 8)? Если да, то в случае 64х-битных масок перебрать все комбинации будет невозможно.
    --- Сообщение объединено, 5 мар 2023 ---
    Если правильно понял, в твоём алгоритме понадобится 2 * (sizeof(mask) * 8) сравнений? Но ведь это покроет не все возможные комбинации.
     
  4. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.328
    А все и не нужно, достаточно экстремальные.
    Если у нас маска 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.  
     
    Последнее редактирование: 5 мар 2023
  5. HoShiMin

    HoShiMin Well-Known Member

    Публикаций:
    5
    Регистрация:
    17 дек 2016
    Сообщения:
    1.422
    Адрес:
    Россия, Нижний Новгород
    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 подпадает под критерий.
     
  6. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.328
    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.  
     
    Последнее редактирование: 8 мар 2023
  7. HoShiMin

    HoShiMin Well-Known Member

    Публикаций:
    5
    Регистрация:
    17 дек 2016
    Сообщения:
    1.422
    Адрес:
    Россия, Нижний Новгород
    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.  
     
    Последнее редактирование: 8 мар 2023
  8. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.328
    HoShiMin,
    Я пофиксил там. Надо OR с инвертированной маской и AND с обычной.
     
  9. HoShiMin

    HoShiMin Well-Known Member

    Публикаций:
    5
    Регистрация:
    17 дек 2016
    Сообщения:
    1.422
    Адрес:
    Россия, Нижний Новгород
    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
     
  10. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.328
    Ну, по крайней мере, если функция вернет 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.  
     
  11. R81...

    R81... Active Member

    Публикаций:
    0
    Регистрация:
    1 фев 2020
    Сообщения:
    141
    Без "заворачивания" вроде не "константное", а двоичные логарифмы просятся, точнее от кол-ва единиц в величине qnt=size+1.
     
  12. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    1ым делом нужно чётко дать определение диапазону - это выглядит, ну, прям дико мутно..
    по идее, тру тут возможен, лишь если desired == value.
    --- Сообщение объединено, 9 мар 2023 ---
    обычно делают так
    • return (desired & mask) == mask;
     
  13. HoShiMin

    HoShiMin Well-Known Member

    Публикаций:
    5
    Регистрация:
    17 дек 2016
    Сообщения:
    1.422
    Адрес:
    Россия, Нижний Новгород
    Не только:
    Код (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 - входит в диапазон, т.к. значащие биты совпадают
    1
    110_1100 - тоже входит, т.к. значащие биты совпадают
    0
    100_1100 - не входит, т.к. один из значащих бит (синий) не совпадает

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

    --- Сообщение объединено, 9 мар 2023 ---
    Хм, почему от количества именно единиц?
     
    Последнее редактирование: 9 мар 2023
  14. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.328
    В последнем примере, что я дал, сложность O(log2(2^N)), где N - количество нулей в маске. 64 сравнения в худшем случае для uint64_t.

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

    HoShiMin Well-Known Member

    Публикаций:
    5
    Регистрация:
    17 дек 2016
    Сообщения:
    1.422
    Адрес:
    Россия, Нижний Новгород
    В любом случае, это уже зависимость не от количества элементов во входном интервале, и потому хорошо) Вечером проверю
     
  16. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.328
    HoShiMin,
    Добавь еще в начало intersects, что если mask == 0, то сразу return true.
     
  17. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    так зачем тебе value нужен, можно же без него обойтись - тогда будешь иметь дело сугубо с маской и подмаску легче вычислять. к примеру, mask1 = [1001], mask2 = [1101] >> mask2 is subMask of mask1. вот по субмаскам и щимишь пересечения.
     
  18. HoShiMin

    HoShiMin Well-Known Member

    Публикаций:
    5
    Регистрация:
    17 дек 2016
    Сообщения:
    1.422
    Адрес:
    Россия, Нижний Новгород
    Не понял идею... А приведи пример?
     
  19. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    ну, вот у тебя mask1 = [1001] & mask2 = [1101].. desired1 = [1111]
    mask1 ^ desired1 = [0110], mask2 ^ desired1 = [0010] и устанавливаешь допустимое расстояние меж значениями. короче, всё упирается в выбор схемы маски.
     
  20. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.328
    Там в цикле надо 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.