Самый быстрый способ найти два несвязанных объекта в отношениях «многие ко многим» и их реализацию в C ++ - PullRequest
Новая
       18

Самый быстрый способ найти два несвязанных объекта в отношениях «многие ко многим» и их реализацию в C ++

3 голосов
/ 16 марта 2019

Основная настройка такова: предположим, у нас есть два простых класса: 

class User {
     private:
        int id;
     public:
        User(int id){ this->id = id };
};

class Channel {
     private:
        std::string name;
     public:
        Channel(std::string name) { this->name = name };
};

Предполагается, что эти два класса находятся во взаимоотношениях «многие ко многим», например каждый User может присоединиться ко многим Channel с, а каждый Channel может иметь много User с.

Количество Channel объектов - несколько сотен. Количество User объектов - десятки тысяч.

Формулировка задачи: Учитывая конкретный Channel объект, я должен найти User, который не связан с ним, как можно быстрее.

Вопрос:

1) Какова была бы оптимальная реализация такого отношения «многие ко многим», учитывая данную задачу? Существует ли какой-либо конкретный алгоритм для такой проблемы (кроме простой итерации по всем отношениям)?

2) Как это реализовать, если отношения должны иметь некоторые дополнительные свойства, например, сохранить время, когда User присоединился Channel?

Мои мысли: Первой идеей было создать дополнительный класс, такой как 

class UserChannelRel {
    private:
        User* userPtr;
        Channel* chPtr;
        float timeJoined;
    public:
        UserChannelRel(User* user, Channel* channel, float tm) {
             this->userPtr = user;
             this->chPtr = channel;
             this->timeJoined = tm;
        }
};

И хранить их в каком-то большом стандартном контейнере (вектор?) Но затем итерация по всем элементам кажется довольно медленной.

Ответы [ 2 ]

4 голосов
/ 16 марта 2019

Сначала вы можете создать два репозитория, которые будут содержать полный список пользователей с одной стороны и полный список каналов с другой.Как правило, вы делаете это с maps : 

map<int, User> users;
map<std::string, Channel> channels;

Тогда я бы предложил иметь для каждого канала набор пользователей: 

class Channel {
     private:
        std::string name;
        std::set<int> subscribers; 
     public:
        Channel(std::string name):name(name) { };
        void add(int userid) {
            subscribers.insert(userid);
        }
};

Затем, чтобы найти пользователей, не связанных с каналом, вы можете перебирать пользователей и легко проверять, включены ли они в канал.

Кроме того, вы также можете использовать глобальный набор пользователей (либо поддерживая членство в наборе в то же время, что и хранилище, либо создавая набор из карты ) и использовать set_difference() для генерации набора пользователей, которые не являются подписчиками.

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

set<int> a { 1,2,3,4,5,6,7};   // imagine a set of all the users
set<int> b{ 2,3,8};            // imagine a set of the subscribers of a channel
vector<int> c;                 // container with the users who are not subscribers

set_difference(a.begin(),a.end(), b.begin(), b.end(), back_inserter(c)); 
copy(c.begin(), c.end(), ostream_iterator<int>(cout," "));

Как выбрать между двумя подходами?Первый подход, повторяющийся и проверяющий, имеет то преимущество, что позволяет быстро найти первых пользователей и начать что-то делать с предложением.Итерацию можно оптимизировать, используя тот факт, что наборы и карты отсортированы.Вам не нужно найти всех пользователей.Второй подход элегантен, но с большой базой пользователей, это может занять больше времени, так как вам нужно получить полный результат, прежде чем что-либо делать.

0 голосов
/ 16 марта 2019

Может быть, вы могли бы попробовать использовать std::shared_ptr?

Каждый User будет иметь набор shared_ptr к Channels, к которому они присоединяются, что экономит память, поскольку к одному Channel могут присоединиться несколько пользователей.

Вы можете сделатьто же самое, чтобы сохранить Users в вашем Channels.

И затем вы можете иметь свой Users в vector и использовать сортировку (может быть эффективный, такой как слияние, попробуйте сравнить существующиесортировки, которые там есть), который смотрит, если User имеет указатель на Channel, на который вы смотрите.

...