企业网站建设 南通,邢台网络推广,新沂微网站开发,网页美工设计培训学什么目录 一、顺序表和链表的区别#xff08;其他链表存在缺陷#xff0c;比较意义不大#xff0c;这里用带头双向循环链表与顺序表进行比较#xff09;
1.1插入、扩容与随机访问
二、缓存利用率的比较
2.1前置知识
详解及补充知识#xff08;本文仅为比较顺序表及链表其他链表存在缺陷比较意义不大这里用带头双向循环链表与顺序表进行比较
1.1插入、扩容与随机访问
二、缓存利用率的比较
2.1前置知识
详解及补充知识本文仅为比较顺序表及链表相关缓存与知识可以看下文 一、顺序表和链表的区别其他链表存在缺陷比较意义不大这里用带头双向循环链表与顺序表进行比较
不同点顺序表链表带头双向循环存储空间上物理上一定连续逻辑上连续但物理上不一定连 续随机访问用下标随机访问支持O(1)不支持O(N)任意位置插入或者删除元 素可能需要搬移元素效率低O(N)只需修改指针指向插入动态顺序表空间不够时需要扩 容没有容量的概念应用场景元素高效存储频繁访问任意位置插入和删除频繁缓存利用率高低 1.1插入、扩容与随机访问
首先链表的如果知道要插入的位置我们可以修改前后节点的指针直接插入数据不需要挪动其他数据非常方便。而顺序表我们如果在数据间插入数据就要将其他数据前移或后移。可能会出现为了插入一个数据而挪动原先所有数据的情况成本较大。
其次链表的本身没有容量的概念节点都是按需申请的不需要考虑扩容的问题。
这方面扩容本身就有很大的消耗。使用realloc扩容主要会有原地扩容和异地扩容两种情况。 如果要扩的空间不大在已有空间接下来的地址够用或者可用就会使用接下来的地址扩大原空间这个过程原空间地址不变只是单纯申请空间扩大。一但接下来的空间不可用或者不够realloc就会另寻一块足够大的可用地址申请空间地址改变之后将原空间中数据复制过来并释放原空间。显而易见的异地扩容的消耗较大。 此外扩容还会存在的一个问题是存在空间浪费比如一般来说我们原空间容量是100现在需要插入5个新元素我们一般将原空间扩大两倍但是可能我们只会插入5个数据这就会浪费95个空间。
需要注意的是扩容存在的两个问题还是相互影响的我们一般按照二倍扩容其实是通过概率学计算希望减少扩容次数避免异地扩容的消耗,但是这样扩容大了又会造成浪费的问题反过来为了节省空间扩容小了就会需要多次扩容这样异地扩容的消耗会非常大。
不过一般来说。单次扩容大减小扩容次数节省时间单次扩容小扩容次数多节省空间。除了物联网等领域时间比空间更宝贵所以一般扩容扩大点。
但是链表有个比较大的缺陷是不支持随机访问用下标访问如果大家学过C的STL,就会发现链表的排序比起顺序表来说没有优势此外如二分查找等场景都需要使用顺序表或者说数组。
总的来说顺序表在存储空间连续、支持随机访问等方面占有优势链表在没有容量和任意位置插入方面占优势。顺序表与链表是互补各有优势。
二、缓存利用率的比较
2.1前置知识
备注缓存利用率参考存储体系结构以及局部原理性。 如上图为我们电脑中存储体系一般来说我们接触最多的是主存(即内存)和本地磁盘磁盘或者叫做外存两者的区别在于内存是带电存储速度快但是空间相对较小8G、16G等而磁盘是不带电存储速度慢但是空间大可以达到几百G及以上。所谓带电与不带电存储是指程序运行时数据主要在内存上如果此时断电数据都会丢失如果我们按保存文件就会被保存到硬盘上这样即使断电数据也会保留下来。 以上图i为例程序运行后由CPU来执行一系列指令但是CPU的速度与内存的速度相差非常大两者不同频所以将内存中的数据加载到寄存器中CPU再对寄存器中的数据进行操作然后将数据放回内存中这是数据较小的情况四或八个字节如果数据较大就会加载到L3高速缓存中然后L2,L1一级一级加载。
2.2顺序表和链表缓存利用的比较 像顺序表和链表中的数据较大是加载到缓存中的CPU执行指令之前会先拿链表或顺序表的地址判断数据在不在缓存中如果数据在缓存中叫做缓存吗命中可以直接访问缓存如果不在缓存内叫不命中这是要先把数据从内存加载到缓存中再访问。
在这个加载的过程中由于计算机局部设计原理与计算机设计逻辑往往访问当前位置那么极有可能访问同时单独只访问当前位置的设计不划算使用物理线探测当前位置是0还是1所以一般会加载一段一长段几十个字节甚至是多少k具体数值跟CPU的型号字长有关系
这时对于数组来说如果第一个数据不命中那么就会将第一个数据连同后面一大段数据加载到缓存中数组不同数据存储的物理地址是连续的之后我们连续访问多个数据都会出现缓存命中的前情况我们将这称为缓存命中率高
但是链表不同节点的物理地址极大概率是不连续的这时将第一个节点连同后面一大段数据加载到缓存中时极大概率是无法加载第二个节点到缓存中的可能加载部分节点这时内存中就会加载进很多无用数据因为缓存大小是固定的根据最近最少用原则LRU,这些无用数据会把缓存中之前早期的数据挤走我们将这种情况称为缓存污染。所以链表的缓存命中率较低。
详解及补充知识本文仅为比较顺序表及链表相关缓存与知识可以看下文
与程序员相关的CPU缓存知识
