内含以下题目的实验报告:

  • CST2021F LAB1 Zuma
  • CST2021F LAB2 HashFun
  • CST2021F LAB3 BBST

这里不提供任何解题代码,仅将解题的白盒报告归档处理。

本博文仅做参考使用,任何可能影响您查重结果的行为请您后果自负!

Problem White Box (100%) Black Box (0%)
CST2021F LAB1 Zuma (100%) 97 [0]
Problem White Box (100%) Black Box (0%)
CST2021F LAB2 HashFun (100%) 98 [100]
Problem White Box (80%) Black Box (20%)
CST2021F LAB3 BBST (100%) 100 [100]

LAB1

01

  • 错误类型: Runtime Error
  • 错误原因: 访问 string a 时可能发生越界访问
  • 相应测例
    XYZ
    3
    0 X
    0 X
    0 X
  • 标准答案: XYZ\n
  • 构造思路
    • 在程序的 19 行 play(left - 1); 可能发生越界访问的情况(原因在于第 10 行 char color = a.at(rank); 直接对 rank 进行了访问).
    • 我们只需构造输入让 left 的值 0,也就是构造在字符串 a 的最左边进行一次消除的情况即可.

02

  • 错误类型: Runtime Error
  • 错误原因: 访问 string a 时可能发生越界访问
  • 相应测例
    
    3
    0 X
    0 X
    0 X
  • 标准答案: \n
  • 构造思路
    • 在程序的 23 行 play(left - 1); 可能发生越界访问的情况(原因在于第 10 行 char color = a.at(rank); 直接对 rank 进行了访问).
    • 我们只需让程序的 18 行字符串 a 的值在 erase() 后为空,此时的 next 值便会变成 0.
    • 在下次 play 时,便会尝试访问一个空串中的第 0 个元素.

03

  • 错误类型: Time Limit Exceeded
  • 错误原因: 算法效率过低
  • 相应测例
    ["QWER" x 65536 times]
    262144
    ["0 X\n0 Y\n" x 131072 times]
  • 标准答案: YXYX...(Trash)...QWER...(Trash)...QWER\n
  • 构造思路
    • 现算法时间复杂度为 $O(mn)$, 构造足够大的数据规模即可.

04

  • 错误类型: Wrong Answer
  • 错误原因: 在进行 while 寻找可消除元素串时对边界情况处理错误
  • 相应测例
    XYY
    1
    1 Y
  • 标准答案: X\n
  • 构造思路
    • 在程序的 12 行 while (left > 0 && a.at(left) == color) --left; 中, 最终 a.at(left) 的值不一定为 color.
    • 而最终却通过 erase 将该值删除.
    • 构造含有消除的输入即可.

05

  • 错误类型: Wrong Answer
  • 错误原因: 没有考虑初始序列为空行的情况
  • 相应测例
    
    1
    0 X
  • 标准答案: X\n
  • 构造思路
    • 构造初始序列为空行即可.

06

  • 错误类型: Wrong Answer
  • 错误原因: 没有考虑到插入分块数组时,块过长的情况
  • 相应测例
    XYXY["XY" x 1020 times]XYM
    2050
    0 Y
    0 X
    0 Y
    0 X
    ["0 Y\n0 X\n" x 1021 times]
    0 Y
    0 X
    0 Y
    0 X
  • 标准答案: 以 M 结尾
  • 构造思路
    • 构造某个块过长,使得在 memmove 时覆盖掉后面数组中的 M 即可.

07

  • 错误类型: Wrong Answer
  • 错误原因: 在向左计算需要消除的区间时,对长度为 0 的分块未有效过滤
  • 相应测例
    QWER["QWER" x 510 times]QWMXXYYX["XYYX" x 510 times]XYYXXM
    2
    3072 X
    2048 M
  • 标准答案: QWERQWER...(Trash)...QW
  • 构造思路
    • 构造需要将其中一个分块完全清除的连消输入.
    • 输入为 $[QWER…QWERQWMX][XYYX…XYYX][XM]$
      • 在中间分块的中间位置首先执行一次连消,中间区块的长度被置为 0.
      • 程序在之后插入 M,寻找可消除区块时,l.first 便无法成功查询到目标位置,导致答案错误的出现.

