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

Сообщение Re[5]: Представление подмножеств от 05.06.2025 11:55

Изменено 05.06.2025 11:58 rg45

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

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

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

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

R>>Ещё пара уточнений. Можно ли ввести какое-либо упорядочение элементов множества.
pva>Да, можно. Выше я немного приврал что тип делает элементы строго отличными друг от друга. Попробую объяснить ниже.
pva>Суть в том, что это a la дерево "symbolic calculation", в котором для узлов в процессе вычисления определяется множество вероятно принимаемых значений.
pva>Например, в какой-то момент решатель видит что результат op(a, b)->bool. Соответственно, допустимые значения {0,1}. not({0,1})={1,0}. Порядок следования важен.
pva>И так далее, двигаясь к корню мы в результате получаем некоторое множество (область) допустимых значений "функций" (МДЗ).
pva>При этом, технически есть еще ограничение размера типа (битовая маска — Mask).
pva>Грубо говоря, если у нас есть

MOV al,0a5h
pva>SHL ax,3

pva>То по итогу у нас Mask=11 бит, МДЗ={0x528} (технически это rax=0x528 & Mask). Теперь если сделать

AND ax,01a5h

pva>Результатом будет Mask=16 бит, MДЗ={0x120}. Неопределенность затронутой части не играет роли. Но если бы мы _вместо_ предыдущего сделали

AND ax,0a5a5h

pva>Результатом будет Mask=11 бит, а вот MДЗ={}, поскольку затронуты были _значимые_ неопределенные биты.
pva>В общем, это напоминает проблемы с неинициализированной памятью в сях, обращение к которой дает неопределенный результат.

R>>И допускается ли дублирование элементов. Например, можно ли добавить в множество диапазон [1-10], а потом еще отдельно, например, 3.
pva>Дублирование элементов не критично. Их можно отсеивать со временем.

pva>Пока писал сам осознал несколько дополнительных подводных камней. Вероятно, есть смысл посмотреть специализированные решатели типа z3 и интегрировать их.

Я тут набросал эскиз — просто для демонстрации идеи. Можно реализовать шаблон класса множества ориентированного на работу с отдельным целочисленным типом а потом сложить все такие множества в общую мапу с ключом std::type_index. Мапу инкапсулировать, конечно же. Для единообразия и упрощения простые числа можно хранить как интервалы. И это будет не хуже, чем вариант с variant (пардон за каламбур).

#include <any>
#include <concepts>
#include <iostream>
#include <map>
#include <set>
#include <typeindex>

template <std::integral T>
struct Interval   // Вместо этого можно заюзать boost::interval
{
   T lower{};
   T upper{};
};

template <std::integral T>
class Set
{
public:
   using Interval = Interval<T>;

   void insert(T t) {insert({t, t});}  // Простые числа тоже хранятся как интервалы
   void insert(const Interval&);    // Вот тут нужно будет реализовать слияние интервалов
   bool contains(T t) const {
      const auto it = m_set.lower_bound(t);
      return it != m_set.end() and it->lower <= t;
   }

private:
   struct Comparer { // Хитрый компаратор
      using is_transparent = void;
      bool operator()(const Interval& a, const Interval& b) const {return a.upper < b.upper;}
      bool operator()(const Interval& a, T t) const { return a.upper < t; }
      bool operator()(T t, const Interval& a) const { return t < a.upper; }
   };
   std::set<Interval, Comparer> m_set;
};

class SuperSet
{
public:

   bool insert(std::integral auto t) {get<decltype(t)>().insert(t);}
   template<std::integral T> bool contains(T t) const {return get<T>() and get<T>()->contains(t);}

private:
   template <std::integral T> Set<T>& get () {
      std::any& any = m_pool.try_emplace(typeid(T)).first->second;
      return any.has_value() ? std::any_cast<Set<T>&>(any) : any.emplace<Set<T>>();
   }
   template <std::integral T> const Set<T>* get() const;

   std::map<std::type_index, std::any> m_pool;
};

int main() {
   SuperSet s;
   s.contains(42);
}

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

MOV al,0a5h
pva>SHL ax,3

pva>То по итогу у нас Mask=11 бит, МДЗ={0x528} (технически это rax=0x528 & Mask). Теперь если сделать

AND ax,01a5h

AND ax,0a5a5h

#include <any>
#include <concepts>
#include <iostream>
#include <map>
#include <set>
#include <typeindex>

template <std::integral T>
struct Interval   // Вместо этого можно заюзать boost::interval
{
   T lower{};
   T upper{};
};

template <std::integral T>
class Set
{
public:
   using Interval = Interval<T>;

   void insert(T t) {insert({t, t});}  // Простые числа тоже хранятся как интервалы
   void insert(const Interval&);    // Вот тут нужно будет реализовать слияние интервалов
   bool contains(T t) const {
      const auto it = m_set.lower_bound(t);
      return it != m_set.end() and it->lower <= t;
   }

private:
   struct Comparer { // Хитрый компаратор
      using is_transparent = void;
      bool operator()(const Interval& a, const Interval& b) const {return a.upper < b.upper;}
      bool operator()(const Interval& a, T t) const { return a.upper < t; }
      bool operator()(T t, const Interval& a) const { return t < a.upper; }
   };
   std::set<Interval, Comparer> m_set;
};

class SuperSet
{
public:

   void insert(std::integral auto t) {get<decltype(t)>().insert(t);}
   template<std::integral T> bool contains(T t) const {return get<T>() and get<T>()->contains(t);}

private:
   template <std::integral T> Set<T>& get () {
      std::any& any = m_pool.try_emplace(typeid(T)).first->second;
      return any.has_value() ? std::any_cast<Set<T>&>(any) : any.emplace<Set<T>>();
   }
   template <std::integral T> const Set<T>* get() const;

   std::map<std::type_index, std::any> m_pool;
};

int main() {
   SuperSet s;
   s.contains(42);
}