DSA PA3 REPORT

CST 3-2 Report

算法构思

位图数据结构设计：本题最大的限制是6MB的空间，也就是只提供 $6\times2^{20}$ B大小的空间，而字符串长度要求需要能存$2^{24}$个数的空间，这就意味着不能用传统的int数组或bool的方式来存，于是自然想到了上课介绍的位图数据结构，这种数据结构将每个01字符存储在了一个bit里。这样成功将存储空间压缩到了$2^{21}$B的大小，从而满足题目对空间的要求。具体来说，是通过char数组的方式，以每个字符存储8个01字符的方式存储该字符串。

此外，在查询固定长度的子串时，由于一个字符某一固定长度的子串个数和这个字符长度几乎相同（准确来说只相差了一个子串长度），为了记住查询结果，我们同样需要一个规模和字符串大小相同的01字符串，而这个字符串的存储又可以通过一个位图实例来实现。

因此，该算法用到了两个位图实例，第一个位图实例b负责存储字符串，第二个位图found负责存储针对某一特定位数，符合这种长度的01串是否出现在字符串中，具体来说，第 i 位存储的是原字符串中是否存在 i 二进制形式下的子串。

针对某一特定长度k，查找是否存在NotFound子串: 在之前的位图设计中已经说明了found实例的含义，接下来还需要特别说明的是如何更高效的实现在原串中检索所有子串。首先，注意到如果线性扫描子串的话，每次扫到的子串和前一个子串相比只要首尾两个字符不同，这就意味着不用每次都把子串转化为十进制数，而是可以通过首尾数字对上一个子串对应的十进制数进行适当的运算转换成下一个子串对应的十进制数。此外，线性扫描时，设置num变量来记录发现了多少个不同的子串，可以稍稍提高之后寻找最小字典序的子串的效率。

通过二分查找来优化搜索效率：由于字符串长度限制在$2^{24}$范围内，这就意味着，NotFound子串长度不能超过24，也就是说我们最终找到的这个NotFound子串长度确定在$[1,24]$内，而我们需要找的是满足在原串中找不到该子串，且该子串在所有NotFound子串中长度和字典序最小，于是便可以通过二分查找的方式优化时间效率。

具体来说，算法针对特定子串长度k，通过函数see(k)来判断是否存在NotFound子串，并在res中保存该所有该长度且不存在在原字符串的子串中字典序最小的那个，如果返回值为true，即找到了较小子串，下一次查找的范围就在[lo,k)之间，否则就在$[mid+1,hi)$之间（$lo和hi初始为1和25$）

时间和空间复杂度的估算

时间复杂度：根据上一节对算法的描述，位图的赋值和循秩访问都是$O(1)$时间的，因此字符串读入时间为$O(n)$。此外，针对特定一子串长度的查询，需要多次线性扫描，因此时间复杂度为$O(n)$而子串长度在$[1,logn]$之间，通过二分查找优化，需要查找$O(log(logn))$次，因此总查询时长的时间复杂度为$O(nlog(logn))$。

综上，总时间复杂度为$O(nlog(logn)) n=2^{24}$

空间复杂度：每个位图实例都需要开一个char数组，其大小正比于字符串长度，相比一个char存一个字符来说现在一个char可以存8个字符，空间复杂度为$O(n/8)$，消去常数后是$O(n)$，除此以外程序没有其它的大开销，因此总的空间复杂度就是$O(n)$

CST 3-4-2 Report

算法构思

线段树动态创建结点

根据提示，本题考察的是线段树这一数据结构，但由于n数据范围较大（$n<2^{31})$，将完整线段树建出来所需要的空间成本过高（完整建出整棵树的空间复杂度是$O(n)$）。而另一方面，查询/插入区间操作的次数m比较有限（$m<2\times 10^{5}$），实际上并不会真正用到每一个节点，尤其是一些靠近树叶的节点的信息，因此我们需要使线段树创立结点动态化，即不是在一开始就将线段树完整的建出来，而是”随用随建“，只有当操作需要读取/改变某个节点的儿子节点的信息时才将其儿子节点建立，从而起到减少空间占用的效果。

