1 简介 🟠 由若干个位（bit）组成，它提供一些成员函数，使程序员不必通过位运算就能很方便地访问、修改其中的任意一位。 2 创建 1️⃣ 调用默认构造函数。 1 bitset<N> b; 3 常用的成员方法 成员方法 功能 count() 返回bitset中 1 的个数。 size() 返回位数。 test() 返回某一位下标是否为1 set() 全部置1,或者某一位置1或0 flip() 全部取反,或者某一位取反

🔗 202303 题号 时间/min 正确率 备注 1 20 100 2 30 100 3 40 0 🔸 bitset、map、set用法🔸 堆栈 🔗 202212 题号 时间/min 正确率 备注 1 10 100 2 45 100 🔸 fill函数 3 65 100 🔸 蛇形填充：规模较小时，可用一个矩阵专门写出下标🔸 cos函数 🔗 202209 题号 时间/min 正确率 备注 1 10 100 2 40 100 🔸 动态规划：01背包问题 3 100 40 🔸 实在做不出来留1h把简单的情况做了🔸 map 的 erase 用法🔸 选好数据结构很重要！ 🔗 202206 题号 时间/min 正确率 备注 1 10 100 2 30 100 🔸 题目给的一串数字不一定是顺序的，不要想当然！ 3 120 100 🔸 cin/cout 提速🔸 vector 查找元素较慢，可用 set 🔗 202203 题号 时间/min 正确率 备注 1 10 100 2 35 100 3 🔗 202112 题号 时间/min 正确率 备注 1 15 100 2 30 100 3 120 40 🔸 注意审题！bug调不出来最好重读一遍题目！🔸 计算多项式中x的系数：找递推关系🔸 模拟多项式除法 🔗 202109 题号 时间/min 正确率 备注 1 10 100 2 50 100 🔸 找前后递推关系🔸 set 的倒序遍历；map 3 🔗 202104 题号 时间/min 正确率 备注 1 10 100 2 60 100 🔸 二维压缩数组🔸 判断时注意整数除法会向下取整 3 🔗 202012 题号 时间/min 正确率 备注 1 5 100 2 40 100 🔸 找递推关系🔸 对不规则排列的数组，用 set 和 map 会快很多 3 🔗 202009 题号 时间/min 正确率 备注 1 30 100 2 20 100 3 🔗 202006 题号 时间/min 正确率 备注 1 30 100 2 20 100 3

本文为论文 SWIRL: Selection of Workload-aware Indexes using Reinforcement Learning 的阅读笔记。 1 简介 🔴 我们提出了一种基于RL的索引选择方法，与最好的竞争者的性能相匹配。 🟡 我们的解决方案采用了一个复杂的工作负载模型，以推广到具有未见过的查询的工作负载，并依靠无效动作屏蔽来减少训练时间。 🔵 我们包括了基于RL的索引选择的首次调查和性能研究，并通过PostgreSQL上复杂的分析性数据库基准评估我们的方法。 2 背景 2.1 索引选择问题 大的解决方案空间。 相关候选索引的数量取决于工作负载查询访问的属性数量、每个索引的最大属性数量。评估所有候选组合通常是不切实际的，因为它们的数量超过了属性的数量级。 索引交互。 一个索引的存在会影响其他索引的性能。因此，在索引选择的每个步骤中，必须要考虑到当前存在的索引，经常需要重新计算候选索引的收益。 量化索引影响。 漫长的创建和执行时间使得物理上创建索引并不可行。索引选择方法通常依赖于估计而不是实际测量。（假设索引） 2.2 问题定义 假设有 N 个查询，K 个属性，每个查询 n 的属性表示为 $q_n⊆{1,…,K},n=1,…,K$ 。 W为每个索引包含的属性个数（索引宽度），$m_i$ 为需要的存储空间。索引的选择由子集 $I^*⊆I$ 表示，其执行成本为 $c_n(I^*)$ ，出现频率为 $f_n$ 。总的工作负载成本为： 目标是确定 $I^*$ 使 $C(I^*)$ 最小，并且不超过给定预算 B。 2.3 强化学习 强化学习（RL）包括一组算法，用于解决决策问题。 这些问题的特点是，在给定状态 $s_t∈S$ ，反复允许一个代理执行行动 $a_t$ ，其中 $a_t∈A$ 。在执行了所选择的行动后，达到新的状态 $s_{t+1}$ ，重复该过程。为了向代理人提供关于行动是否选择得当的反馈，他们会收到反馈信号，即每次决策后的奖励 $r_t$ 。 问题是要找到一个最佳决策，它将状态映射为行动，涉及到以时间 t 为开始状态的未来长期报酬：