08

  • 错误类型: Wrong Answer
  • 错误原因: 没有考虑连消
  • 相应测例
    XXYYZZYYXX
    1
    4 Z
  • 标准答案: \n
  • 构造思路
    • 构造连消输入即可.

09

  • 错误类型: Runtime Error
  • 错误原因: 在执行消除时没有对 l, r 出现在同一个分块数组的情况进行特判而导致异常
  • 相应测例
    XYZXYZMMXYZXYZ
    1
    6 M
  • 标准答案: XYZXYZXYZXYZ\n
  • 构造思路
    • 代码的 132 行,135 行对 len 的赋值,在l, r 出现在同一个分块数组的情况会出现负数.
    • 构造执行消除时 l, r 出现在同一个分块数组的情况即可.

10

  • 错误类型: Wrong Answer
  • 错误原因: 在执行跨分块消除时,误将 plen[l.first] 设为 0
  • 相应测例
    XY["XY" x 1022 times]XYYM
    1
    2048 Y
  • 标准答案: 以 M 结尾
  • 构造思路
    • 代码消除连珠后,在对中间分块的区间长度置 0 时,for (int i = l.first; i < r.first; i++) 会误将 plen[l.first] 设为 0.
    • 构造跨分块消除的情况,注意构造 M 使得在 p2a() 拷贝时 M 覆盖掉 a 的首元素.
      • 输入为 $[XYXYXY…XYXY][YM]$.
      • 连消后 plen[0] 被置 0,再发生 p2a() 拷贝时 M 便会覆盖掉 a 的首元素.

LAB2

Hashing Strategies

[hashing_ascii]

即字符串 aaaabbbbcd 会被分割为 aaaa, bbbb, cd\0\0 考虑,分别找出其 32bit 的表示后求和。(对 $TableSize$ 取模的意义下)

[hashing_utf8]

哒a 被考虑为 哒\0a\0\0\0。即考虑字符串中的每个 utf-8 字符,将其延拓为 32bit 表示后求和。(对 $TableSize$ 取模的意义下)

[quad_probe]

quad_probe 有成员函数 getOffset() 建立 $(-1,0,1,2,3,4,5,6\cdots)$ 到 $(0,0,1,-1,4,-4,9,-9\cdots)$ 的映射,成员变量 lastIndex 记录当前的 offset-index,在 init() 类对象的时候将 lastIndex 置为 $-1$​​​,之后每次解决冲突都将 lastIndex 自增,在对 $TableSize$ 取模的意义下返回 last_choice + getOffset(lastIndex) - getOffset(lastIndex-1)

[public_overflow]

对 collision_strategy 增加虚函数 get_max_hashing_volume 获得非溢出区的长度,默认返回 $TableSize$,并修改 *my_hashing 调用时传入该函数的返回值。public_overflow 对该函数重写,返回最大表长的 $4/5$。

在解决 overflow 问题的时候,若 last_choice 不在缓冲区中,则返回缓冲区的第一个位置;不然返回下一个邻近的位置。

Testing Cases

测例名 数据来源 插入 查询 Collision Factor
1-ascii-standard poj 30k 90k 20
2-utf8-standard hdu 30k 90k 20
3-ascii-collision poj 30k 90k 100
4-utf8-collision hdu 30k 90k 100
5-ascii-large poj 100k 300k 20
6-utf8-large hdu 100k 300k 20

测例构造方法

