Структура данных для многоуровневого обхода - PullRequest
Новая
       17

Структура данных для многоуровневого обхода

3 голосов
/ 02 августа 2011

У меня есть приложение, которое работает с данными в следующей структуре: 

struct Message
{
   int    time;
   string name;
   string details;
};

Например, у меня может быть набор данных, который выглядит следующим образом: 

9:00:00 Bob  <Info>
9:01:00 John <Info>
9:05:00 Bob  <Info>
9:11:00 Mary <Info>
9:17:00 John <Info>
9:25:00 Mary <Info>
9:30:00 Bob  <Info>

И у меня будет список Message структур, которые представляют каждую строку в наборе данных.

Некоторые операции, которые мне нужно будет выполнить с этими данными, включают:

  • Соберите все данные в хронологическом порядке и dostuff()
  • Соберите все данные от John (или от кого угодно) в хронологическом порядке и dostuff()

Итак, мне нужен способ пройти список, чтобы я мог передать каждое сообщение в хронологическом порядке, а также выбрать человека и пропустить только его сообщения в хронологическом порядке.

Мои мысли должны иметь такую ​​структуру: 

struct Node
{
   Message* message;
   Node*    next_time;
   Node*    next_name;
};

, в котором next_time указывает на следующее Node в хронологическом порядке, а next_name указывает на следующее Node, которое принадлежит message->name. И структура Root указывает на первый из каждого типа. 

struct Root 
{
   Node* first_time;
   Node* first_bob;
   Node* first_john;
   Node* first_mary;

   Node* last_time;
   Node* last_bob;
   Node* last_john;
   Node* last_mary;
};

Вот изображение, иллюстрирующее точку.

enter image description here

Эта структура позволяет мне довольно легко проходить через каждое сообщение, или только через сообщения Боба, или только через Джона и т. Д.

Однако меня беспокоит, что, может быть, это сложнее, чем нужно. У меня также есть проблемы по обслуживанию (см. Ниже). Мне нужно, чтобы операции поиска / выбора / чтения были довольно быстрыми, что я и считаю. И мне нужно, чтобы операции вставки были достаточно быстрыми. Но сейчас, для каждой вставки Message, я должен (1) обновить некоторый указатель next_time и (2) обновить указатель next_name.

Мой вопрос: Существует ли структура данных, которая уже обеспечивает такую ​​функциональность? Если нет, правильно ли я подхожу к этой проблеме?

Пожалуйста, предоставьте любые примеры кода на C ++ или C #, если это возможно.

Спасибо.

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

  • Соберите все данные из определенного City в хронологическом порядке и dostuff()

Для этого потребуется добавить next_city, а затем для каждой вставки мне придется обновить next_time, next_name, И next_city.

Далее, предположим, я хочу сделать это:

  • Соберите все данные из определенного City И определенного name в хронологическом порядке и dostuff()

Я думаю, что это невероятно усложнит проблему, если я не решу пройти через все Message и пропустить те, которые мне не нужны.

Ответы [ 2 ]

1 голос
/ 02 августа 2011

Простой связанный список всех сообщений (отсортированный по времени).

struct Node
{
   Message* message;
   Node*    next_name;
};

Это будет соответствовать требованию 1. Вы можете добавить () и getAll () в O (1)

Отдельный хэш-файл с пользователем в качестве ключа и списком узла * в качестве значений. 

Hashmap
{key = User, value = List(Message*)}

Это удовлетворяет требованию 2. Вы можете добавить новую запись в конец списка определенного пользователя O (1), а getAllOfUser () также может запускаться в O (1) * 1009.*

1 голос
/ 02 августа 2011

Я бы, вероятно, создал класс для представления пользователя, сохраняя пользователей в хеш-таблице по некоторому идентификатору, например по имени, и затем каждый пользователь содержал список Message, отсортированный в хронологическом порядке, которые также хранятся в единый глобальный список, который содержит все Message в хронологическом порядке. Для каждого добавленного Message вам нужно будет вставить его один раз в каждый список (под списком я имею в виду некоторую коллекцию), что может быть log n раз или плохо n, в зависимости от структуры данных.

...