在学习C++时,一位大佬给我出了个题,如何实现积分排行榜,我通过查资料问AI,写了下面的处理方式\
首先,当积分排行榜很明显就是对大量数据进行排序,会对指定结点有大量的删除,修改,增加操作
我首先想的是肯定不能用vector这类的数据结构,vector,对于数据的增加,删除和修改vector的添加时间复杂度O(n),删除O(n),修改,O(n),查前top500 O(1)所以时间复杂度太高了,不合适
set和map,这两个数据结构底层是红黑树实现的,每次添加时需要保证红黑树规则,进行左旋右旋,修改颜色操作,删除,修改都需要进行大量对结点的操作,时间复杂度可想而知的O(logn),而且构建时很复杂
通过查找资料，Redis 有序集合 (ZSet) 底层就是跳表，是全球互联网公司排行榜的标准方案。
那到底是用红黑树写还是要通过跳表来写
跳表的结构如下
可以看到,当查找数据时,从头结点开始(最上层),想找到9,
第3层的头节点开始先找4,右边是NULL,往下跳,
跳到第2层的4结点找10,大了,从4结点开始再往下跳,
跳到第1层的4结点,往右找到7,小了,小了就把指针放到7这个结点,再往右跳,10大了,在7这个结点往下跳,
跳到第0层的7结点,往右跳,找到9了.
这过程中4-->4-->4-->7-->7-->9走了6个结点
如果是红黑树呢
找9走过了4个结点,这是数据量小的情况,如果数据量超级大100000个用户,这个红黑树和跳表其实是差不多的.
再看插入,跳表在插入时,从第3层开始找,和查找一样找到第0层该插入的位置,然后插入,再抛硬币0.5概率,决定是否要往上建索引(在极端情况下,当每次插入时抛硬币,都不往上插,那效率就会降低到O(n)),效率为O(logn)
红黑树在插入时,要遵循左根右,根叶红,不红红,黑路同,需要左旋右旋,判断爷,叔,父结点颜色,改变颜色,等等复杂操作,效率为O(logn)
修改数据时,跳表修改结点不需要动太多结点
而红黑树需要判断红黑树是否满足,再次判断左根右,根叶红,不红红,黑路同
获取数据时,跳表的效率是O(m),从第0层从左到右获取你想要的前m个用户积分数据即可
红黑树则是O(logn)
下面是对整个排行榜的构建过程
在构建过程中,我觉得难点在于删除操作,删除时,要记录前驱结点,从上到下删除,改指针,找前驱
#include<iostream> #include<vector> using namespace std; struct Node { string username; int score; Node* down; Node* right; Node(string username, int score) :username(username), score(score), down(nullptr), right(nullptr){} }; class SkipList { public: int MAX_LEVEL; vector<Node*>head;//存头结点(最左边那列) vector<Node*>path;//存走过的结点 SkipList(int maxlevel) { MAX_LEVEL = maxlevel; path.resize(maxlevel, nullptr);//对走过的结点初始化 for (int i = 0; i <= maxlevel - 1; ++i) {//最左边的头结点 head.push_back(new Node("", -65535)); } for (int i = maxlevel-1; i > 0; --i) { head[i]->down = head[i - 1]; } } void insertNode(string name,int score) { //从最顶层开始存放前驱结点 Node* cur = head[MAX_LEVEL - 1]; int level = MAX_LEVEL-1; while (cur != nullptr) { if (cur->right == nullptr || cur->right->score < score) { path[level] = cur;//将最左侧的头节点都记录到了path中 cur = cur->down; level--; } else { cur = cur->right; } } //从最底层开始插入 Node* node = new Node(name, score); node->right = path[0]->right;//path[0]右边相当于连了个nullptr,先把nullptr给到node->right path[0]->right = node;//然后连到一起 int nowlevel = 0;//从0层开始插入,50%的概率插入 while (rand() % 2 == 0 && nowlevel < MAX_LEVEL - 1) { nowlevel++; Node* upNode = new Node(name, score); upNode->right = path[nowlevel]->right; path[nowlevel]->right = upNode; upNode->down = node;//连下面 //更新现在node的位置 node = upNode; } } Node* SearchUser(int score,string name) { //从头节点开始找 Node* nodeHead = head[MAX_LEVEL - 1]; while (nodeHead != nullptr) { while (nodeHead->right != nullptr && nodeHead->right->score < score) {//只要满足右边比左边大,且右边不是空的,就一直往右边走 nodeHead = nodeHead->right; } if (nodeHead->right != nullptr) {//右边不为空,但是分数小于或者等于了要找的分数 if (nodeHead->right->score == score && nodeHead->right->username == name) { return nodeHead; } } else { nodeHead = nodeHead->down; } } //找完了都没找到 return nullptr; } void DeleteNode(int score,string name) { //先找,找到之后再从前驱里面找,删结点,然后改指针 Node* headNode = head[MAX_LEVEL - 1]; int level = MAX_LEVEL-1; while (headNode != nullptr) { if (headNode->right == nullptr || headNode->right->score < score) { path[level] = headNode; headNode = headNode->down; level--; } else if (headNode->right->score == score && headNode->right->username == name) { path[level] = headNode;//前驱结点,记录 headNode = headNode->down;//准备去删下面的 level--; } else {//右边分数大于查找的分数,继续往右找 headNode = headNode->right; } } if (headNode == nullptr) { cout << "Can't Find the User" << endl; } else { Node* delNode;//要删除的结点 for (int i = 0; i < MAX_LEVEL; i++) {//从最底层开始删 if (path[i] != nullptr && path[i]->right != nullptr && path[i]->right->score == score && path[i]->right->username == name) { delNode = path[i]->right;//前驱结点不是空的,前驱结点的右边也不是,当前结点的分数和名字都一样,确定是要删的结点 path[i]->right = delNode->right;//前驱结点连接到要删结点的右边,把要删除的结点的链条断掉 delete delNode;//删掉 } path[i] = nullptr;//把每一层的前驱删掉,下次再使 } } } void updateNode(int score,string name,int newScore) { //更新就是先查找,先删,改分数,再插入 Node* cur = SearchUser(score, name); if (cur != nullptr) { DeleteNode(score, name); insertNode(name,newScore); } else { cout << "Can't Find the User" << endl; } } void printLevel() { for (int i = MAX_LEVEL - 1; i >= 0; i--) { cout << "第" << i << "层"; Node* cur = head[i]->right; while (cur != nullptr) { cout << cur->username << "(" << cur->score << ")" << "--->"; cur = cur->right; } cout << "nullptr"; cout << endl; } } void printTop(int num) { //打印前num名用户 Node*HeadNode=head[0]->right; cout << "榜" << num << "为:"<<endl; for (int i = 0; i < num; i++) { if (HeadNode != nullptr) { cout << HeadNode->username << "(" << HeadNode->score << ")" << endl; HeadNode = HeadNode->right; } else { cout << "暂无用户" << endl; } } } }; int main() { SkipList sl(4);//最大4层,跳表 sl.insertNode("张三", 2314); sl.insertNode("李四", 3215); sl.insertNode("王五", 234612); sl.insertNode("赵六", 1246123); sl.insertNode("刘七", 65431); sl.insertNode("王八", 2152); sl.insertNode("谭九", 1235); sl.insertNode("白小白", 20452); sl.printLevel(); cout << "=================" << endl; sl.printTop(10); return 0; }在工程项目中,一定是多线程对于数据结构进行操作,上面的结构适用于单线程使用,多线程使用必然崩溃,同时有多个线程操作插入查找删除,尤其是更新,还没删除就插入了,还没查找就删除了,很容易混乱全部操作都在共享内存中,可以在跳表结构中加一个互斥锁,mutex,每段增删改查都加上锁,这样的改造成本明显降低
但如果想要使用无锁跳表,原子级别操作,我建议还是使用redis中的zset合适,现成的
如果有大佬有改进意见欢迎评论,谢谢