首先将所有数据读入,并维护一个 hashTable 来进行 key 去重的操作。这个 hashTable 使用的 hash 策略根据数据来源,分别使用 hashing-ascii 和 hashing-utf8,这是为了保证可以构造高冲突率的样例。在将数据读入时,我们为每条数据赋予一个 uniqueId,计算公式为:

这个计算公式可以保证,在 CollisionFactor 较小时,数据的 uniqueId 由随机值决定;而在冲突因子较大时,hash 值相近的数据最终 uniqueId 相近。最终我们按照 uniqueId 将读入的顺序进行排序。

然后我们均匀选择插入与查询操作,插入即将排序后的条目的最后一个移入待查询队列中;查询有 75% 的概率从待查询队列随机选取一个,25% 概率查询条目队列的最后一个并将其丢弃。

Result

  1. 使用 hashing-ascii 处理 utf-8 字符串的性能比使用 hashing-utf8 的性能差。这是因为 hashing-ascii 没有充分考虑 utf-8 字符串的组成结构,导致散列后的关键码分布不均匀。
  2. 双向平方探测的性能显著优于线性试探,这是因为一旦发生散列冲突,前者可以快速跳离冲突区域。
  3. 闭散列在性能上更占优势。当冲突的元素个数 $k \le TableSize$ 时,不需要进行 $O(TableSize)$ 的试探链探测,只需要 $O(k)$ 的溢出区查找。
  4. 这可能会导致散列后的散列码分布并不均匀,因而可能导致局部的聚集性,进而造成散列表操作效率的下降。

[Input Data] a-z0-9 上长度为 5 的串的集合 $S$​。

[Representation] $h :=(0,\cdots,9,a,\cdots,z) \rightarrow (0,\cdots,9,10,\cdots, 35)$​​​​​, $f(w) := \sum _{i=1}^n h(w_i)*36^{i-1}$​​​​。

[Operation] 使用长度为 $O(|S|)$​ 的向量 $V$,$Rank(w)=f(w)$,$V_w = Rank(w)$。

LAB3

Data Structures

实验中实现了AVL 树Splay 树红黑树三种数据结构,接下来做简单介绍与复杂度分析。数据结构的构思部分参考了《数据结构》课堂讲义第八章和第十章的内容。

BBST

这是一个接口(抽象基类)。本实验用到的三种数据结构均由 BBST 派生。具体来说,它提供了以下虚方法:

  • find(const T& e)
  • insert(const T& e)
  • remove(const T& e)

AVL 树

AVL 树实现了一种渐进平衡,其定义一个结点的平衡因子为左孩子与右孩子的高度差。其渐进平衡的条件为每个结点的平衡因子绝对值不超过 1。可以证明,在这样的渐进平衡意义下,树高 $h=O(\log_2n)$。

AVL 树的查找调用了与标准 BST 类似的接口,不过增设了 _find 指针记录上一个结点 $T$ 的地址,其中结点 $T$ 满足 $data(T) \le e$ 的题设条件。最终的查找结果便是 _find 指针对应的结点。

AVL 树的插入和删除涉及到平衡因子被破坏后的恢复操作。具体来说,是对失衡结点 $g$,及其较高的孩子 $p$,以及较高的孩子的较高的孩子 $v$ 执行 3+4 重构,保持中序遍历单调增原则的不变性。对于插入操作可以证明这样的修正是一蹴而就的,修正后局部子树的高度恢复,平衡因子的改变影响无需上传至树根。而删除操作在修正后,产生的失衡影响可能继续上传,一直到树根。

也因此我们可以分析得出,一颗结点数为 $n$ 的 AVL 树的空间复杂度为 $O(n)$,时间复杂度分析如下:

单次查找时间复杂度为 $O(h) = O(\log n)$,插入删除操作最坏情况均为 $O(\log n)$。而单次插入操作引起的拓扑结构变化量为 $O(1)$,单次删除操作引起的拓扑结构变化量为 $O(\log n)$。

Splay 树

