CSP认证的第4、5题型好比攀登珠峰,令人绝望。而第3题型则像是爬泰山,知道能解决,但总要付出几个小时的艰苦努力。应同学要求试做2023年3月份CSP认证的第3题:LDAP。题面参见CSP官网模拟考试。
第3题型的模式是:解析数据、建立模型、执行操作/答复查询/转换输出。LDAP这题的计算部分属于答复查询。
其他题型输入多为数字,较简单。而第3题型的输入通常是文本,需要运用编译原理的词法分析、语法分析思路解析数据。
v1:基础表达式(20%)
对于 20% 的输入…是原子表达式…
BASE_EXPR = ATTRIBUTE OPERATOR VALUE
先实现简单情况,打只兔子腰里别着:
- 数据结构:两级映射
map<用户, map<属性, 值> >
。 - 算法:蛮力搜索所有具备属性、并且值符合要求(相等、不等)的用户。
- 用户(DN)、属性编号(aid)、属性值(value)都不超过1e9,又不涉及算术计算,用
int
表示即可。 - 基础表达式用
cin >> aid >> op >> val
可直接读入。其中char op;
可能是:
或~
,表示判等、不等。// 失误1 - 输出用户列表要求由小到大排序,于是用
set<int>
保存。// 失误2
提交后很快20分到手:运行错误 20 2.015s 58.58MB
。运行错误也符合预期,因为没实现的功能分支设了断言。
#include <bits/stdc++.h>
using namespace std;using db_t = map<int, map<int, int> >; // u:用户, a:属性
db_t db; // 数据库,{uid: {attrib_id : value} }set<int> eval_base() { // 基础表达式求值int aid, x;char op;cin >> aid >> op >> x;set<int> usr;for(auto& m : db) {const int DN = m.first;for(auto& a : m.second) {if(a.first == aid) { // 存在目标属性if((op == ':' && a.second == x) ||(op == '~' && a.second != x)) {usr.insert(DN);}break; // 这个用户不用再检查其他属性}}}return usr;
}set<int> eval_expr() { // 表达式求值set<int> usr;char c;if(!(cin >> c)) {// EOF} else if(isdigit(c)) { // base exprcin.unget(); // 回退字符cusr = eval_base();} else {assert(false); // 未实现}return usr;
}void print(const set<int>& usr) {bool first = true;for(auto DN : usr) {if(first) {first = false;} else {cout << ' ';}cout << DN;}cout << '\n';
}int main(){int n, m;cin >> n;for(int DN, ak; n > 0 && cin >> DN >> ak; --n) {map<int, int>& attribs = db[DN];for(int aid, x; ak > 0 && cin >> aid >> x; --ak) {attribs[aid] = x;}}cin >> m >> ws;for(int i = 0; i < m; ++i) {print(eval_expr());}
}
v2: 逻辑表达式(40%)
对于 40% 的输入……表达式中至多含有两个原子表达式的逻辑组合,即符合 BNF 语法 EASY_EXPR。
- 普通表达式开头一定是数字,逻辑表达式则以
&
或|
开头。 - 解析时预读一个字符来判断表达式类型。如果是数字则回退
cin.unget()
,然后按简单表达式解析。 - 基础表达式求值结果是
set<DN>
,交集、并集运算可用set_intersection
和set_union
实现。
又用了几分钟写完提交:运行错误 40 2.078s 58.55MB
,仍然符合预期,因为还没实现多层嵌套表达式。一切尽在掌握。
#include <bits/stdc++.h>
using namespace std;using db_t = map<int, map<int, int> >; // u:用户, a:属性
using us_t = set<int>; // 用户列表
db_t db; // 数据库,{uid: {attrib_id : value} }us_t eval_base() { // 基础表达式int aid, x;char op;cin >> aid >> op >> x;us_t us;for(auto& m : db) {const int DN = m.first;for(auto& a : m.second) {if(a.first == aid) { // 存在目标属性if((op == ':' && a.second == x) ||(op == '~' && a.second != x)) {us.insert(DN);}break; // 这个用户不用再检查其他属性}}}return us;
}us_t eval_nested() { // 括号嵌套表达式char c;cin >> c; assert(c == '(');us_t us = eval_base();cin >> c; assert(c == ')');return us;
}us_t eval_expr() { // 表达式求值us_t us;char c;if(!(cin >> c)) {// EOF} else if(isdigit(c)) { // base exprcin.unget(); // 回退字符cus = eval_base();} else {const char logic = c;auto a = eval_nested();auto b = eval_nested();if(logic == '&') {set_intersection(a.begin(), a.end(), b.begin(), b.end(), inserter(us, us.begin()));} else { assert(logic == '|');set_union (a.begin(), a.end(), b.begin(), b.end(), inserter(us, us.begin()));}}return us;
}void print(const us_t& us) {bool first = true;for(auto DN : us) {if(first) {first = false;} else {cout << ' ';}cout << DN;}cout << '\n';
}int main(){int n, m;cin >> n;for(int DN, ak; n > 0 && cin >> DN >> ak; --n) {map<int, int>& attribs = db[DN];for(int aid, x; ak > 0 && cin >> aid >> x; --ak) {attribs[aid] = x;}}cin >> m >> ws;for(int i = 0; i < m; ++i) {print(eval_expr());}
}
v3: 嵌套表达式(40%)
这时感觉胜利在望,因为在v2基础上只需略微出手就能支持全部语法:
us_t eval_expr(); // 前置声明us_t eval_nested() { // 括号嵌套表达式char c;cin >> c; assert(c == '(');us_t us = eval_expr(); // 原为eval_base();cin >> c; assert(c == ')');return us;
}
添加前置声明,递归调用eval_expr
就实现了全部语法功能。满怀希冀地提交:运行超时 40 运行超时 58.55MB
v4:徒劳的优化……(70%)
时间超限(TLE)……回顾题目时间限制:12.0s
,我感到一丝忧虑。接下来的几个小时试了多种方案:
- 属性表
map
换成unordered_map
- 略有提升
- “每个用户的属性个数不超过500,属性编号均不超过1e9”,离散化压缩,把属性ID映射成连续ID?
- 没有变化
- 属性ID离散化后,可以把属性表换成长度固定的向量
vector<int>(505)
,用属性ID做索引。- 运行时错误(RTE)……推测是数组越界。莫非误解了题意,每个人500种属性,但全部用户的不同属性则更多?
- 加段测试代码试验下,如果离散化时属性不只500则输出错误结果,触发错误答案(WA):
- 确实从RTE变成了WA。又用2000等试验几次,已经超出内存上限,全部属性远不止500……
if(virtual_aid >= 505) { // 各用户不同的属性数量远超505,确实触发了错误cout << "OVERFLOW" << endl;return 0;}
v5:数据结构(100%,7.31s)
以前在公司用过数据仓库,也接触过数据引擎Kudu方面的研发。回忆数据库的两大类型:
- 联机事务处理(OLTP):追求高效的增删改查。数据通常按行(记录)组织。
- 联机分析处理(OLAP):追求高效的查询性能。除了分区、MPP等技术外,还常用列式存储。
这题表达式求值就全是数据查询、没有修改,类似OLAP,意味着应该用列式存储?
- 数据结构:
map<属性, map<用户, 属性值> >
,读入时把用户ID和属性值按属性汇集保存。 - 算法:根据属性ID直接得到全部具备该属性的用户,再按属性值过滤,不用扫描全部用户。
修改、提交:正确 100 7.312s 31.54MB
,通过了!这是最关键的一步优化。
v6:散列表(100%,7.29s)
之前行式数据组织时,用散列表保存属性内存超限。改用列式存储后把map
换成unordered_map
能否更快?
- 修改、提交:
正确 100 7.296s 29.55MB
优化效果微弱。
v7:预排序+向量(100%,2.25s!)
又发现优化点:
- 交集、并集都保持结果有序。如果基础表达式的结果有序,那么最终结果也有序。
- 所以没必要用
set
。而set
的集合运算不如有序的vector
快。 - 可以修改
eval_base
,在返回结果前对vector
排序。但每次过滤用户列表时都要重复排序。 - 可在解析数据后,对所有属性对应的用户列表预先排序。以后过滤出的用户列表自然有序。
修改、提交:正确 100 2.250s 29.55MB
又缩短5秒!
#include <bits/stdc++.h>
using namespace std;using us_t = vector<int>; // 用户集
using uv_t = pair<int, int>; // (用户, 属性值)
using db_t = unordered_map<int, vector<uv_t> >; // {属性编号 -> [uv_t]}
db_t db; // 列式数据库us_t eval_base() { // 基础表达式求值int aid, x;char op;cin >> aid >> op >> x;us_t us;if(op == ':') { // 提取常性表达式for(auto& uv : db[aid]) {if(uv.second == x) { // 属性值相等us.push_back(uv.first);}}} else {for(auto& uv : db[aid]) {if(uv.second != x) { // 属性值不等us.push_back(uv.first);}}}return us;
}us_t eval_expr(); // 前置声明us_t eval_nested() { // 括号嵌套表达式char c;cin >> c; assert(c == '(');us_t us = eval_expr();cin >> c; assert(c == ')');return us;
}us_t eval_expr() { // 表达式求值us_t us;char c;if(!(cin >> c)) {assert(false); // 不应EOF} else if(isdigit(c)) { // 基础表达式cin.unget(); // 字符c属于表达式,回退us = eval_base();} else { // 逻辑表达式auto a = eval_nested();auto b = eval_nested();if(c == '&') {set_intersection(a.begin(), a.end(), b.begin(), b.end(), inserter(us, us.begin()));} else { assert(c == '|');set_union (a.begin(), a.end(), b.begin(), b.end(), inserter(us, us.begin()));}}return us;
}void print(const us_t& us) {bool first = true;for(auto DN : us) {if(first) {first = false;} else {cout << ' ';}cout << DN;}cout << '\n';
}int main(){ios::sync_with_stdio(0); // 参见下步IO优化。cin.tie(0);cout.tie(0);int n, m;cin >> n;for(int DN, ak; n > 0 && cin >> DN >> ak; --n) { // 每位用户for(int aid, x; ak > 0 && cin >> aid >> x; --ak) { // 每种属性db[aid].push_back(make_pair(DN, x)); // 将用户、属性值加到属性对应的向量。}}auto cmp = [](const uv_t& a, const uv_t& b) { return a.first < b.first; };for(auto& v : db) { // 全读入后才能按用户ID排序sort(v.second.begin(), v.second.end(), cmp);}for(cin >> m; m > 0; --m) {print(eval_expr());}
}
v8:IO优化(100%,0.64s!)
- 用户最多2500,属性最多500,每个属性用编号、值2个数字描述,共约
2500 * 500 * 2 ~ 2.5M
个数字。 - 表达式最多500条,最长2000字符,又是
1M
字符。
所以这题应该有巨大的IO优化空间:
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
...
解除C的桎梏后:正确 100 0.640s 29.60MB
,满意!
经验教训
- 失误1:版本1用整行读入再解析的方式。版本2改为
istringstream
。后来试验发现从cin
直接混合读入int char int
即可。 - 失误2:为满足输出有序的要求,轻率地选用
set<int>
保存数据,导致显著开销(接近5s)。 - 失误3:一开始就抱着演示、混分的态度,没分析时间复杂度就开始编码。如果认真分析,正确的数据结构还是挺明显的。
- 经验:再次验证了“当设计出恰当的数据结构时,算法往往直白而高效”的说法。