具体来说，如讲义634页所展示，每次翻盘/查询操作所访问到的节点可以构成一棵二叉树，而这棵二叉树又只有$O(log(n))$个叶节点（一个线段被分成两半，左半部分每层至多一个右子树作为叶节点，右半部分同理），根据二叉树性质，二叉树的非叶节点数=叶节点数-1,所以整个二叉树的节点个数也是$O(log(n))$的，因此m次操作，至多会访问到$O(mlog(n))$个节点，并不会访问所以节点。最终，根据本题数据范围和空间限制，我选择将存储节点的数组开到$10^6$大小。

函数设计

懒惰标记：对于每一个节点，我为其设计了懒惰标记：懒惰标记lazy的值表示该节点表示的区间内，除了sum记录的翻牌次数外，该节点下的每个节点还会被翻lazy次，这样当翻盘时遇到某一结点表示的区间完全包含于操作区间时，只需要为其懒惰标记加1即可，而不需要递归其子树

push_down: 当操作需要访问某个节点的子节点时，首先需要尝试为其创建子节点，然后再将懒惰标记下放，并将该节点的sum值更新。

merge_up: 用于翻牌操作，但对某节点的子节点进行翻牌操作后，此时子节点的sum变为修改后的值，需要根据左右子节点的sum值更新父节点的sum，从而使父节点sum值记录修改后的结果

翻牌：用递归函数的方式实现，针对某一结点，对其$[l,r]$子区间进行翻牌操作，会有四种情况：1.$[l,r]$恰好就是这个节点表示的区间，则修改其懒惰标记后返回。2.$[l,r]$仅包含于左子树，则递归其左子树。3.$[l,r]$仅包含于右子树，则递归右子树。4.$[l,r]$既包含于左子树，又包含于右子树。对于后三种情况，需要同时递归两棵子树，并在递归后将两侧结果merge_up赋给父节点。

查询：设计思路和翻牌类似，不同在于查询相当于”只读“，并不会真正修改sum的大小（但依然会有懒惰标记下放的情况，比如所查询的区间设计了新节点的建立），所以在情况1中只需要返回其sum值，而情况4中不再需要merge

常数优化

为了将节点数组开的尽量大，我尽可能缩小了每个节点的大小，最后每个Node类只有3个int和1个long long，这样就可以使存储节点的数组开到$10^6$大小。

时间和空间复杂度的估算

时间复杂度：如前文”线段树动态创建结点“一节所述，每次翻牌/查询操作，至多访问到$O(log(n))$个节点，而对每个节点操作的时间复杂度为$O(1)$，共进行m次这样的操作，所以总的时间复杂度为$O(mlog(n))$

空间复杂度：如前文”线段树动态创建结点“一节所述，只需要$O(mlog(n))$个节点就可以满足m次操作访问节点的需求。而每个节点的空间复杂度为$O(1)$，因此总的空间复杂度为$O(mlog(n))$（在程序中我开到了$10^6$）

CST 3-5 Report

做完 CST 3-6 最近邻查找后，本以为手握KD树模板，这道题会完成得比较快，但事实证明不同的问题中kdtree差异还是很大的，为此花了不少时间来改进原树模板。

算法构思

KD-Tree构造方法

结点

KD-Tree每个结点存储以下信息：

l,r：左右孩子下标

num[2]：该结点所表示点的坐标

dim：该结点所“切”的维度，$dim\in[0,d)$

up_bond[2],low_bond[2]：每一个结点都代表在2维空间的矩形中“切”了一刀，这两个数组表示的就是这个矩形的上下界。对于每一个结点点，我们规定其上下界为这个结点表示区域包含的所有结点的上下确界，特别的，如果只有一个结点，那么其上下确界就是自己的坐标。

max_temp,min_temp:该结点表示区域内的最高气温和最低气温。

建立KD-Tree

原始结点被输入后存储在数组node中，我们用函数build(lp,rp,d0)递归地建立KD-Tree，对每一个递归实例：

  1. 将node数组中下标处于$[lp,rp]$之间的部分进行升序排序，排序依据是其第d0维的坐标大小($d0=0 , 1$)
  2. 对区间进行线性扫描，确定空间坐标的上下确界，更新up_bond[2],low_bond[2]
  3. 找到排序后区间内中位数的结点，用该结点的坐标来构造一个KD-Tree中的结点，并将该结点保存在kdtree[index]中
  4. 递归$[lp,rp]$的左半部分和右半部分（构造时需要判定左右区间是否为空，如果为空则不需要再为其建立子结点，此时其子结点下标指向0，也可视作空结点或垃圾结点），递归构造kdtree[index]的左右子树，最后更新其区域内温度最大值和最小值。

