Блог

Главная - Вопросы по программированию - Как я должен сериализовать дерево, содержащее очередь строк в каждом узле

Как я должен сериализовать дерево, содержащее очередь строк в каждом узле

#c #serialization #memory-management #deserialization #trie

#c #сериализация #управление памятью #десериализация #trie

Вопрос:

Я построил клавиатуру t9 на c , используя 8-полосный trie, где каждый узел выглядит следующим образом :-

 const int R=8;
    
class node
    {
        queue<string> words;
        node* keys[R];
        public:
        node()
        {
            for(int i=0;i<R;keys[i  ]=NULL);
        }
        queue<string> getWords() { return words; }
        void addWord(string w) { words.push(w); }
        void addKeys(node* k,int p) { keys[p]=k; }
        node* getKey(int p) { return keys[p]; }
    }*root=NULL;

Очередь используется для хранения таких слов, как «туман» и «собака», потому что оба они имеют одинаковый ввод с клавиатуры «1-4-2».

Прямо сейчас я использую словарь, содержащий всего около 60 000 слов, поэтому мне сходит с рук инициализация trie при каждом запуске программы. Но время загрузки и использование памяти значительно увеличатся, если будет больше слов. Итак, я столкнулся с методами сериализации и десериализации. Но я понятия не имею, как мне это сделать с очередью строк, присутствующих в каждом узле.

Также приветствуются любые другие предложения по изменению структуры данных. Спасибо.

Комментарии:

1. Но время загрузки и использование памяти значительно увеличатся, если будет больше слов. — В наш век компьютеров, процессоров, памяти и скорости 60 000 слов — это сбой. Итак, сколько слов вы ожидаете?

2. @PaulMcKenzie Около миллиона.

3. Вы действительно измеряли чтение миллиона слов или просто предполагали, что это будет медленно? Когда вы говорите «массовое увеличение», какие конкретные временные тесты вы провели, чтобы увидеть, является ли увеличение значительным? Кроме того, миллион слов, учитывая современные компьютеры, гораздо более управляемы с точки зрения памяти, чем 20 или 30 лет назад. Мы не вернулись во времена MSDOS.

4. @PaulMcKenzie Я не измерял чтение миллиона слов, но я уверен, что для создания trie на моем компьютере потребуется около 4 секунд, поскольку для вставки 60 000 (O (m * n) ) временной сложности для вставки в trie требуется 0,22 секунды. Это не мой огромный проект, поэтому я даже не знаю, подходит ли 4s или нет, и я хочу реализовать сериализацию практическим способом.

5. 4 секунды звучат для меня очень разумно для миллиона слов. Может быть, просто установите заставку «Загрузка данных …», если вам нужно какое-то визуальное приглашение пользователю относительно того, что происходит.