2

Решил заменить медленный поиск под двухмерному массиву на 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, прикинул как оно должно быть и сделал. Результат меня совсем не устраивает. Есть другие реализации, позволяющие использовать меньше памяти? Какие есть варианты по оптимизации моего решения?.

6
  • Вы бы озвучили что есть поиск по двумерному массиву? Структуру данных следует выбирать исходя из задач которые планируется решать. Если выбран двумерный массив - то в первую очередь нужен быстрый доступ к элементу по двум индексам.
    – sba
    12 ноя 2015 в 9:06
  • Имелся в виду динамический массив для разбора JSON. Да, я не уверен, что выбрал правильную структуру данных, но вопрос не в этом.
    – mikelsv
    12 ноя 2015 в 9:21
  • Начните с четкого описания решаемой задачи и с выбора правильной структуры данных. JSON это структура с множественной вложенностью. Вы делаете поиск ключа в JSON при неизвестном уровне вложености?
    – sba
    12 ноя 2015 в 9:38
  • Задача описана - оптимизировать Trie. В JSON поиск идет в основном по первым двум уровням вложенности, по остальным тоже ищет, но гораздо реже.
    – mikelsv
    12 ноя 2015 в 10:00
  • Битый час пытаюсь понять как работает Ваш поиск. Из предоставленной информации выплывает, что у Вас более 650K элементов (при размере указателя 8 байт). При том размер MString 12 байт. Естественно не учтено выделение динамической памяти самим классом MString. В текущем виде TrieListElProto вносит максимум 64 байта дополнительных расходов. Сложно придумать намного более компактный вариант. В классическом варианте при использовании контейнера std::map<char, TrieListElProto*> накладные расходы 48 байт на каждый узел, без учета требуемого блока памяти под данные для std::map.
    – sba
    12 ноя 2015 в 13:10

1 ответ 1

2

Оптимизировал, использовав два байта валяющихся без дела: unsigned int key : 24, use : 8; Ключ стал длинной в три байта и занимаемый объем данных уменьшился в 2,45 раза, до 17,5 мегабайт. Это уже приемлимые цифры.

Полагаю в алгоритме Trie основным моментом является длинна ключа, влияющая на занимаемую память и скорость поиска.

Также полагаю, что можно оптимизировать расход памяти за счет использования нескольких типов ячеек, но это тема для исследования.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.