区间内的温度最值查找：

我们设计了query_p函数来递归地查找结点p表示的区域和给定查找区间的交集，并更新查找到的气温最大值和最小值，对于每个结点分为以下四种情况讨论：

  1. 到达空结点，则直接返回，不做更新操作
  2. 结点表示区域包含于查找区间，则直接根据这个结点标记的气温最大值和最小值更新查找结果，不需要再深探
  3. 结点表示区域与查找区间完全无交集，则直接返回不做更新操作
  4. 结点表示区域与查找区域存在交集，则首先根据这个结点表示站点的温度最大值和最小值更新查找结果，然后对其左右子树进行深探。

在实际写代码的时候，我们采取比较两个维度来确定查找区间和结点区间的关系，这是和讲义中KD树区间查询不同的地方，但显然这个剪枝要比比较单维度更强，实际运行的时候效果也更好。

时间和空间复杂度的估算

时间复杂度

本题的时间消耗来自两步操作：建立KD-Tree和对KD-Tree的查找，下面分别对其进行分析。

建立KD-Tree的时间复杂度可以这样分析：考虑一颗满树，其深度为k的层有$2^k$个结点，也就对应在递归建立是要创建$2^k$个递归实例，对于每一个递归实例，其包含的区间长度为$len \leq \frac {n}{2^{k}}$，每一个递归实例中，时间复杂度主要来自区间排序，其复杂度为$O(lenlog(len))$而每一层总的时间复杂度应为$O(lenlog(len) \cdot 2^k) = O(n(logn-k)) k=1,2,… logn$。KD-Tree共有$logn$层，因此总的时间复杂度为$O(n(logn)^2)$。

对KD-Tree的每次区间查找，根据讲义中对KD树查询的时间复杂度分析，由于每两刀最多切到2个矩形，因此复杂度递推式满足$Q(n)=2Q(n/4)+O(1)$，因此其复杂度为$O(\sqrt n)$（讲义中的问题是记录具体的所有点，因此还要加上report的复杂度r，但本题只获取区间最值，更新次数应正比于区间包含的矩形框个数，对于完全包含于区间的矩形框，不需要深究其内部的每个点，因而不需要加r）。

综上，结合这两步操作，总的时间复杂度为$O(n(logn)^2+m\sqrt n)$

空间复杂度

KD-Tree存储在数组kdtree中，每个结点的struct需要存储12个int，数组空间消耗为$O(n)$，原始结点存储在二维node数组中，其大小也为$O(n)$，建树的递归实例个数应等于KD树的结点个数，节点个数不大于2n，递归建树空间复杂度为$O(n)$，查询递归的递归实例个数应等于访问结点的个数$O(log(n))$。

因此，总的空间复杂度为$O(n+log(n)) = O(n)$

CST 3-6 Report

算法构思

KD-Tree构造方法

结点

KD-Tree每个结点存储以下信息：

l,r：左右孩子下标

num[5]：该结点所表示点的坐标

dim：该结点所“切”的维度，$dim\in[0,d)$

up_bond[5],low_bond[5]：每一个结点都代表在d维空间($2\leq d \leq5$)的高维立方体中“切”了一刀，这两个数组表示的就是这个“高维立方体”的上下界。对于根节点，我们将其上下界设为$\pm MAX$，其大小为$10^7$(因为题目规定每一个向量坐标不会超过这一区域，所以MAX起到代替$\infty$的作用)

为每个结点设置上下界的目的是，在查找最近邻时，能通过查询结点到某个一个结点所处的空间立方体的距离，判断是否需要剪枝（query节中进一步介绍）

建立KD-Tree

原始结点被输入后存储在数组node中，我们用函数build(lp,rp,d0)递归地建立KD-Tree，对每一个递归实例：

  1. 将node数组中下标处于$[lp,rp]$之间的部分进行升序排序，排序依据是其第d0维的坐标大小
  2. 找到排序后区间内中位数的结点，用该结点的坐标来构造一个KD-Tree中的结点，并将该结点保存在kdtree[index]中
  3. 递归$[lp,rp]$的左半部分和右半部分（构造时需要判定左右区间是否为空，如果为空则不需要再为其建立子结点，此时其子结点下标指向0，也可视作空结点或垃圾结点），构造kdtree[index]的左右子树，同时更新其对应区域的上下界。

