Лучшая структура данных для хранения групповых отношений и поддержки - PullRequest
Новая
       10

Лучшая структура данных для хранения групповых отношений и поддержки

1 голос
/ 02 ноября 2019

Мне нужно создать структуру данных, чтобы отслеживать некоторую информацию о группировке. Предполагая, что элементы просто строки. Например, {'a', 'b', 'c'} является группой, а {'e', 'f', 'g'} - другой группой. Мне также нужно поддерживать поиск по ключам и ключи все строки. Сейчас я могу подумать об использовании карты: 

{a} -> {"a", "b", "c"}
{b} -> {"a", "b", "c"}

{e} -> {"e", "f", "g"}
{f} -> {"e", "f", "g"}

Но в этом случае я дублирую много информации на карте, и размер взорвется. Любая другая хорошая структура данных, которая компактна и также поддерживает быстрый поиск?

Ответы [ 2 ]

1 голос
/ 04 ноября 2019

Но в этом случае я дублирую много информации на карте, и размер взорвется. Любая другая хорошая структура данных, которая компактна и также поддерживает быстрый поиск?

Вместо того, чтобы отображать элементы непосредственно в группы, вы можете ввести дополнительный уровень косвенности, чтобы покончить с этим дублированием, отображая элементы, которые std::string с, идентификаторы группы , которые являются индексами. Затем вы можете сохранить std::vector групп. Вы используете идентификаторы групп, полученные сопоставлением, чтобы индексировать этот вектор групп.

В качестве примера реализации этой идеи: 

#include <unordered_map>
#include <unordered_set>
#include <string>
#include <vector>

class GroupRelation {
   std::unordered_map<std::string, group_id_t> elem2group_id_;
   std::vector<std::unordered_set<std::string>> groups_;
public:
   using group_id_t = size_t;

   auto num_groups() const { groups_.size(); }

   auto add_group(std::unordered_set<std::string> group) {
      auto grp_id = groups_.size();
      for (auto const& elem: group)
         elem2group_id_[elem] = grp_id;

      groups_.push_back(std::move(group));
      return grp_id; // return group_id_t of just added group
   }

   // for checking whether or not an element is in a group
   bool is_in_group(const std::string& elem) const {
      auto it = elem2group_id_.find(elem); 
      return elem2group_id_.end() != it;
   }

   // returns the group ID where the element belongs
   group_id_t group_id(const std::string& elem) const {
      auto it = elem2group_id_.find(elem); 
      return it->second;
   }

   const std::unordered_set<std::string>& group(group_id_t group_id) const {
      return groups_[group_id];
   }

   std::unordered_set<std::string>& group(group_id_t group_id) {
      return groups_[group_id];
   }
};

Извлечение идентификатора группы из элемента может быть выполнено в среднем за постоянное время.

Пример использования: 

auto main() -> int {
   GroupRelation grp_rel;

   grp_rel.add_group({"a", "b", "c"});   
   grp_rel.add_group({"e", "f", "g"});

   for (auto const& elem: grp_rel.group(0))
      std::cout << elem << ' ';
   std::cout << '\n';

   for (auto const& elem: grp_rel.group(1))
      std::cout << elem << ' ';
   std::cout << '\n';

}

Мой вывод: 

b c a 
g f e
0 голосов
/ 04 ноября 2019

У вас уже есть одна быстрая структура данных, которую вы должны использовать с умом.
, если вы хотите, чтобы два ключа make из 3 разных строк (s1, s2, s3) делали это

Добавлениеключ, значение на карте
создайте новую строку s1+"_"+s2+"_"+s3
используйте это как ключ

При получении значения с карты
создайте новую строку s1+"_"+s2+"_"+s3
используйте это как ключ

UnderScore здесь выполняет всю работу.

Это тоже достаточно быстро.

...