dw博客网站怎么做百度网盘搜索引擎入口官网
生成文件和从文件中读取数据。
需求如下：
你的任务是实现 SkipList 类中的数据持久化成员函数和数据加载成员函数。
持久化数据成员函数签名：void dump_file();
该成员函数负责将存储引擎内的数据持久化到文件中。数据的持久化格式是将每个键值对写入文件的单独一行，采用key:value的格式。这种方式不仅确保了数据格式的一致性，还便于数据的恢复和解析。
读取数据成员函数签名：void load_file();
此成员函数的目的是从文件中读取之前持久化的数据，并将其加载到存储引擎中。读取的数据格式遵循每行一个key:value键值对的规则。在数据加载过程中，成员函数还需确保跳表的索引能够被正确地重建，以保持数据的快速访问和检索性能。
其实看起来蛮简单的，就是把原本数据按照一定格式读入到文件中，和从文件中读取数据再调用insert_element函数就行了。但实现起来还是遇到了几个坑的。
首先是文件读写，这个网上版本很多，随意选择一种就行。
包含如下头文件：
#include <fstream>
#include <iostream>在要编写的dump_file函数里写明绝对路径，然后修改下print拿过来用就行了。代码如下：
void dump_file() {std::ofstream out("D:\\dev_c++\\destination\\out.txt");if (out.is_open()) {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode->forwards[curlevel];while (cur) {out << cur->getKey() << ":" << cur->get_value() << '\n';cur = cur->forwards[curlevel];}curlevel--;}out.close();}}这个在在线判题系统里似乎修改不了，需要用本地C++编译器。然后还会在time(0)出报错，需要加上如下头文件：
#include <sys/time.h>
实现效果如图，还用的删除跳表那里的输入输出数据
再来看读入数据：
这个首先要判断是否打开了文件，没打开直接报错，在线判题网上里就是直接报错的。所以我们还是要用编译器。之后就是对输入字符串进行处理，循环遍历找到':'下标作为分隔符下标，以此为依据调用substr函数即可。
代码如下：
void load_file() {std::ifstream in("D:\\dev_c++\\destination\\out.txt");char buffer[256];if (!in.is_open()) {std::cout << "open error";} else {while (!in.eof()) {std::string s;in >> s;int index = 0;if (s.size() == 0) return; for (int i = 0; i < s.length(); i++) {if (s[i] == ':') {index = i;break;}}
// std::cout << s << ' ';std::string s1 = s.substr(0, index);std::string s2 = s.substr(index + 1, s.length() - 1 - index); //下标从index+1开始std::cout << s1 << s2 << std::endl;
// int key = std::stoi(s1);int value = std::stoi(s2);insert_element(key, value);}}}这个实现的就只是int类型的读取文件。
运行效果如图：
由于我们采用的是随机层数的机制，所以每次结果层数会不一致，也很正常。这也是跳表好玩的地方之一了。
整体代码如下：
#include<stdlib.h>
#include <iostream>
#include <cstring>
#include <fstream>
#include <iostream>
#include <string>
#include <sys/time.h>template<typename K, typename V>
class Node {
private:K key;V val;int node_level;public:Node** forwards;public:Node(K inkey, V value, int level): key(inkey), val(value), node_level(level),forwards(nullptr) {this->forwards = new Node<K, V>*[node_level+1];memset(this->forwards, 0, sizeof(Node<K,V>*)*(node_level+1));}~Node(){delete forwards;};K getKey() const {return key;}V get_value() const {return val;}int getLevel() const {return node_level;}void set_value(V value) {val = value;}};template<typename K, typename V>
class SkipList {
private:Node<K,V>* HeadNode = nullptr;int _maxlevel = 0;int temp_level = 0;
public:SkipList(int maxlevel = 500) {_maxlevel = maxlevel;HeadNode = new Node<K, V>(K(),V(),maxlevel);}~SkipList() { delete HeadNode; _maxlevel = 0; temp_level = 0; }int getRandomLevel() {srand((int)time(0));int k = 1;while (rand() % 2) {k++;}k = (k < _maxlevel) ? k : _maxlevel;return k;}int insert_element(const K key, const V value) {int flag = 0;Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode;while (cur) {if (cur->getKey() == key) {flag = 1;cur->set_value(value);}cur = cur->forwards[curlevel]; }curlevel--;}if (flag == 1) return 1;Node<K, V>* newNode = new Node<K,V>(key, value, getRandomLevel());if (temp_level < newNode->getLevel()) temp_level = newNode->getLevel();curlevel = newNode->getLevel();while (curlevel) {Node<K,V>* prev = HeadNode;cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() > newNode->getKey()) {prev->forwards[curlevel] = newNode;newNode->forwards[curlevel] = cur;break;} cur = cur->forwards[curlevel];prev = prev->forwards[curlevel];} if (!cur)prev->forwards[curlevel] = newNode;curlevel--;}return 0;}bool search_element(K key) {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() == key) return true;cur = cur->forwards[curlevel]; }curlevel--;}return false;}void delete_element(K key) {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {Node<K,V>* prev = HeadNode;cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() == key) {prev->forwards[curlevel] = cur->forwards[curlevel];break;}cur = cur->forwards[curlevel];prev = prev->forwards[curlevel];}curlevel--;}}void print() {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode->forwards[curlevel];std::cout << "Level " << curlevel-1 << ": ";while (cur) {std::cout << cur->getKey() << ":" << cur->get_value() << ';';cur = cur->forwards[curlevel];}std::cout << std::endl;curlevel--;}}void dump_file() {std::ofstream out("D:\\dev_c++\\destination\\out.txt");if (out.is_open()) {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode->forwards[curlevel];while (cur) {out << cur->getKey() << ":" << cur->get_value() << '\n';cur = cur->forwards[curlevel];}curlevel--;}out.close();}}void load_file() {std::ifstream in("D:\\dev_c++\\destination\\out.txt");char buffer[256];if (!in.is_open()) {std::cout << "open error";} else {while (!in.eof()) {std::string s;in >> s;int index = 0;if (s.size() == 0) return; for (int i = 0; i < s.length(); i++) {if (s[i] == ':') {index = i;break;}}
// std::cout << s << ' ';std::string s1 = s.substr(0, index);std::string s2 = s.substr(index + 1, s.length() - 1 - index);
// std::cout << s1 << s2 << std::endl;int key = std::stoi(s1);int value = std::stoi(s2);insert_element(key, value);}}}
};int main() {SkipList<int, int> mySkipList;// 插入删除数据 int n,k,m;std::cin >> n >> k >> m;while (n--) {int key, v, r;std::cin >> key >> v;r = mySkipList.insert_element(key,v);if (r == 0) std::cout << "Insert Success" << std::endl;else std::cout << "Insert Failed" << std::endl;}while (k--) {int key;std::cin >> key;mySkipList.delete_element(key);}while (m--) {int k;std::cin >> k;if (mySkipList.search_element(k)) std::cout << "Search Success" << std::endl;else std::cout << "Search Failed" << std::endl;}mySkipList.dump_file();// 读文件并展示 mySkipList.load_file();mySkipList.print();
}模块合并
需求如下：
你的任务是创建一个 skiplist.h 的头文件，包含前面所有章节介绍的 Node 类和 SkipList 类，用以在其他程序中进行引用
其实主要也就是引入了锁，加上如下头文件：
#include <mutex> 并且在插入删除数据函数前后分别加锁和解锁就行了，伪代码如下：
// 只有在插入和删除的时候，才会进行加锁
template <typename K, typename V>
int SkipList<K, V>::insert_element(const K key, const V value) {mtx.lock(); // 在函数第一句加锁// ... 算法过程（省略）if (current != NULL && current->get_key() == key) {std::cout << "key: " << key << ", exists" << std::endl;// 在算法流程中有一个验证 key 是否存在的过程// 在此处需要提前 return，所以提前解锁mtx.unlock();return 1;}// ... mtx.unlock(); // 函数执行完毕后解锁return 0;
}template <typename K, typename V>
void SkipList<K, V>::delete_element(K key) {mtx.lock(); // 加锁// ... 算法过程（省略）mtx.unlock(); // 解锁return;
}最终代码如下：
#include<stdlib.h>
#include <iostream>
#include <cstring>
#include <fstream>
#include <iostream>
#include <string>
#include <mutex>
#include <sys/time.h>std::mutex mtx; template<typename K, typename V>
class Node {
private:K key;V val;int node_level;public:Node** forwards;public:Node(K inkey, V value, int level): key(inkey), val(value), node_level(level),forwards(nullptr) {this->forwards = new Node<K, V>*[node_level+1];memset(this->forwards, 0, sizeof(Node<K,V>*)*(node_level+1));}~Node(){delete forwards;};K getKey() const {return key;}V get_value() const {return val;}int getLevel() const {return node_level;}void set_value(V value) {val = value;}};template<typename K, typename V>
class SkipList {
private:Node<K,V>* HeadNode = nullptr;int _maxlevel = 0;int temp_level = 0;
public:SkipList(int maxlevel = 500) {_maxlevel = maxlevel;HeadNode = new Node<K, V>(K(),V(),maxlevel);}~SkipList() { delete HeadNode; _maxlevel = 0; temp_level = 0; }int getRandomLevel() {srand((int)time(0));int k = 1;while (rand() % 2) {k++;}k = (k < _maxlevel) ? k : _maxlevel;return k;}int insert_element(const K key, const V value) {mtx.lock();int flag = 0;Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode;while (cur) {if (cur->getKey() == key) {flag = 1;cur->set_value(value);}cur = cur->forwards[curlevel]; }curlevel--;}if (flag == 1) return 1;Node<K, V>* newNode = new Node<K,V>(key, value, getRandomLevel());if (temp_level < newNode->getLevel()) temp_level = newNode->getLevel();curlevel = newNode->getLevel();while (curlevel) {Node<K,V>* prev = HeadNode;cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() > newNode->getKey()) {prev->forwards[curlevel] = newNode;newNode->forwards[curlevel] = cur;break;} cur = cur->forwards[curlevel];prev = prev->forwards[curlevel];} if (!cur)prev->forwards[curlevel] = newNode;curlevel--;}mtx.unlock();return 0;}bool search_element(K key) {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() == key) return true;cur = cur->forwards[curlevel]; }curlevel--;}return false;}void delete_element(K key) {mtx.lock();Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {Node<K,V>* prev = HeadNode;cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() == key) {prev->forwards[curlevel] = cur->forwards[curlevel];break;}cur = cur->forwards[curlevel];prev = prev->forwards[curlevel];}curlevel--;}mtx.unlock();}void print() {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode->forwards[curlevel];std::cout << "Level " << curlevel-1 << ": ";while (cur) {std::cout << cur->getKey() << ":" << cur->get_value() << ';';cur = cur->forwards[curlevel];}std::cout << std::endl;curlevel--;}}void dump_file() {std::ofstream out("D:\\dev_c++\\destination\\out.txt");if (out.is_open()) {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode->forwards[curlevel];while (cur) {out << cur->getKey() << ":" << cur->get_value() << '\n';cur = cur->forwards[curlevel];}curlevel--;}out.close();}}void load_file() {std::ifstream in("D:\\dev_c++\\destination\\out.txt");char buffer[256];if (!in.is_open()) {std::cout << "open error";} else {while (!in.eof()) {std::string s;in >> s;int index = 0;if (s.size() == 0) return; for (int i = 0; i < s.length(); i++) {if (s[i] == ':') {index = i;break;}}
// std::cout << s << ' ';std::string s1 = s.substr(0, index);std::string s2 = s.substr(index + 1, s.length() - 1 - index);
// std::cout << s1 << s2 << std::endl;int key = std::stoi(s1);int value = std::stoi(s2);insert_element(key, value);}}}
};int main() {SkipList<int, int> mySkipList;// 插入删除数据 int n,k,m;std::cin >> n >> k >> m;while (n--) {int key, v, r;std::cin >> key >> v;r = mySkipList.insert_element(key,v);if (r == 0) std::cout << "Insert Success" << std::endl;else std::cout << "Insert Failed" << std::endl;}while (k--) {int key;std::cin >> key;mySkipList.delete_element(key);}while (m--) {int k;std::cin >> k;if (mySkipList.search_element(k)) std::cout << "Search Success" << std::endl;else std::cout << "Search Failed" << std::endl;}mySkipList.dump_file();// 读文件并展示 mySkipList.load_file();mySkipList.print();
}压力测试
测试结果如图
这一模块是要编写代码对所做项目进行测试，所用代码文件如下：
// 引入必要的头文件
#include <iostream> // 用于输入输出流
#include <chrono> // 用于高精度时间测量
#include <cstdlib> // 包含一些通用的工具函数，如随机数生成
#include <pthread.h> // 用于多线程编程
#include <time.h> // 用于时间处理函数
#include "./skiplist.h" // 引入自定义的跳表实现// 定义宏常量
#define NUM_THREADS 1 // 线程数量
#define TEST_COUNT 100000// 测试用的数据量大小
SkipList<int, std::string> skipList(18); // 创建一个最大层级为18的跳表实例// 插入元素的线程函数
void *insertElement(void* threadid) {long long tid; // 线程IDtid = (long long)threadid; // 将void*类型的线程ID转换为long型std::cout << tid << std::endl; // 输出线程IDint tmp = TEST_COUNT/NUM_THREADS; // 计算每个线程应该插入的元素数量// 循环插入元素for (int i=tid*tmp, count=0; count<tmp; i++) {count++;skipList.insert_element(rand() % TEST_COUNT, "a"); // 随机生成一个键，并插入带有"a"的元素}pthread_exit(NULL); // 退出线程
}// 检索元素的线程函数
void *getElement(void* threadid) {long long tid; // 线程IDtid = (long long)threadid; // 将void*类型的线程ID转换为long型std::cout << tid << std::endl; // 输出线程IDint tmp = TEST_COUNT/NUM_THREADS; // 计算每个线程应该检索的元素数量// 循环检索元素for (int i=tid*tmp, count=0; count<tmp; i++) {count++;skipList.search_element(rand() % TEST_COUNT); // 随机生成一个键，并尝试检索}pthread_exit(NULL); // 退出线程
}int main() {srand(time(NULL)); // 初始化随机数生成器{pthread_t threads[NUM_THREADS]; // 定义线程数组int rc; // 用于接收pthread_create的返回值int i; // 循环计数器auto start = std::chrono::high_resolution_clock::now(); // 开始计时// 创建插入元素的线程for( i = 0; i < NUM_THREADS; i++ ) {std::cout << "main() : creating thread, " << i << std::endl;rc = pthread_create(&threads[i], NULL, insertElement, (void *)i); // 创建线程if (rc) {std::cout << "Error:unable to create thread," << rc << std::endl;exit(-1); // 如果线程创建失败，退出程序}}void *ret; // 用于接收pthread_join的返回值// 等待所有插入线程完成for( i = 0; i < NUM_THREADS; i++ ) {if (pthread_join(threads[i], &ret) != 0 ) {perror("pthread_create() error");exit(3); // 如果线程等待失败，退出程序}}auto finish = std::chrono::high_resolution_clock::now(); // 结束计时std::chrono::duration<double> elapsed = finish - start; // 计算耗时std::cout << "insert elapsed:" << elapsed.count() << std::endl; // 输出插入操作耗时}// 下面的代码块与上面类似，用于创建并管理检索操作的线程{pthread_t threads[NUM_THREADS];int rc;int i;auto start = std::chrono::high_resolution_clock::now();for( i = 0; i < NUM_THREADS; i++ ) {std::cout << "main() : creating thread, " << i << std::endl;rc = pthread_create(&threads[i], NULL, getElement, (void *)i);if (rc) {std::cout << "Error:unable to create thread," << rc << std::endl;exit(-1);}}void *ret;for( i = 0; i < NUM_THREADS; i++ ) {if (pthread_join(threads[i], &ret) != 0 ) {perror("pthread_create() error");exit(3);}}auto finish = std::chrono::high_resolution_clock::now();std::chrono::duration<double> elapsed = finish - start;std::cout << "get elapsed:" << elapsed.count() << std::endl;}pthread_exit(NULL); // 主线程退出return 0;
}我们还需要新建一个项目工程文件，将之前写的代码重命名成skiplist.h，编译运行进行测试，编译链接要按照如下指令来：
g++ --std=c++11 main.cpp -o stress -pthreaddev_c++里面点进这里修改这个即可。
但在测试过程中，我发现即便是很少的数据量比如4，运行黑框仍旧会卡住，一直无法出来。自己检查代码后才发现，是我在插入数据函数加锁时只在return 0的情况下加了锁，因此在return 1 的情况下，系统就陷入了死锁局面！
加上去之后就好了。
修改后代码如下：
//skiplist.h
#include<stdlib.h>
#include <iostream>
#include <cstring>
#include <fstream>
#include <iostream>
#include <string>
#include <mutex>
#include <sys/time.h>std::mutex mtx; template<typename K, typename V>
class Node {
private:K key;V val;int node_level;public:Node** forwards;public:Node(K inkey, V value, int level): key(inkey), val(value), node_level(level),forwards(nullptr) {this->forwards = new Node<K, V>*[node_level+1];memset(this->forwards, 0, sizeof(Node<K,V>*)*(node_level+1));}~Node(){delete forwards;};K getKey() const {return key;}V get_value() const {return val;}int getLevel() const {return node_level;}void set_value(V value) {val = value;}};template<typename K, typename V>
class SkipList {
private:Node<K,V>* HeadNode = nullptr;int _maxlevel = 0;int temp_level = 0;
public:SkipList(int maxlevel = 500) {_maxlevel = maxlevel;HeadNode = new Node<K, V>(K(),V(),maxlevel);}~SkipList() { delete HeadNode; _maxlevel = 0; temp_level = 0; }int getRandomLevel() {srand((int)time(0));int k = 1;while (rand() % 2) {k++;}k = (k < _maxlevel) ? k : _maxlevel;return k;}int insert_element(const K key, const V value) {mtx.lock();int flag = 0;Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode;while (cur) {if (cur->getKey() == key) {flag = 1;cur->set_value(value);}cur = cur->forwards[curlevel]; }curlevel--;}if (flag == 1) {mtx.unlock();return 1;}Node<K, V>* newNode = new Node<K,V>(key, value, getRandomLevel());if (temp_level < newNode->getLevel()) temp_level = newNode->getLevel();curlevel = newNode->getLevel();while (curlevel) {Node<K,V>* prev = HeadNode;cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() > newNode->getKey()) {prev->forwards[curlevel] = newNode;newNode->forwards[curlevel] = cur;break;} cur = cur->forwards[curlevel];prev = prev->forwards[curlevel];} if (!cur)prev->forwards[curlevel] = newNode;curlevel--;}mtx.unlock();return 0;}bool search_element(K key) {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() == key) return true;cur = cur->forwards[curlevel]; }curlevel--;}return false;}void delete_element(K key) {mtx.lock();Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {Node<K,V>* prev = HeadNode;cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() == key) {prev->forwards[curlevel] = cur->forwards[curlevel];break;}cur = cur->forwards[curlevel];prev = prev->forwards[curlevel];}curlevel--;}mtx.unlock();}void print() {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode->forwards[curlevel];std::cout << "Level " << curlevel-1 << ": ";while (cur) {std::cout << cur->getKey() << ":" << cur->get_value() << ';';cur = cur->forwards[curlevel];}std::cout << std::endl;curlevel--;}}void dump_file() {std::ofstream out("D:\\dev_c++\\destination\\out.txt");if (out.is_open()) {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode->forwards[curlevel];while (cur) {out << cur->getKey() << ":" << cur->get_value() << '\n';cur = cur->forwards[curlevel];}curlevel--;}out.close();}}void load_file() {std::ifstream in("D:\\dev_c++\\destination\\out.txt");char buffer[256];if (!in.is_open()) {std::cout << "open error";} else {while (!in.eof()) {std::string s;in >> s;int index = 0;if (s.size() == 0) return; for (int i = 0; i < s.length(); i++) {if (s[i] == ':') {index = i;break;}}
// std::cout << s << ' ';std::string s1 = s.substr(0, index);std::string s2 = s.substr(index + 1, s.length() - 1 - index);
// std::cout << s1 << s2 << std::endl;int key = std::stoi(s1);int value = std::stoi(s2);insert_element(key, value);}}}
};跳表项目总结
这次完整做完了一个小项目，花了几天。最后才发现测试时会有一些不测试就发现不了的小bug，所以说测试还是蛮重要的。