Решил заменить медленный поиск под двухмерному массиву на Trie. В результате объем используемой памяти вырос с 7,6Мб до 43!
Как элемент массива я использую:
template<class TrieListEl>
class TrieListElProto/* : public OMatrixT<TrieListEl>*/{
public:
TrieListEl *_a, *_e; // up, end
TrieListEl *_p, *_n; // prev, next
TrieListEl *_l, *_r; // left, right
unsigned char key, use;
//MString val;
TrieListElProto(){
_a = 0; _e = 0;
_p = 0; _n = 0;
_l = 0; _r = 0;
key = 0;
use = 0;
}
//void SetItem(TrieListEl &t){}
};
Плюс переменная для хранения значения.
_a, _e - указатели на следующий уровень массива. _p, _n - указывают на следующий элемент на этом уровне. _l, _r - указывают на следующий уровень имени ключа. key - символ ключа. use - указывает на конечный символ в имени ключа.
Я решил, что хочу Trie, прикинул как оно должно быть и сделал. Результат меня совсем не устраивает. Есть другие реализации, позволяющие использовать меньше памяти? Какие есть варианты по оптимизации моего решения?.
MString
12 байт. Естественно не учтено выделение динамической памяти самим классомMString
. В текущем видеTrieListElProto
вносит максимум 64 байта дополнительных расходов. Сложно придумать намного более компактный вариант. В классическом варианте при использовании контейнераstd::map<char, TrieListElProto*>
накладные расходы 48 байт на каждый узел, без учета требуемого блока памяти под данные для std::map.