伸展树使用双层伸展策略,思想主要是充分利用数据访问的局部性,具体来说:

  • 刚被访问过的结点,极有可能很快地再次被访问
  • 下一次将要访问的结点,极有可能就在刚被访问过的结点的附近

于是就模仿自适应链表的想法,一旦结点被访问,便通过旋转将其推送至树根。而这旋转是使用双层伸展策略,即每次旋转考察祖孙三代,对其做 3+4 重构。事实证明这有利于树高的减小。

Splay 树的查找调用了与标准 BST 类似的接口,不过增设了 _find 指针记录上一个结点 $T$ 的地址,其中结点 $T$ 满足 $data(T) \le e$ 的题设条件。最终的查找结果便是 _find 指针对应的结点。此外,在结点查找结束后,最终被查找到的结点会被旋转推送至根。

Splay 树的插入和删除依赖于其查找操作。不管是插入,还是删除,在此之前都会执行一次查找操作。对于插入操作来说,带插入节点的直接前驱/后继已经在这时推送至根,我们只需在根部做简单的拓扑结构改变便可将新结点接入。而对于删除操作来说,待删除结点已经在这时被推送至根。我们只需要在其其中一棵子树中寻找其直接后继,然后将其推送至该子树的根部,然后将两颗子树重新拼接起来即可。

于是我们可以分析得出,一颗结点数为 $n$ 的 Splay 树的空间复杂度为 $O(n)$,时间复杂度分析如下:

单次查找最坏时间复杂度为 $O(h) = O(n)$,而分摊复杂度为 $O(\log n)$;插入删除操作由于调用了查找接口,最坏情况均为 $O(n)$,但分摊复杂度均为 $O(\log n)$。单次插入删除操作引起的拓扑结构变化量均为 $O(\log n)$。而当我们进行连续的 $m$ 次查找,满足 $k \ll n \ll m$ 时,整体的时间复杂度仅为 $O(m\log k+n \log n)$。也就是说,针对局部性的数据访问,Splay 树有其独特的优势。

红黑树

红黑树是一种适度平衡树,其满足以下条件:

  1. 树根必为黑色。
  2. 外部结点必为黑色。
  3. 红结点只能有黑孩子和黑父亲。
  4. 外部结点的黑深度相等,或全树的黑深度相等。

事实上,红黑树的性质与 (2,4)-B 树有密不可分的联系,在这里我们不多详细介绍。值得注意的是,适度平衡的红黑树虽然平衡条件没有 AVL 树严格,但是可以证明其高度 $h = O(\log n)$。

红黑树的查找调用了与标准 BST 类似的接口,不过增设了 _find 指针记录上一个结点 $T$ 的地址,其中结点 $T$ 满足 $data(T) \le e$ 的题设条件。最终的查找结果便是 _find 指针对应的结点。

红黑树的插入和删除需要处理插入时上溢(双红修正)和下溢(双黑修正)两种特殊情况。二者均可以类比 B 树中结点上溢和下溢的操作来处理,然后将 B 树的处理结果通过重染色和旋转两种方式体现回红黑树中。而不管是插入还是删除的哪种情况,针对拓扑结构改变而言,我们均最多做常数次旋转便可以将其恢复为符合红黑树规则的 BST。

也因此我们可以分析得出,一颗结点数为 $n$ 的红黑树的空间复杂度为 $O(n)$,时间复杂度分析如下:

单次查找时间复杂度为 $O(h) = O(\log n)$,插入删除操作最坏情况均为 $O(\log n)$。而单次插入和删除操作引起的拓扑结构变化量均为 $O(1)$。

Test Cases

实验使用 Python 写了自动化的测试工程,只需使用 python3 main.py 即可运行输出测试结果。我们在报告的根目录留了一份 result.log,为使用 Ubuntu-20.04 LTS, AMD Ryzen 5 4600H (3.00 GHz), 8GM RAM 的运行结果。

项目目录解释如下:

