文章目录

• 一、 背景
• 二、初步实现
• • main.cpp
  • creater.h
  • creater.cpp
• 三、优化
• • 修改内容：
  • • creater.h
    • creater.cpp
• 四、复杂化
• • main.cpp
  • creater.h
  • lru.h
  • 运行结果
• 五、后记

一、 背景

孩子经常需要做口算题，现在需要做的是100以内的加减法以及乘法口诀的题目，本来是想从外面直接买，但是买的口算题基本上有一小半都不符合条件，要么是10以内的，要么是20以内的，要么是100以内没有进退位的加减法，所以做完想要的题之后会空下特别多的页，做也不想做，扔了还可惜

所以想着自己写个程序随机生成想要的加减法，再打印出来给孩子做，这样就不会感觉浪费了

二、初步实现

初步实现算法没什么好说的，直接随机2个100以内的数字，过滤一些能想到的badcase（10以内的加减法，或者没有进退位的），然后写入到文件中

main.cpp

#include "creater.h"int main(int argc, char* argv[]) {kousuanCreater kousuan("C:\\Users\\yuwen.song\\Desktop\\VS test\\self test\\kousuan.txt");kousuan.run();return 0;
}

creater.h

#include 
#include 
#include 
#include 
using namespace std;// 口算题类型
enum COLUMN_TYPE : int {COLUMN_INVALID = -1,COLUMN_ADD = 0,COLUMN_MINUS = 1,COLUMN_MULTI = 2,COLUMN_NUM
};// 每行设置3列
const int COLUMN_PER_ROW = 3;
// 在word中使用Calibri(body)字体，12号字，每页能放27行
const int MAX_NUMBER_IN_ONE_PAGE = COLUMN_PER_ROW * 27;
// 默认输出10页题
const int MAX_KOUSUAN_NUM = MAX_NUMBER_IN_ONE_PAGE * 10;class kousuanCreater {
public:kousuanCreater();kousuanCreater(const string& filename, int max_num = MAX_KOUSUAN_NUM);~kousuanCreater();public:void run();private:int createAdd(int i, int j);int createMinus(int i, int j);int createMulti(int i, int j);private:ofstream _file;int _max_num;
};

creater.cpp

#include 
#include "creater.h"kousuanCreater::kousuanCreater() {_file.open("C:\\Users\\yuwen.song\\Desktop\\kousuan.txt", ios::out);assert(_file.is_open());_max_num = MAX_KOUSUAN_NUM;
}kousuanCreater::kousuanCreater(const string& filename, int max_num) {_file.open(filename, ios::out);assert(_file.is_open());_max_num = MAX_KOUSUAN_NUM;
}kousuanCreater::~kousuanCreater() {_file.close();
}void kousuanCreater::run() {// 随机初始化default_random_engine randEngine(time(0));uniform_int_distribution u(5, 100);int count = 0;int lastCount = 0;int num1 = 0;int num2 = 0;int type = COLUMN_INVALID;// 主循环while (count < _max_num) {num1 = u(randEngine);num2 = u(randEngine);type = randEngine() % COLUMN_NUM;switch (type) {case COLUMN_ADD:count += createAdd(num1, num2);break;case COLUMN_MINUS:count += createMinus(num1, num2);break;case COLUMN_MULTI:count += createMulti(num1, num2);break;default:fprintf(stderr, "impossible!\n");break;}// 每COLUMN_PER_ROW列换一次行if (count % COLUMN_PER_ROW == 0 && count > lastCount) {_file << endl;}// 为了避免出现连续的无效题，导致出现连续的空行，记录之前的个数进行比较lastCount = count;}return;
}// 生成加法
int kousuanCreater::createAdd(int num1, int num2) {if (num1 + num2 <= 10) {return 0;} else if (num1 + num2 > 100) {return 0;} else if (num1 <= 10 || num2 <= 10 || num1 % 10 == 0 || num2 % 10 == 0) {return 0;}_file << num1 << " + " << num2 << "\t= \t\t\t";return 1;
}// 生成减法
int kousuanCreater::createMinus(int num1, int num2) {// 固定将num1设置为更大的数，可以避免后续判断哪个更大放前面if (num1 < num2) {swap(num1, num2);}if (num1 < 10 || num2 < 10 || num1 >= 100 || num2 >= 100) {return 0;} else if (num1 - num2 < 10 || (num1 - num2) % 10 == 0) {return 0;}_file << num1 << " - " << num2 << "\t= \t\t\t";return 1;
}// 生成乘法
int kousuanCreater::createMulti(int num1, int num2) {// 将数字限定在1 ~ 9之间num1 %= 9 + 1;num2 %= 9 + 1;if (num1 <= 1 || num2 <= 1) {return 0;}// 固定将num1设置为更大的数，可以避免后续判断哪个更大放前面// 为了更好的匹配乘法口诀if (num1 > num2) {swap(num1, num2);}_file << num1 << " × " << num2 << "\t= \t\t\t";return 1;
}

