先聊一聊文章的标题,标题已然表明了这是一篇计算机方面的博文,这是毫无疑问的了. 然而,紧跟着映入眼帘的‘妥协’二字却颇让人费解. 何谓妥协?字典里给出的解释是：妥协—— 以让步的方式避免冲突与争执.诚然，字典给出的解释是不会有误的. 解决了这个问题,又有另一个摆在我们面前,它又向谁妥协呢?计算机当然不会像人一样卑躬屈膝,它是不会向人妥协的. 不是人,又是谁呢?不急,不急，往下看,容我慢慢道来.
我先问一个问题：”储存器”和”内存”有什么区别?自然,计算机方面专业的学生都能够回答这个问题,”计算机的储存结构粗略的可分为三层,自顶向下分别是:高速缓存器、主储存器、辅助储存器,自顶向下价格和访问速度依次….”
储存层次结构
这里,我需要指出的是: 计算机的层次结构是与生俱来的,这种结构的底层是晶体管,其顶层则是计算机显示器上所显现的信息. 因此,我们常常能够在计算机中看见这种层次的结构,然而正是因为”层次结构”计算机不得不做出本文中的”第一次妥协”….
我们找不到一个”有大又快”的储存媒介,但我们却又不想花费高昂的代价去访问主存以获得数据.我们在主存与 CPU 之间,设置了”高速缓冲存储器”来满足我们”过分”的要求.
南亚nt5cb256m16bp-di ddr3高速缓存芯片
我们不能找到一个完美的解决方案来满足我们的要求,所以计算机做出了”妥协”.
高速缓存器的使用使得我们能花费较低的代价获得数据. 但,我们还是渐渐的发现,即使我们做出了妥协,需求任不能被完全的满足,我们有时还是不得不花费高昂的代价访问内存以获得我们”梦寐以求的数据”.
我们为此付出了一些东西,但我们往往会发现:我们失去的比我们预想的要多的多.
如同大国之间的政治谈判一样,在谈判桌上,我们妥协了,但”对手”却依旧咄咄逼人.
俾斯麦以西班牙王位继承问题制造争端逼迫法国宣战.
同样的情况,还出现在”数据结构与算法”这个领域.通过下面的例子,我们将看见,即使是在最简单的数据结构身上,为了实现一丁点需求,我们也不得不为此付出很多.
在计算机中维护线性表,最简单,最自然的方式,就是把表项存放在连续的位置,一个结点紧挨着另一个节点,正如你所知道的一样,这种分配方式,被冠上了一个华丽华丽的名字 —— 顺序分配.
这是一个数组
因为基地址的存在,通过简单的加法运算,我们便能够在常数时间内访问到线性表中的任一元素.
一切看起来很美好,直到我们尝试在第一个节点与第二个节点之间插入一个元素.这时,我们发现我们几乎要把整个数组向后移动一个单元.
为了一个结点,我们却要移动整个数组,这样巨大的代价是我们难以接受的.
与链接分配相对应的是链接分配.
链表
这一次,我们能够在常数时间内在任意位置插入一个节点,但,此时的我们已经不能在单位时间内访问任意的结点了. 但,还远远不仅如此,为了我们能以在常数时间的代价插入一个节点,我们不得不为此多花费上一倍的空间.
我们为了能节约时间而妥协,但我们却在空间上付出了高昂的代价,我们为此付出了太多了.
在计算机这个世界中,两全其美总是如同不存在一般,我们总是在为了得到一些东西的同时,失去了更多的东西.我们在跟一位顽固的”外交官”谈判着,但往往我们的妥协,只会让我们失去更多.