|- main.py  测试程序主入口
|- cases  测试样例生成器
    |- case1_rand.py
    |- case2_sorted.py
    |- case3_query.py
    |- case4_modification.py
|- utils
    |- judger.py  Judger
|- testdata  样例生成器的生成结果 // Very large. Maybe 600MB+!

Case 1: Random

实验的第一组为随机数据。数据量分为 $100K$,$1M$,$5M$,$10M$ 四种情况。

具体来说,测例生成的流程如下:

  • 随机在 $[1, 1M]$ 中均匀选择关键字 key
  • 如果 key 不在树中,执行插入操作;不然有 70% 的概率对 key 执行一次查找,30% 的概率执行一次删除。

这样可以首先保证树中有足够多的数据,后续操作不至因树中结点规模 $n$ 过小而导致性能无法区分;此外可知 $p_{query}$,$p_{insertion}$,$p_{removal}$ 三者的极限均收敛,实证证明三者的比例分别约为 $0.5, 0.3, 0.2$。

Case 2: Sorted

实验的第二组为顺序插入数据。数据量分为 $100K$,$1M$,$5M$,$10M$ 四种情况。

具体来说,测例生成的流程如下:

  • 对于 $[1, n]$ 之间的所有关键码 key,顺序插入 key

有序数据是现实中较为特殊的一种情况。同时,这样数据的插入也在一定程度上具有局部性,即每次要插入的结点都是上一次插入的结点的直接后继。此外,这组数据也可以反映出树的动态操作次数。

Case 3: Query with locality

实验的第三组为大量查询具有局部性特征的数据。数据量分为 $100K$,$1M$,$5M$,$10M$ 四种情况。

具体来说,测例生成的流程如下:

  • 向树中插入规模为 $n * 0.5\%$ 的随机结点;
  • 剩下的次数均用于查询最后被插入的结点。

这既能反映 AVL 树和红黑树面对大量查询时的表现性能,从而间接反映出树高的情况,同时由于查询带有局部性,可以更好地体现 Splay 树具有的局部性查询的特征。

Case 4: Modification

实验的第四组为大量插入和删除数据。数据量分为 $100K$,$1M$,$5M$,$10M$ 四种情况。

具体来说,测例生成的流程如下:

  • 随机在 $[1, 1M]$ 中均匀选择关键字 key
  • 如果 key 在树中,执行插入操作;不然执行删除操作。

这样可以首先保证树中有足够多的数据,后续操作不至因树中结点规模 $n$ 过小而导致性能无法区分;此外这样可以测试数据结构在面对大量的增删操作时的运作性能。

Analysis

我们在计算机无其他任务运行时使用上述的配置共计运行了 5 次实验并取平均值。其中“运行时间”的定义为 Python 的 subprocess 开始运行与停止运行的时间,旋转次数定义为 zig, zag, 或是 3+4 重构总的调用次数。下面我们逐测例分析:

Case 1

数据结构/运行时间(s) 100 K 1M 5M 10M
AVL 0.45 1.14 5.14 10.50
Splay 0.47 2.10 11.00 > 15.00
RedBlack 0.51 1.05 5.03 9.25
数据结构/旋转次数 100 K 1M 5M 10M
AVL 45K 0.32M 0.95M 1.5M
Splay 1.2M 15M 79M - TLE -
RedBlack 39K 0.27M 0.8M 1.4M

在随机数据上的表现红黑树最好,伸展树最差。伸展树由于其单次插入,删除和查询都需要将目标结点通过旋转推送至根,而我们的数据输入十分具有随机性,因此平均每次增删查都需要 $O(\log n)$ 的时间将目标结点推送至根,因此在时间复杂度上逊于另外两者。而 AVL 树与红黑树二者的表现不相伯仲,但红黑树的动态操作数明显小于 AVL 树,这是由于其动态操作拓扑结构的变化量都是常数级别的。

Case 2

