Информация об изменениях

Сообщение Re: Представление подмножеств от 06.06.2025 16:43

Изменено 06.06.2025 16:56 Chorkov

Старый текст
Новый текст
Разница

Re: Представление подмножеств

Здравствуйте, pva, Вы писали:

pva>Привет,

pva>поделитесь, пожалуйста, мыслями или идеями как можно эффективно представлять множества целых и некоторые операции над ними.
pva>Размер: на текущий момент можно ограничиться до 64-bit числами.
pva>Варианты элементов множеств: знаковое целое (8/16/32/64), беззнаковое целое (8/16/32/64), диаппазон целых с заданным шагом.
pva>Операции: +,-,*,/,&,|,^

pva>На текущий момент пытаюсь сделать это через std::optional<std::list<std::variant<*>>>>, но как-то громоздко получается, что ли.

А как еще будут запросы? (Кроме операций со множествами?)
(1) Проверка принадлежности числа множеству. (2) Число элементов множества. (3) число элементов, попадающих в диапазон. (4) перечислить все элементы. (5) проверить что множество не пусто ... ?

Если никакие запросу не предусмотрены, можно ничего не хранить.

Для диапазонов с шагом, каков период шага? (Порядка единиц / десятоко / ... / миллионов ?)

Каковы типичные размеры диапазонов? Бывают ли на всю числовую ось шириной?

Как много операций происходит прежде чем будет сделан запрос?

Как соотносятся частоты запросов (принадлежность элемента (?)) и частоты операций над множествами?
Часто ли диапазоны пересекаются?

Варианты:

1) Храним дерево операций, с помощью которых получено множество.

template<typename T>
struct points_set
{
     std::function< bool(T) > impl;
 //...
     points_set operator & ( const points_set& rhs) const // добавить && по вкусу
     {
    return points_set { [l=this->impl, r=rhs.impl] (T i)->bool { return l(i) && r(i); } };
     }
     
     bool contains(T i) const { return impl(i); }
};

Можно тоже самое на shared_ptr, для исключения копирования, или если нужно распечатать дерево, например.

Минус: никакой оптимизации, если при промежуточных вычислениях имеет место пустое множество. Не дружественно к памяти. Но не факт, что такая оптимизация нужна. Не дружественно к отладчику.

2) Храним множество, как набор точек и набор диапазонов

template<typename T>
struct points_set
{
   struct range{ T begin, end, step; };

   std::flat_set<T> points; // или unordered
   std::vector<range> ranges; // Можно сгруппировать по делителям / остаткам от деления если делители часто повторяются
};

Минусы: если операция "не" — очень дорогая, особенно если шаг большой. По диапазонам вынуждены ходить полным перебором. (Предполагается, что диапазонов много меньше чем точек.)

3) Хранить битовую маску для значимого под диапазона данных + границы диапазона + значение для всех запросов за пределами диапазона.

template<typename T>
struct points_set
{
   bool out_of_range_value=flase; // это поле нужно только для поддержки "не"
   T begin, end;
   std::vector<bool> subrange_points;

   bool contains(T i) const { return ((i>=begin) && (i<end)) ? subrange_points.at(i-begin) : out_of_range_value; }
};

4) точку рассмотрим как диапазон единичной длины. Пересекающиеся (по началу/концу) диапазоны, делим на либо с совпадающими концами, либо на не пересекающиеся.

template<typename T>
struct points_set
{
   std::flat_map< T, std::flat_map< T, std::flat_set<T> > data; // data[begin][divider] -> remainders set 

   bool contains(T key) const 
   { 
      auto i = data.upper_bound(key);
      if(i==data.begin()) return false;
      --i;
      assert( i->first <= key ); 
      assert( i+1 == data.end() || (i+1)->first > key ); 

      for( auto & [divider, remainders] : i->second )
      if( remainders.contains( key % divider ))
               return true;
      return false;
   }
};

Минусы: операции "^" и "/" — дорогие.

Re: Представление подмножеств

template<typename T>
struct points_set
{
   std::function< bool(T) > impl;
 //...
   points_set operator & ( const points_set& rhs) const // добавить && по вкусу
   {
      return points_set { [l=this->impl, r=rhs.impl] (T i)->bool { return l(i) && r(i); } };
   }
     
   bool contains(T i) const { return impl(i); }
};

Можно тоже самое на shared_ptr, для исключения копирования, или если нужно распечатать дерево, например.

Минусы: никакой оптимизации, если при промежуточных вычислениях, имеет место пустое множество. Не дружественно к памяти. Но не факт, что такая оптимизация нужна. Не дружественно к отладчику.

2) Храним множество, как набор точек и набор диапазонов

template<typename T>
struct points_set
{
   struct range{ T begin, end, step; };

   std::flat_set<T> points; // или unordered
   std::vector<range> ranges; // Можно сгруппировать по делителям / остаткам от деления если делители часто повторяются
};

template<typename T>
struct points_set
{
   bool out_of_range_value=flase; // это поле нужно только для поддержки "не"
   T begin, end;
   std::vector<bool> subrange_points;

   bool contains(T i) const { return ((i>=begin) && (i<end)) ? subrange_points.at(i-begin) : out_of_range_value; }
};

template<typename T>
struct points_set
{
   std::flat_map< T, std::flat_map< T, std::flat_set<T> > data; // data[begin][divider] -> remainders set 

   bool contains(T key) const 
   { 
      auto i = data.upper_bound(key);
      if(i==data.begin()) return false;
      --i;
      assert( i->first <= key ); 
      assert( i+1 == data.end() || (i+1)->first > key ); 

      for( auto & [divider, remainders] : i->second )
         if( remainders.contains( key % divider ))
            return true;
      return false;
   }
};

Минусы: операции "^" и "/" — дорогие.