本文为论文 Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe? 的阅读笔记。 1 引言 🟥 我们提出了一个增强的访问路径成本模型，它可以捕捉到在支持访问共享的主内存优化的分析数据系统中的选择运算符的性能。 🟨 访问路径的选择是需要的；即使在快速扫描时，经过调整的二级索引也是有用的。 🟩 我们表明，除了【选择性】和【硬件特性】外，访问路径的选择还需要动态地考虑到【查询并发性】。 🟦 我们将访问路径选择整合到一个现代分析原型的优化器中，并表明即使访问路径选择现在是一个更复杂的操作，必须考虑到更多的信息，它仍然可以快速完成；并且可以在各种工作负载上进行。 🟪 使用该模型，我们展示了何时使用索引的决定是如何随着数据布局和硬件属性的变化而变化的。 2 访问路径选择 2.1 模型准备工作 索引的选择性： 指不重复的索引值和数据表的记录总数的比值，取值范围在 [0,1] 之间。 索引的选择性越高则查询效率越高，因为选择性高的索引可以让 MySQL 在查找时过滤掉更多的行。 2.2 内存中共享扫描建模 🔴 扫描的数据移动。给定内存带宽 $BW_S$ ，顺序扫描数据的成本为： $TD_S = \frac {N·ts}{BW_s}$ 。 🟡 谓词评估。假设 p 是时钟周期，fp 是指令流水线的常数，则谓词评估 PE 的 CPU 为： $PE = 2 · fp · p · N$ 。

这里记录了在智能数据存储与管理实验室的实习经历。前部分是关于【深度学习】、【hash】的内容；后部分主要和【index】相关。 2022 【2022.10】 看论文： Vision GNN: An Image is Worth Graph of Nodes 🔗 阅读笔记 参与论文修改： Supervised Hierarchical Online Hashing for Cross-modal Retrieval PS：主要是帮学长找语法错误、可以改进的地方 【2022.11】 看论文： Label Embedding Online Hashing for Cross-Modal Retrieval 🔗 阅读笔记 参与论文修改： Supervised Hierarchical Online Hashing for Cross-modal Retrieval 【2022.12】 参与论文修改： Supervised Hierarchical Online Hashing for Cross-modal Retrieval 2023 【2023.04】 看论文： Magic mirror in my hand, which is the best in the land?

