Какая структура данных подходит для пользователей Facebook-модели

Question

Я хочу построить эффективную структуру данных для такого случая:
Есть много пользователей, у каждого пользователя есть идентификатор и имя.Каждый пользователь может следовать за другими.Мне нужно обработать четыре вида команд: create-user, follow, delete-user и cancel-follow.Вот пример:

create-user id=3 name="Chandler"
create-user id=7 name="Janice"
create-user id=2 name="Joey"
follow id=3 id=7     # Chandler follows Janice
follow id=7 id=3     # Janice follows Chandler
follow id=2 id=7
follow id=7 id=2
delete-user id=7
follow id=3 id=2
follow id=2 id=3
cancel-follow id=3 id=2

Одним словом, мне нужно прочитать файл, содержащий множество команд, как указано выше, и обработать все данные.

Вот что япопробовал (функции для обработки четырех видов команд):

struct User
{
    unsigned long id;
    string name;
    unordered_set<User *> followers;
    unordered_set<User *> fans;

    User(unsigned long pid, const string & pname) : id(pid), name(pname) {}
};

list<User> users;

User & getUserById(list<User> & users, unsigned long id)
{
    auto it = std::find_if(users.begin(), users.end(), [&](User & u) {return id == u.id;});
    return *it;
}

void createUser(list<User> & users, unsigned long id, const string & str)
{
    users.emplace_back(User(id, str));
}

void deleteUser(list<User> & users, unsigned long id)
{
    auto itUser = std::find_if(users.begin(), users.end(), [&](User & u) {return id == u.id;});
    auto itFans = itUser->fans;
    for (auto it = itFans.begin(); it != itFans.end(); ++it)
    {
        (*it)->followers.erase(&*itUser);
    }
    auto itFollowers = itUser->followers;
    for (auto it = itFollowers.begin(); it != itFollowers.end(); ++it)
    {
        (*it)->fans.erase(&*itUser);
    }
    users.erase(itUser);
}

void buildRelation(list<User> & users, unsigned long follower, unsigned long fan)
{
    User & u1 = getUserById(users, follower);  //3
    User & u2 = getUserById(users, fan);  //7
    u1.fans.insert(&u2);
    u2.followers.insert(&u1);
}

void cancelRelation(list<User> & users, unsigned long follower, unsigned long fan)
{
    User & u1 = getUserById(users, follower);       //3
    User & u2 = getUserById(users, fan);  //2
    u1.fans.erase(&u2);
    u2.followers.erase(&u1);
}

Работает без ошибок.

Однако я использовал свой код для обработки файла, содержащего команды 70000 строк,это заняло около 67 секунд.

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

Answer 1

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

Реализация ориентированного графа в виде структуры как

Graph{ intV;LinkedList<Map<Long,String>>adjList[]; }

1. Создать пользователя:
   Создать узел на графике

2. Подписаться на пользователя: создать направленную ссылку от этого пользователя к другому пользователю

3. удалить пользователя: Используя технику обхода графа, найдите пользователя и удалите узел

4. Отмена - Следуйте: Удалить ссылку с графика, как он направлен граф

Надеюсь этопомогает

Answer 2

Ваши входные данные выглядят хорошо подходящими для ключевой структуры данных значения, такой как std :: unordered_map (https://en.cppreference.com/w/cpp/container/unordered_map)

Где значение id может выступать в качестве ключа для хранения и извлечения структуры данных пользователя.

Если бы вы могли обрабатывать данные в структуре, такой как std :: unordered_map вместо списка, тогда вашей функции getUserById не нужно будет каждый раз искать список для получения пользовательских данных.