查找最近邻结点：

每次查找某个结点q的最近邻时，用min_len记录最短距离，首先在KD-Tree中不断深探找到“离q最近”的叶节点，但这个“离q最近”是打引号的，正如KD-Tree的区间查找算法一样，由于每个结点的具体位置并不确定，所以深探找到的叶节点未必就是真正离q最近的结点。此时需要自下而上班地回溯深探过程中经过的所有结点，对于每一个路径上的非叶结点，首先应判断此结点距离q是否更近并更新min_len。此外，如果该结点的另一棵子树可能存在一个距离q比当前最短距离更短的结点。则需要对另一棵子树进行搜索，重复此操作，直至回溯至根节点。

那么如何判定一个结点的另一棵子树是否可能存在距离q最近的结点呢？我们给出两种剪枝方法：

  1. 判断该结点对应的维度上，结点和q距离的平方是否小于min_len，实际上这一操作是求了q到这一边界的垂直距离，若小于，则需要搜索另一子树。
  2. 判断该结点另一个儿子对应的“高维立方体”p和q的距离，运算公式为$\Sigma_{i=0}^{d-1}(len(q,p,i))^2$，其中$len(q,p,i)$表示在第i维上q到高维立方体p的距离，显然当$q[i]\in[p.low_bond[i],p.up_bond[i]]$时，该维度的距离为0。若这一距离小于了min_len则有必要对其进行深探。

显然第一种剪枝方法是弱于第二种剪枝方法的，但程序中实际上同时用了两种剪枝方法，原因是计算多维距离的平方这一操作虽然能够跟多的剪枝，但计算本身却要花费比方法一更多的时间。因此，我们采用了先用方法一粗判剪枝，再用方法二进一步细判的方法，提高剪枝效率。

时间和空间复杂度的估算

时间复杂度

本题的时间消耗来自两步操作：建立KD-Tree和对KD-Tree的查找，下面分别对其进行分析。

建立KD-Tree的时间复杂度可以这样分析：考虑一颗满树，其深度为k的层有$2^k$个结点，也就对应在递归建立是要创建$2^k$个递归实例，对于每一个递归实例，其包含的区间长度为$len \leq \frac {n}{2^{k}}$，每一个递归实例中，时间复杂度主要来自区间排序，其复杂度为$O(lenlog(len))$而每一层总的时间复杂度应为$O(lenlog(len) \cdot 2^k) = O(n(logn-k)) k=1,2,… logn$。KD-Tree共有$logn$层，因此总的时间复杂度为$O(n(logn)^2)$。

对KD-Tree的每次查找，上网查询得知在点随机均匀分布的情况下其时间复杂度为$O(logn)$，但因为个人能力有限，无法对一般情况进行证明，下面仅在一个特别情况，即所有点都严格均匀分布的情况下证明其复杂度。

可以这样考虑，对KD-Tree的每次查找，首先要深探至叶节点，其复杂度为$O(logn)$，将整个d维空间平均划分为边长为$\frac{a}{n^{1/d}}$的n个d维立方体，由于每个向量分布是均匀的，因此每个立方体内仅存在结点，深探所确定的叶结点与目标结点q之间的的距离，应不大于d维立方体体对角线的长度$L = \sqrt d\cdot a\cdot n^{-1/d}$，因为高维球体体积不太方便计算，下面考虑以$2L$为边长，q为中心做高维立方体$M$，球真包含于该立方体中，任何在该立方体之外的高维立方体和q的距离应大于$L$，而根据此前对每个立方体内结点只有1个的条件，$M$内所包含的结点个数肯定不会超过$2^dd^{d/2}$，因此获取他们中长度最小值的时间复杂度为$O(2^dd^{d/2})$，由于$d\leq5$，可以认为这个复杂度是$O(1)$的

因此，对于q次查找，其时间复杂度为$O(q(logn))$

