Ок, новая головоломка всем адептам ооп, красивого кода и так же всем царями.
Дано: Класс который является адаптером для битовых масок больших размеров - 190 бит. Размер маски определён на этапе компиляции и не изменяется.
На данный момент класс является простой обёрткой над std::bitset (код приведён ниже)
Проблема заключается в данных которые там находятся.
Екземляры данного класса очень коротко живущие и их очень много. (каждые 10мс появляются и уничтожаются десятки тысяч). Количество использованной информации в большинствo из них довольно мало. Большая часть масок состоит из нулей и от одного до пяти активных битов. хотя переодически попадаются и по 30-40 битов. Очень редко могут появлятся почти все заженные биты.
Соотношение полезной информации к используемогу пространству очень и очень низкое.
Что требуется в задании: Поменять внутренюю структуру данных, так чтоб было использовано как можно меньше байт памяти.
Обязательные условия: 1. Нельзя пользоватся хипом 2. Должен остатся абсолютно тот же интерфейс класса. 3. Как можно более минимальный оверхед на обработку внутрених данных. 4. Нельзя использовать inline asm
Можно использовать любые техники -> от темплейтов до SIMD intrinsics.
Вроде ничего не забыл. Если появятся вопросы - я отвечу.
Ну и сам код класса;
#include <inttypes.h>
#include <assert.h>
#include <bitset>
#define CHANGESET_MAX_BITS 190
class ChangeSet
{
public:
inline ChangeSet()
{}
inline explicit ChangeSet(uint32_t uniqueChangeID)
{
//The current implementation of ChangeSet is limited to total 190 changes
assert(uniqueChangeID < CHANGESET_MAX_BITS);
m_changes.set(uniqueChangeID, 1);
}
inline ChangeSet(const ChangeSet & other): m_changes(other.m_changes)
{}
inline void clear()
{
m_changes.reset();
}
inline bool empty() const
{
return m_changes.none();
}
inline ChangeSet & operator |=(const ChangeSet & other)
{
m_changes |= other.m_changes;
return *this;
}
inline ChangeSet operator |(const ChangeSet & other) const
{
ChangeSet out(*this);
out |= other;
return out;
}
inline void addChanges(const ChangeSet & other)
{
m_changes |= other.m_changes;
}
inline void removeChanges(const ChangeSet & other)
{
m_changes &= ~other.m_changes;
}
inline ChangeSet & operator &=(const ChangeSet & other)
{
m_changes &= other.m_changes;
return *this;
}
inline ChangeSet operator &(const ChangeSet & other) const
{
ChangeSet out(*this);
out &= other;
return out;
}
inline ChangeSet & operator ^=(const ChangeSet & other)
{
m_changes ^= other.m_changes;
return *this;
}
inline ChangeSet operator ^(const ChangeSet & other) const
{
ChangeSet out(*this);
out ^= other;
return out;
}
inline ChangeSet operator ~() const
{
ChangeSet out;
out.m_changes = ~m_changes;
return out;
}
inline operator bool() const
{
return !m_changes.none();
}
inline bool containsAnyOf(const ChangeSet & other) const
{
return !(m_changes & other.m_changes).none();
}
inline bool operator ==(const ChangeSet & other) const
{
return m_changes == other.m_changes;
}
inline bool operator !=(const ChangeSet & other) const
{
return m_changes != other.m_changes;
}
static inline ChangeSet generateChangeSetWithAllChangesOn()
{
ChangeSet out;
out.m_changes.flip();
return out;
}
private:
std::bitset<CHANGESET_MAX_BITS> m_changes;
};
