vector速度测试

vector速度测试 _ANIG_ · 2024-04-22 20:44:02 · 个人记录 vector 的 insert 和 erase 操作理论复杂度为 O(n)，但是实测速度非常快，甚至可以超过平衡树，线

vector速度测试

_ANIG_

·

2024-04-22 20:44:02

·

个人记录

vector 的 insert 和 erase 操作理论复杂度为 O(n)，但是实测速度非常快，甚至可以超过平衡树，线段树等 O(\log n) 的数据结构。

下面是各种情况下 vector 和平衡树(set)的速度对比。（所有数都为 long long）

测试点编号

vector

set

Subtask1

532ms

31ms

Subtask2

60165ms

687ms

Subtask3

1090ms

31ms

Subtask4

124ms

46ms

Subtask5

1305ms

15ms

Subtask1：随机插入 10^5 个数。

Subtask2：随机插入 10^6 个数。

Subtask3：在头部插入 10^5 个数。

Subtask4：随机插入，查询 10^5 个数。

Subtask5：随机删除 10^5 个元素。

可见，如果只有插入，删除，查询等简单的 set 能维护的操作，vector 的速度不及 set。但是其速度在操作数为 10^5 数量级时是可以接受的。

vector 更优秀的地方，是它能维护一些更复杂的操作，而这些操作可能是 set 难以维护的。

下面是 vector 在进行一些复杂操作时与手动实现的平衡树的速度对比。（所有数都为 int）

测试点编号

vector

Splay

Subtask1

78ms

62ms

Subtask2

375ms

419ms

Subtask1：10^5 次插入，随机访问。

Subtask2：普通平衡树模板。

vector 在维护复杂操作时，速度已经几乎与手写平衡树相当。

可见，如果出题人不卡，vector 几乎就是一个常数小，好写的平衡树。