数据结构/运行时间(s) 100 K 1M 5M 10M
AVL 0.49 0.62 1.30 2.16
Splay 0.50 0.54 0.98 1.72
RedBlack 0.50 0.66 1.50 2.66
数据结构/旋转次数 100 K 1M 5M 10M
AVL 100K 1M 5M 10M
Splay 0 0 0 0
RedBlack 100K 1M 5M 10M

Splay 树在这组数据上表现的最好,这是因为插入的数据具有局部性,每次插入的数据的直接前驱是上一次插入的数据,这样可以让 Splay 树仅仅在根部做嫁接即可,无需旋转操作,单次操作也只需要常数级别。而 AVL 树在这组数据上的动态操作表现与红黑树近似,这是因为只有插入操作,二者均可在 $O(1)$ 的动态操作次数内完成。

Case 3

数据结构/运行时间(s) 100 K 1M 5M 10M
AVL 0.52 0.67 1.40 2.00
Splay 0.50 0.66 1.39 3.12
RedBlack 0.51 0.67 1.44 3.20
数据结构/旋转次数 100 K 1M 5M 10M
AVL 0.2K 2.3K 11K 23K
Splay 3K 44K 280K 610K
RedBlack 0.2K 1.9K 9.7K 19K

在小批量插入随机数据,大批量查询局部数据的过程中我们可以得出结论:

  • Splay 树针对局部数据的查询有其独到之处,具体来说,在 1M 和 5M 的实验中,即使其有十分缓慢的插入速度,其综合性能仍然优于其他两者;而在 10 M 的实验中,其查询带来的性能提升终究没有低过随机插入带来的严重性能浪费(这点由其动态操作的次数便可看出)。
  • 而同时值得我们注意的是,AVL 树和红黑树在面对大规模的数据查询时所表现出的不同。AVL 树面对大规模的数据查询时性能明显优于红黑树,这是由于其较为严格的平衡条件保证了其在结点规模相等的情况下,树高低于红黑树,因而查找的平均长度低。

Case 4

数据结构/运行时间(s) 100 K 1M 5M 10M
AVL 0.54 1.28 5.30 10.45
Splay 0.53 2.02 10.30 > 15.00
RedBlack 0.51 1.16 4.89 9.89
数据结构/旋转次数 100 K 1M 5M 10M
AVL 44K 375K 1.6M 3.1M
Splay 1.3M 16.4M 88M - TLE -
RedBlack 37K 326K 1.4M 2.8M

在涉及到大规模的数据插入与删除的时候,因为每次插入和删除都要大批量旋转的伸展树自然是喜提 TLE。而我们得到的结论是,红黑树在大规模的增删操作是优于 AVL 树的,这恰恰也是因为红黑树对于渐进平衡的要求并没有 AVL 树严格,同时红黑树删除操作所涉及的动态操作数目少于 AVL 树的缘故。

Conclusion

  1. 在进行大规模查找时,AVL 树比红黑树更优。因为它的平衡条件更严格,平均树高更低,也因此适用于数据库等需要快速查找的场合。
  2. 红黑树的大规模插入与删除操作优于 AVL 树,既可以有效减少拓扑结构的更改次数,且分摊时间成本也较低。红黑树也因此被广泛用于各种编程语言提供的标准数据结构中。
  3. 当问题访问的数据具有局部性时,Splay 树的可以大大提升性能,甚至在某些情况下会超过 AVL 树和红黑树的性能。因此当要处理的问题数据具有明显的局部性特征,应选用 Splay 树。

Reference

[1] Pfaff B. Performance analysis of BSTs in system software[J]. ACM SIGMETRICS Performance Evaluation Review, 2004, 32(1): 410-411.

[2] Štrbac-Savić S, Tomašević M. Comparative performance evaluation of the AVL and red-black trees[C]//Proceedings of the Fifth Balkan Conference in Informatics. 2012: 14-19.