浅谈空间利用效率优化（一个简单易懂的优化空间教程）

· · 个人记录

背景：

现在的比赛，大多空间都很大。由于很容易TLE（时间不够），所以大多数都是空间换时间。

↑讨厌的TLE↑

但是，（由于本人沉浸于空间换时间不能自拔）本人在比赛时，曾经经常MLE。

所以本文就要反其道而行之，讨论如何用少量时间换大量空间的一本万利的简单方法。

在比赛中，本人在本机端经常用大量的空间换时间，于是经常mle。下面我就讲一下我在比赛过程中各种节省空间的经历。

正文

1.空间利用最大化

（删掉多余变量，有时候MLE就差一个变量的大小）←这个大家应该都干(^_^)

停止胡说八道，开始正经的。

举个例子：现在我要表示一堆关于一个人的数据。

如果按普通存储，会存储：姓名，出生地（省，区），出生日期，性别。

这样存储需要大量空间，需要开一个二十几位的字符串来存储。

让我们看到身份证反面。

我们可以看到上面有一行数字。

身份证↓

[手动滑稽]

身份证号↓（以上海2000年1月1日出生的人为例）

3 1 0 1 1 5 2 0 0 0 0 1 0 1 0 1 1 m*

*m指验证位，因为笔者不知如何计算

这些数字，包含了上文提到的几乎所有信息，只有18位，节省了使用字符串的大量空间。

所以，我们在输入和输出时，可以使用O（1）的时间来适当处理数据，这样就能使数据存储空间更小，而且更便于处理。

再举个用少量时间换大量空间的例子：

现在输入一个等差数列，有很多位数字，需要知道某一位的值和总和等。

如果直接开数组处理，查找时间是O(1)，求和时间是O（n）；

如果用4位数组（首项，末项，项数，公差）来存储，查找时可以直接计算，时间大约O(1)；求和时间也只有O(N)。

这样省下的大量空间可以用来进一步省下更多时间。

还有一个小小的建议：

大家好多题目都是用的队列吧。

队列有一个缺点：出队后队前会有空位，会造成假上溢（队前有空位但队后没有，导致假的溢出）。

对于这种情况，可以使用循环队列解决，省下大量空间。

假上溢:

head tail
a b s x
head tail
b s x
head tail
b s x y

此时队尾已经没有空间了，但是队伍里还是有空间的，所以称为假上溢。

解决方法：循环队列

即：最后一个位置在第一个位置前面，循环使用。

这样做可以省下大量空间，不需要开太长的队列。

2.时间换空间

上面讲了用少量时间换大量空间的方法，下面讲一个时间空间相平衡的方法。

这个方法就是：著名的Hash表。

hash表使用模来存储，即取一个数，数据存储在数据mod这个数的位置，如果这个位置被占用就到下一个。

↓HASH表储存一些3的倍数（以模7为例）↓

数：9 15 18 21 24 17 33

1 2 3 4 5 6 7(0)
15 9 24 18 33 27 21

使用Hash表时，使用的时间是O（n）（存储时间，查询时间），但是大大减少了空间使用量，值得使用。

综上，在使用空间换时间时，不妨使数据更易于处理，节省一些空间，避免出现笔者的MLE情况,同时也可以用节省的大量空间来节省更多的时间。

希望我的方法可以给大家一些帮助，救回大家因换时间而摇摇欲坠的空间。

最后，祝大家CCF顺利通过，拿到一等奖！