三、优化

上面的程序写出来后，生成算式时，发现经常同一页上会有重复的题目，所以需要加一个去重的算法。

算法设计是在程序启动时，创建一个MAX_NUMBER_IN_ONE_PAGE大小的数组和hash表来记录，hash表用于快速查找，数组用于记录顺序。在hash表中查找到，则过滤；如果没查找到，则记录到数组中；如果数组已满，则删除数组和hash表中最旧的一个，把当前的插入其中。

修改内容：

creater.h

class kousuanCreater {
...private:int writeStrIntoFile(const string& str);private:
...// 记录过去MAX_NUMBER_IN_ONE_PAGE个数的口算题size_t _str_list[MAX_NUMBER_IN_ONE_PAGE] = {0};// 记录当前使用到的_str_list下标int _list_idx = 0;// 记录当前已有的算式，key使用字符串hash后的结果，速度更快unordered_set _rec;
};

creater.cpp

// 生成加法
int kousuanCreater::createAdd(int num1, int num2) {...return writeStrIntoFile(to_string(num1) + " + " + to_string(num2) + "\t= \t\t\t");
}// 生成减法
int kousuanCreater::createMinus(int num1, int num2) {...return writeStrIntoFile(to_string(num1) + " - " + to_string(num2) + "\t= \t\t\t");
}// 生成乘法
int kousuanCreater::createMulti(int num1, int num2) {...return writeStrIntoFile(to_string(num1) + " × " + to_string(num2) + "\t= \t\t\t");
}int kousuanCreater::writeStrIntoFile(const string& str) {hash str_hash;size_t hash_num = str_hash(str);if (_rec.count(hash_num) > 0) {return 0;}_file << str;_rec.insert(hash_num);if (_str_list[_list_idx] != 0) {_rec.erase(_str_list[_list_idx]);}_str_list[_list_idx] = move(hash_num);_list_idx = (_list_idx + 1) % MAX_NUMBER_IN_ONE_PAGE;return 1;
}

四、复杂化

在上面的优化中提到，其实是有个类似时序的概念存在的，在MAX_NUMBER_IN_ONE_PAGE个数内，按照出现先后进行数据的淘汰，这样就有点类似LRU的，所以继续使用LRU算法进行优化和剔重
LRU的实现思路为：

数据结构使用一个hash表，一个双向链表，双向链表有一个不保存数据的head和tail节点，方便后续操作
hash表用于快速查询，双向链表用于保存时序，具体的操作为：
数据插入 ： 先判断当前数据个数是否到达最大值。如果已经到达最大值，删除tail节点前一个元素，并删除hash表中保存的此节点数据；之后在head节点后插入数据
判断是否存在 ：使用hash表判断当前数据是否存在，如果不存在，返回false；如果存在，使用hash表取出此节点，并将此节点移动到head节点后

小tips：

hash表初始化时reserve足够的空间，避免后续重复申请空间导致的性能损耗
hash表的key用算式hash过后的size_t作为key进行保存，因为size_t的比较比string的比较性能快很多，所以虽然增加了hash值计算的逻辑，但是整体性能会有所提升
较短的函数设置为inline函数，能够避免重复创建和销毁函数栈的性能损耗

根据此思路，最终修改的代码为：

main.cpp

