一周技术学习笔记(第83期)-时间和空间到底哪一个更经济

这篇文字讲述时间和空间，但肯定不是去理解牛顿的绝对时空观，也不会去理解爱因斯坦狭义相对论的理论。

我们今天说的是，程序世界的两句话 “时间换空间，空间换时间”，这两句词语在我们的工作中经常会被提及。

那么这中间的【换】我的理解是“被动的牺牲，然后再去争取”，有点置之死地而后生的气魄。

比如牺牲时间，多“浪费”一些时间换取空间的延伸；牺牲空间，多“浪费”一些空间节省时间上的消耗。

空间换时间

空间换时间，比如增加数据库的索引提高查询性能，为数据库表的列字段增加索引就会占用一定的物理空间，如果是创建聚族索引还会需要更多的空间。

再比如利用缓存，数据库里面本来有一份却要再另外申请缓存空间，将耗时的操作放入到remote缓存或者内存中也可以提升性能。

这些都是空间换时间的例子，无论是索引还是缓存都额外增加了存储空间，然后换来查询性能的提升，查询的耗时减少了。

时间换空间

时间换空间，比如分页查询显示，本来可以一次查询数千条记录一次显示出来，但这样如果每条数据字节过大，会对应用程序内存造成威胁。

这个时候，就可以牺牲时间，本来可以一次全部看完，我们却一页数十条或者百条记录，分成好几次展示给最终用户。

再比如，按照一定规则对要处理的数据进行加密算法处理，然后将加密的数据直接返回给用户，这中间增加了加密的时间开销。

程序运行中的时间和空间

时间，代表的是性能，空间，代表的是存储。

我们日常的程序运行中总是跟这两块分不开的。程序被编译好一开始就存于磁盘，运行时继而被加入内存，都用到了空间。

CPU从内存读取程序和将结果写入内存，此时过程中更是关注读写的性能，读取磁盘也是。如下图所示。

上图选自《架构修炼之道》第一章

算法的时间复杂度

在计算一个算法的时间复杂度的时候，可以通过总的执行次数T(n)是关于问题规模n的函数来表示。

通过分析T(n)随n的变化情况确定T(n)的数量级。因此，算法的时间复杂度，也可以用公式 T(n)= O(f(n)) 来表示。

代表着随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。f(n)是问题规模n的某个函数。

算法的空间复杂度

我们写一个算法来判断某年是不是闰年，老土的办法就是我通过程序开辟一个好多年数值大小的数组，比如2080个元素的数组。

随后我们对所有的年份下标的数字做对应，如果是闰年，年份下标对应的数组元素的值就是1，否则是0。

这样我们通过索引的方式能很快获取输入的年份是否闰年。

当然，上述方法是利用了增加数组空间存储的方式。

如果不这样做，就需要我们写那么一个算法，当程序接收到一个年份的时候，就可以通过这个算法计算出所给年份是否是闰年。

当然，这样做就要耗费CPU计算性能。到底采取哪一种，就需要看使用这种增加空间的开销能否足够换来减小计算时间的开销了。

算法的空间复杂度计算公式为，S(n)=O(f(n))，其中，n是问题的规模，f(n)是这个公式关于n所占存储空间的函数。

摩尔定律

上面提到的时间，多指性能的成分偏多，或者说就是纯粹的性能。

现在要说的时间就是偏向纯粹的时间一面了。摩尔定律讲的是集成电路上可容纳的元器件数目，大约每隔18-24个月便会增加一倍，性能也会提升一倍。

那么，有了这个定义，此时的时间和性能又对应上了。只不过他们之间不像上面提到时间和空间那样有交换关系，这里没有交换关系。

起初的时候电脑的CPU都是单核，各大厂商都是拼CPU的频率，多少多少赫兹。随着这种技术发展遇到了瓶颈，于是大家开始横向扩展，拼CPU的核数，多少多少核。

这是不是也是一种空间换时间呢，核数增加了势必要积压原本狭小的计算内部硬件空间，但同时确实换来了计算机整体计算性能的提升。

时间、空间的跨越发展

在2000年初我们访问一个页面，我们可以一直等，直到页面有内容返回，呈现在我们面前。如今，我们访问一个网站，使用一个APP，如果超过2S，甚至1S没有内容返回，我们都会有放弃继续使用的冲动。

在2000年初我们写一个程序要存储到一张只有几KB的软盘里面，当时的学生上下计算机课都随身携带。如今，我们不仅可以在本机存储几TB的数据，而且我们还可以申请到上百G的云存储空间。

回到代码

返回到代码层面，我们再来看一个空间和时间交换的两段程序代码，我们大学时代上C语言课程的时候，常用的例子。

下面两段程序的目的都是让都整形数值的a和b做个交换，但却分别是牺牲了空间和牺牲了时间。

程序片段-1

void swap(int a, int b)
{
int c;
 c=a;
 a=b;
 b=c;
}

在这段程序里面，我们新开辟了一块空间c，然后我们利用这个新开辟的空间，做了三次赋值运算，最终的结果是a和b的值之间互换。

程序片段-2

void swap(int a, int b)
{
a=a+b;
 b=a-b;
 a=a-b;
}

在这段程序里面，我们就没有新创建任何的空间，那是怎么做的呢，我们分别做了三次加减运算和三次赋值运算，最终将a和b的值互换。

显然第2段程序运算要比第1段程序复杂，计算耗时肯定也要比新开辟空间多。

那么程序片段-1是用空间换了时间，程序片段-2是用时间换了空间。

程序片段-1时间效率就比较高，空间效率低；程序片段-2时间效率低，空间效率高。

写在最后

这样看，作为一名程序员，我们经常跟时空打交道，从常见的应用场景到摩尔定律的规则，再到考虑一段程序设计，我们往往都要在时空间取一个平衡。

因为，时间上的性能考虑和空间上的利用是我们每次设计程序以及程序将来运行在生产环境下，都是我们要重点对待的两件事情。

----END----

这里记录，我每周碰到的，或想到的，引起触动，或感动的，事物的思考及笔记。不见得都对，但开始思考记录总是好的。