因此，总的时间复杂度为$O(n(logn)^2+qlogn) \ n \leq 10^5, q \leq 2 \cdot10^5 \ d\leq5, \ n \leq 10^5, q \leq 2 \cdot10^5$

空间复杂度

KD-Tree存储在数组kdtree中，每个结点的struct需要存储18个int，因此其空间消耗为$O(18n)$，原始结点存储在node数组中，其大小也为$O(5n)$，除此以外，建树的递归实例个数应等于kd树的结点个数，节点个数不大于2n，查询递归的递归实例个数应等于访问结点的个数，递归深度为$O(log(n))$。因此总的空间复杂度应该为$O(n+log(n)) = O(n)$

LAB2 HashFun Report

不同哈希策略的实现

“坏”哈希函数：将每个字符的ascii值相加求和后对N取模。

“好”哈希函数：将字符串根据ascii码值视作128进制数，将其转化为十进制后对N取模，和坏的哈希函数相比，这一函数能区分相同字符通过不同顺序组成的单词，因此更加均匀。

双向平方试探策略：先通过哈希函数为字符串确定一个初始值(init中实现)，然后以该位置为轴双向平方试探。在派生类中定义变量成员stride记录上一次试探步长，每次试探更新stride，并根据变化前后stride确定新位置。

1
2
3
4
5
6
7
8
9
10
11
12
int old_stride = stride;
    if (stride <= 0) {	//向右试探
        stride = -stride + 1; 
        int next = ((long long)old_stride * old_stride) % table_size;
        next = (next + (long long)stride * stride) % table_size;
        return (last_choice + next) % table_size;
    } else {	//向左试探
        stride = -stride;
        int next = ((long long)old_stride * old_stride) % table_size;
        next = (next + (long long)stride * stride) % table_size;
        return (last_choice - next + table_size) % table_size;
    }

公共溢出区策略：

原有table_size拿出一半设为缓冲溢出区，在hashtable构造函数中用向下转换判断冲突类型

1
2
3
4
overflow_probe* find = dynamic_cast<overflow_probe*>(my_collision);	//相下转换，如果成功则是公共溢出策略
if (find) {
    table_size =  size/2;
}

每次探测时，从table_size（溢出区起点）向后扫描

1
2
3
if (last_choice < table_size)
    return table_size;
return last_choice + 1;

测试数据

构造方法：从poj.txt中提取所有信息，对其使用random_shuffle混排取前in_num项。数据生成有三个参数：

  • in_num：插入的字符串数量，字符串选取方法见上
  • sear_num：询问次数，其中一半为成功查找，一半为失败查找，失败询问构造方法为“#_#”+存在的字符串，正确和失败查找交替出现
  • 第三个参数为1时，将插入的键值字符串按字典序升序排序，否则不排序

运行makedata.bat脚本可生成对应的数据

数据特征：（表大小为200023）

in_num sear_num 是否排序
0 10000 8000 否
1 10000 8000 是
2 100000 80000 否
  • 数据0和数据1相比，数据规模相同（但两次随机取，内容不完全一致），区别在于是否排序
  • 数据2和数据0相比，数据规模扩大了10倍

运行run.bat进行一组测试，运行的具体结果保存在result0,1,2三个文件夹下。

分析结果

  1. 无论规模如何，插入值排序与否，好哈希都明显提高程序性能（最好300倍），因为好哈希让散列更均匀，减少冲突次数，排序对运行效率无明显影响。
  2. 双向平放和线性试探相比，散列不均匀性能提升明显，均匀时无提升。可能是不均匀时，双向平方试探可迅速跳出聚集点。而散列均匀时，线性试探也能在附近迅速找到空位。
  3. 不均匀散列，开放和封闭效率大体相同，均匀散列，封闭表现明显更优。另外装填因子较大时，封闭散列明显更占优。公共溢出区策略在处理表的局部比较“满”，再插入少量数据的情况下，可能表现更好。
  4. 字符串本身不均匀，可能导致“好”哈希函数生成的散列也不均匀，冲突增多。
  5. 可以记录实时的装填因子，对不同哈希策略，实验确定装填因子为多大时扩容或者缩容，使性能最优。
#DSA
DSA PA3 REPORT
http://example.com/2023/01/16/DSA-PA3-REPORT/
作者
John Doe
发布于
2023年1月16日
许可协议