#include "creater.h"int main(int argc, char* argv[]) {int start_time = time(0);kousuanCreater kousuan("C:\\Users\\yuwen.song\\Desktop\\VS test\\kousuan\\kousuan.txt");kousuan.run();int end_time = time(0);fprintf(stderr, "cost time : [%d]\n", end_time - start_time);return 0;
}

creater.h

#include 
#include 
#include 
#include 
#include 
#include 
#include "lru.h"
using namespace std;// 口算题类型
enum COLUMN_TYPE : int {// 无效值COLUMN_INVALID = -1,// 加法COLUMN_ADD = 0,// 减法COLUMN_MINUS = 1,// 乘法COLUMN_MULTI = 2,COLUMN_NUM
};// 每行设置3列
const int COLUMN_PER_ROW = 3;
// 在word中使用Calibri(body)字体，12号字，每页能放27行
const int MAX_NUMBER_IN_ONE_PAGE = COLUMN_PER_ROW * 27;
// 默认输出10页题
const int MAX_KOUSUAN_NUM = MAX_NUMBER_IN_ONE_PAGE * 10;class kousuanCreater {
public:kousuanCreater(const string& filename = "C:\\Users\\yuwen.song\\Desktop\\kousuan.txt", int max_num = MAX_KOUSUAN_NUM) : _file(filename, ios::out), _max_num(max_num),lru(MAX_NUMBER_IN_ONE_PAGE),_count{0} {assert(_file.is_open());}~kousuanCreater() {_file.close();for (int idx = 0; idx < COLUMN_NUM; ++idx) {cout << getCalcTypeStr(idx) << "有" << _count[idx] << "道题" << ", 占比" << _count[idx] * 100 / _max_num << "%" << endl;}}public:void run();private:// 生成加法，返回值为本次生成个数，1 : 有效，0 ： 无效int createAdd(int i, int j);// 生成减法，返回值为本次生成个数，1 : 有效，0 ： 无效int createMinus(int i, int j);// 生成乘法口诀，返回值为本次生成个数，1 : 有效，0 ： 无效int createMulti(int i, int j);private:// 将口算题剔重后写入文件inline int writeStrIntoFile(const string& str) {if (lru.is_exist(str)) {return 0;}lru.add_node(str);_file << str;return 1;}// 加减法通用过滤inline bool commonFilterAddAndMinus(int num1, int num2, int type) {if (num1 < 10 || num2 < 10) {// 小于10return false;} else if (num1 % 10 == 0 || num2 % 10 == 0) {// 整10return false;} else if (num1 > 100 || num2 > 100) {// 大于100return false;}return true;}private:inline string getCalcTypeStr(int type) {string ret_str = "";switch (type) {case COLUMN_INVALID:ret_str = "无效";break;case COLUMN_ADD:ret_str = "加法";break;case COLUMN_MINUS:ret_str = "减法";break;case COLUMN_MULTI:ret_str = "乘法";break;default:ret_str = "未知";break;}return ret_str;}private:// 文件句柄ofstream _file;// 最大口算题个数int _max_num;// 使用LRU去重LRU lru;// 各种算式计数器int _count[COLUMN_NUM];
};

creater.cpp

