什么样的数据结构适合facebook-model用户

Question

我想为这种情况构建一个有效的数据结构：
有很多用户，每个用户都有一个ID和一个名字。每个用户都可以关注其他人。我需要处理四种命令：创建用户、关注、删除用户和取消关注。这是一个例子：

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

您的输入数据看起来很适合像 std::unordered_map (https://en.cppreference.com/w/cpp/container/unordered_map)

这样的键值数据结构

其中 id 值可以作为存储和检索用户数据结构的键。

如果你能把数据处理成这样的结构 std::unordered_map 而不是列表这样您的 getUserById 函数就不需要每次都搜索列表来检索用户数据。

Answer 2

对于用户来说，我有一个映射类型的数据结构键和名称的值。

将有向图实现为

结构

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

创建用户：
在图中创建节点
关注用户：创建从该用户到其他用户
删除用户：使用图遍历技术找到用户并删除节点
取消 - 关注：从图中删除 link，因为它是有向图

希望对您有所帮助

什么样的数据结构适合facebook-model用户

What kind of data structure is suitable for facebook-model users

c++

algorithm

performance

performance-testing

data-structures