电影网站如何做seo优化,2021能看的网站不要app贴吧,公司网站建设制作价格,重庆建设工程证照查询网站生成文件和从文件中读取数据。
需求如下#xff1a; 你的任务是实现 SkipList 类中的数据持久化成员函数和数据加载成员函数。 持久化数据成员函数签名#xff1a;void dump_file(); 该成员函数负责将存储引擎内的数据持久化到文件中。数据的持久化格式是将每个键值对写入文…生成文件和从文件中读取数据。
需求如下 你的任务是实现 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()) {NodeK,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); //下标从index1开始std::cout s1 s2 std::endl;
// int key std::stoi(s1);int value std::stoi(s2);insert_element(key, value);}}}
这个实现的就只是int类型的读取文件。
运行效果如图 由于我们采用的是随机层数的机制所以每次结果层数会不一致也很正常。这也是跳表好玩的地方之一了。
整体代码如下
#includestdlib.h
#include iostream
#include cstring
#include fstream
#include iostream
#include string
#include sys/time.htemplatetypename 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 NodeK, V*[node_level1];memset(this-forwards, 0, sizeof(NodeK,V*)*(node_level1));}~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;}};templatetypename K, typename V
class SkipList {
private:NodeK,V* HeadNode nullptr;int _maxlevel 0;int temp_level 0;
public:SkipList(int maxlevel 500) {_maxlevel maxlevel;HeadNode new NodeK, 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;NodeK,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;NodeK, V* newNode new NodeK,V(key, value, getRandomLevel());if (temp_level newNode-getLevel()) temp_level newNode-getLevel();curlevel newNode-getLevel();while (curlevel) {NodeK,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) {NodeK,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) {NodeK,V* cur HeadNode;int curlevel temp_level;while (curlevel) {NodeK,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() {NodeK,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()) {NodeK,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() {SkipListint, 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 SkipListK, 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 SkipListK, V::delete_element(K key) {mtx.lock(); // 加锁// ... 算法过程省略mtx.unlock(); // 解锁return;
}
最终代码如下
#includestdlib.h
#include iostream
#include cstring
#include fstream
#include iostream
#include string
#include mutex
#include sys/time.hstd::mutex mtx; templatetypename 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 NodeK, V*[node_level1];memset(this-forwards, 0, sizeof(NodeK,V*)*(node_level1));}~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;}};templatetypename K, typename V
class SkipList {
private:NodeK,V* HeadNode nullptr;int _maxlevel 0;int temp_level 0;
public:SkipList(int maxlevel 500) {_maxlevel maxlevel;HeadNode new NodeK, 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;NodeK,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;NodeK, V* newNode new NodeK,V(key, value, getRandomLevel());if (temp_level newNode-getLevel()) temp_level newNode-getLevel();curlevel newNode-getLevel();while (curlevel) {NodeK,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) {NodeK,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();NodeK,V* cur HeadNode;int curlevel temp_level;while (curlevel) {NodeK,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() {NodeK,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()) {NodeK,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() {SkipListint, 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// 测试用的数据量大小
SkipListint, 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 itid*tmp, count0; counttmp; 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 itid*tmp, count0; counttmp; 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::durationdouble 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::durationdouble elapsed finish - start;std::cout get elapsed: elapsed.count() std::endl;}pthread_exit(NULL); // 主线程退出return 0;
}
我们还需要新建一个项目工程文件将之前写的代码重命名成skiplist.h编译运行进行测试编译链接要按照如下指令来
g --stdc11 main.cpp -o stress -pthread
dev_c里面点进这里修改这个即可。 但在测试过程中我发现即便是很少的数据量比如4运行黑框仍旧会卡住一直无法出来。自己检查代码后才发现是我在插入数据函数加锁时只在return 0的情况下加了锁因此在return 1 的情况下系统就陷入了死锁局面 加上去之后就好了。
修改后代码如下
//skiplist.h
#includestdlib.h
#include iostream
#include cstring
#include fstream
#include iostream
#include string
#include mutex
#include sys/time.hstd::mutex mtx; templatetypename 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 NodeK, V*[node_level1];memset(this-forwards, 0, sizeof(NodeK,V*)*(node_level1));}~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;}};templatetypename K, typename V
class SkipList {
private:NodeK,V* HeadNode nullptr;int _maxlevel 0;int temp_level 0;
public:SkipList(int maxlevel 500) {_maxlevel maxlevel;HeadNode new NodeK, 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;NodeK,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;}NodeK, V* newNode new NodeK,V(key, value, getRandomLevel());if (temp_level newNode-getLevel()) temp_level newNode-getLevel();curlevel newNode-getLevel();while (curlevel) {NodeK,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) {NodeK,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();NodeK,V* cur HeadNode;int curlevel temp_level;while (curlevel) {NodeK,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() {NodeK,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()) {NodeK,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所以说测试还是蛮重要的。