#include "creater.h"
void kousuanCreater::run() {// 随机初始化default_random_engine randEngine(time(0));uniform_int_distribution u(11, 99);int count = 0;int last_count = 0;int num1 = 0;int num2 = 0;int type = COLUMN_INVALID;// 主循环while (count < _max_num) {num1 = u(randEngine);num2 = u(randEngine);type = randEngine() % COLUMN_NUM;switch (type) {case COLUMN_ADD:count += createAdd(num1, num2);break;case COLUMN_MINUS:count += createMinus(num1, num2);break;case COLUMN_MULTI:count += createMulti(num1, num2);break;default:fprintf(stderr, "impossible!\n");break;}_count[type] += count - last_count;// 每COLUMN_PER_ROW列换一次行if (count % COLUMN_PER_ROW == 0 && count > last_count) {_file << endl;}// 为了避免出现连续的无效题，导致出现连续的空行，记录之前的个数进行比较last_count = count;}return;
}// 生成加法
int kousuanCreater::createAdd(int num1, int num2) {if (!commonFilterAddAndMinus(num1, num2, COLUMN_ADD)) {return 0;} else if (num1 + num2 > 100) {return 0;}return writeStrIntoFile(to_string(num1) + " + " + to_string(num2) + "\t= \t\t\t");
}// 生成减法
int kousuanCreater::createMinus(int num1, int num2) {// 固定将num1设置为更大的数，可以避免后续判断哪个更大放前面if (num1 < num2) {swap(num1, num2);}if (!commonFilterAddAndMinus(num1, num2, COLUMN_MINUS)) {return 0;} else if (num1 - num2 < 10 || (num1 - num2) % 10 == 0) {return 0;}return writeStrIntoFile(to_string(num1) + " - " + to_string(num2) + "\t= \t\t\t");
}// 生成乘法
int kousuanCreater::createMulti(int num1, int num2) {// 将数字限定在1 ~ 9之间num1 %= 9 + 1;num2 %= 9 + 1;if (num1 <= 1 || num2 <= 1) {return 0;}// 固定将num1设置为更大的数，可以避免后续判断哪个更大放前面// 为了更好的匹配乘法口诀if (num1 > num2) {swap(num1, num2);}return writeStrIntoFile(to_string(num1) + " × " + to_string(num2) + "\t= \t\t\t");
}

lru.h

#include 
#include 
#include 
using namespace std;struct myListNode {myListNode(const string& str = "") {this->str = str;this->next = nullptr;this->prev = nullptr;}string str;myListNode* next;myListNode* prev;
};class LRU {
public:LRU(int max_num) {_head = new myListNode();_tail = new myListNode();_head->next = _tail;_tail->prev = _head;_max_num = max_num;_rec.reserve(_max_num);}~LRU() {while (_head) {myListNode* next = _head->next;delete _head;_head = nullptr;_head = next;}}public:bool is_exist(const string& str) {size_t key = _str_hash(str);return is_exist(key);}bool is_exist(size_t key) {auto it = _rec.find(key);if (it == _rec.end()) {return false;}update_node(it->second);return true;}bool add_node(const string& str) {size_t key = _str_hash(str);if (is_exist(key)) {update_node(_rec[key]);return true;} else if (_rec.size() >= static_cast(_max_num)) {del_tail_node();}myListNode* node = new myListNode(str);insert_head_node(node);_rec.insert({key, node});return true;}private:inline bool update_node(myListNode* node) {if (!node) {return false;}node->prev->next = node->next;node->next->prev = node->prev;insert_head_node(node);return true;}inline bool del_node(myListNode* node) {if (!node) {return false;}size_t key = _str_hash(node->str);_rec.erase(key);node->prev->next = node->next;node->next->prev = node->prev;delete node;node = nullptr;return true;}inline void del_tail_node() {if (_tail->prev == _head) {return;}del_node(_tail->prev);}inline bool insert_head_node(myListNode* node) {if (!node) {return false;}_head->next->prev = node;node->next = _head->next;_head->next = node;node->prev = _head;return true;}private:int _max_num;unordered_map _rec;myListNode* _head = nullptr;myListNode* _tail = nullptr;hash _str_hash;
};

运行结果

cost time : [0]
加法有259道题, 占比31%
减法有398道题, 占比49%
乘法有153道题, 占比18%

五、后记

从开始最简单的生成算式，到添加数组 + hash表的方式进行去重，然后再修改为使用LRU的方式进行去重，代码量也从刚开始的156行，到第二版的193行，再到最后的336行，代码也越写越复杂。
当然项目中是不推荐这样写的，如果真的在工作上遇上类似问题，应该第二种方法就够用了，只是单纯为了写复杂练习才慢慢修改为第三版代码。
之后还能想到的复杂化方式有：

1. 修改为消费者模式，把生成算式和写文件分开到不同的线程
2. 使用装饰者模式进行算式过滤条件的组合添加
3. 修改算法，使得每种算式占比尽量均匀分布

暂时想不到继续复杂化的地方了，后续再继续慢慢完善