1 二叉搜索树BST 🔴 对于 BST 的每一个节点 node，左子树节点的值都比 node 的值要小，右子树节点的值都比 node 的值大。 🔵 对于 BST 的每一个节点 node，它的左侧子树和右侧子树都是 BST。 二叉搜索树问题的核心是【利用中序位置】。 以下代码可以将 BST 中每个节点的值升序打印出来： 1 2 3 4 5 6 7 void traverse(TreeNode root) { if (root == null) return; traverse(root.left); // 中序遍历代码位置 print(root.val); traverse(root.right); } 后面两道题都是基于这个性质实现的。 2 二叉搜索树中第K小的元素 题目 🔗力扣 230. 二叉搜索树中第K小的元素 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。 解析 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { private: int count=0,k,ans; public: int kthSmallest(TreeNode* root, int k) { this->k = k; traverse(root); return ans; } void traverse(TreeNode* root){ if(root==nullptr) return; traverse(root->left); // 中序遍历位置，找到第k小的元素 count++; if(count == k){ ans = root->val;return; } traverse(root->right); } }; 扩展 🔴 利用【BST 中序遍历就是升序排序结果】这个性质，寻找第 k 小的元素的时间复杂度是 O(N)。

1 算法思路 🔴 所有递归的算法，本质上都是在遍历一棵（递归）树，然后在节点（前中后序位置）上执行代码。 🔵 【归并排序】类似于【二叉树的后序遍历】，使用【分治算法】的思想。 🟡 递归的 sort 函数就是二叉树的遍历函数，而 merge 函数就是在每个节点上做 的事情 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 // 定义：排序 nums[lo..hi] void sort(int[] nums, int lo, int hi) { if (lo == hi) { return; } int mid = (lo + hi) / 2; // 利⽤定义，排序 nums[lo..mid] sort(nums, lo, mid); // 利⽤定义，排序 nums[mid+1..hi] sort(nums, mid + 1, hi); /****** 后序位置 ******/ // 此时两部分⼦数组已经被排好序 // 合并两个有序数组，使 nums[lo.

【二叉树问题的通用思路】 🔴 是否可以通过 遍历一遍二叉树 得到答案？如果可以，用一个 traverse 函数配合外部变量来实现。 🟡 是否可以定义一个 递归函数 ，通过 子问题（子树） 的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的 返回值 。 🔵 明白二叉树的 每个节点需要做什么 ，需要 在什么时候（前中后序）做 。 🟢 二叉树的构造问题⼀般使用【分解问题】的思路：构造整棵树 = 根节点 + 构造左子树 + 构造右子树。 1 最大二叉树 题目 🔗力扣 654. 最大二叉树 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建: 创建一个根节点，其值为 nums 中的最大值。 递归地在最大值 左边 的 子数组前缀上 构建左子树。 递归地在最大值 右边 的 子数组后缀上 构建右子树。 返回 nums 构建的 最大二叉树 。 解析 🔴 遍历数组把找到最大值 maxVal，得出根节点 root 。

【二叉树问题的通用思路】 🔴 是否可以通过 遍历一遍二叉树 得到答案？如果可以，用一个 traverse 函数配合外部变量来实现。 🟡 是否可以定义一个 递归函数 ，通过 子问题（子树） 的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的 返回值 。 🔵 明白二叉树的 每个节点需要做什么 ，需要 在什么时候（前中后序）做 。 1 翻转二叉树 题目 🔗力扣 226. 翻转二叉树 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。 遍历一遍二叉树 tips：遍历一遍二叉树一般比分解子问题快一些。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public: TreeNode* invertTree(TreeNode* root) { traverse(root); return root; } TreeNode* traverse(TreeNode* root){ if(root==nullptr) return nullptr; // 前序位置，交换左右子节点 TreeNode* temp = root->left; root->left = root->right; root->right = temp; traverse(root->left); traverse(root->right); return root; } }; 分解问题 1 2 3 4 5 6 7 8 9 10 11 class Solution { public: TreeNode* invertTree(TreeNode* root) { if(root==nullptr) return nullptr; TreeNode* temp = invertTree(root->left); root->left = invertTree(root->right); root->right = temp; return root; } }; 2 填充节点的右侧指针 题目 🔗力扣 116.

1 田地丈量 🔗 题目：田地丈量 分情况求出长、宽，再计算总和即可。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include<bits/stdc++.h>using namespace std; int n,a,b,x1,y1,x2,y2,x,y,ans=0; int main(){ cin>>n>>a>>b; for(int i=0;i<n;i++){ cin>>x1>>y1>>x2>>y2; if(x1>=a || y1>=b || x2<=0 || y2<=0) continue; if(x1<=0) x=min(a,x2); else x=min(a,x2)-x1; if(y1<=0) y=min(b,y2); else y=min(b,y2)-y1; ans += x*y; } cout<<ans; } 2 垦田计划 🔗 题目：垦田计划 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include<bits/stdc++.

1 快速排序&归并排序 🔴 快速排序：二叉树的前序遍历 先构造分界点，然后去左右子数组构造分界点。 要对 nums[lo..hi] 进行排序，我们先找⼀个分界点 p，通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p]，且 nums[p+1..hi] 都大于 nums[p]，然后递归地去 nums[lo..p-1] 和 nums[p+1..hi] 中寻找新的分界点。 1 2 3 4 5 6 7 8 void sort(int[] nums, int lo, int hi) { /****** 前序遍历位置 ******/ // 通过交换元素构建分界点 p int p = partition(nums, lo, hi); sort(nums, lo, p - 1); sort(nums, p + 1, hi); } 🔵 归并排序：二叉树的后序遍历 先对左右子数组排序，然后合并，即分治算法。 （对 nums[lo..hi] 进行排序，我们先对 nums[lo..mid] 排序，再对 nums[mid+1.

本文为论文 Slalom: Coasting Through Raw Data via Adaptive Partitioning and Indexing 的阅读笔记。 🟠 Slalom 一个通过监视用户访问模式来适应工作负载变化的原位查询引擎。 🟡 关键组件 在线分区和索引方案 为原位查询引擎量身定制的分区和索引调优器。 🟢 性能优势 对原始数据文件进行逻辑分区；为每个分区构建轻量级分区特定的索引 1 简介 🟠 加载、索引和调优的成本 考虑到所涉及的数据大小，对数据的任何转换、复制和准备步骤都会在查询数据前引入大量延迟。缺乏对工作负载的先验知识使得物理设计决策几乎不可能。 🟡 自适应分区和细粒度索引 使用第一次表扫描来生成分区和轻量级索引提示 数据集以动态方式部分索引，以适应三个关键工作负载特征：数据分布；查询类型；投影属性。 调优器通过以下方式降低数据访问成本: 对原始数据集进行逻辑分区，在不进行物理重构的情况下将其虚拟地分解为更易于管理的块 在每个逻辑分区上选择适当的索引策略，以提供有效的数据访问。（细粒度的索引决策） 🟢 基于Slalom的高效 In-Situ Query 将在线分区和索引调谐器集成到原位查询处理原型系统Slalom中 Slalom在逻辑上将原始数据划分为分区，并根据每个分区的“热度”(访问频率)、针对每个分区的查询类型来选择构建哪个细粒度的分区索引。 Slalom填充二进制缓存(从原始数据转换为二进制数据的缓存)以进一步提高性能 Slalom使用基于随机成本的决策算法调整当前分区和索引方案来适应工作负载的变化 🔵 贡献 我们提出了原始数据文件的逻辑分区方案，该方案支持在每个分区级别上进行细粒度的索引决策。 好处：带来了原位查询处理索引的好处；索引构建成本低；内存占用小。 我们将分区和索引调谐器集成到我们最先进的原型原位查询引擎Slalom中。 2 相关工作 🟣 对原始数据的查询 Slalom使用的技术可以通过减少索引的大小、为每个文件分区构建内存效率高的索引来提高系统的可伸缩性。 Slalom不加载所有数据，而是利用工作负载局域性自适应地为原始数据创建细粒度索引方案，并逐渐减少I/O和访问成本，同时在适度的内存预算下运行。 🔵 数据库分区