建设pc 移动网站,做网站一定要虚拟主机吗,徐州云龙区建设局网站,网站栏目推介怎么做顺序表和链表都是线性表#xff0c;它们有着相似的部分#xff0c;但是同时也有着很大的差异。 存储空间上的差异#xff1a; 对于插入上的不同点#xff0c;顺序表在空间不够时需要扩容#xff0c;而如果在使用realloc函数去扩容#xff0c;会有原地扩容和异地扩容两种情…顺序表和链表都是线性表它们有着相似的部分但是同时也有着很大的差异。 存储空间上的差异 对于插入上的不同点顺序表在空间不够时需要扩容而如果在使用realloc函数去扩容会有原地扩容和异地扩容两种情况若申请的空间没有被使用则会用原地扩容消耗不会大。但是若申请被使用的话则会用异地扩容则会在堆区上申请一块空间并把原来的数据拷贝过来就会造成消耗会比较大的问题。而带头双向循环链表则不需要考虑到这些问题只需要按需申请释放就可以了。同时顺序表的扩容还可能存在空间浪费的问题。
关于原地扩容和异地扩容的代码
int main()
{int* p1 (int*)malloc(8);printf(%p\n, p1);int p2 (int*)realloc(p1, 800);printf(%p\n, p2);return 0;
}
原地扩容 异地扩容 关于缓存利用率两种线性表也有很大的不同。
在此之前我们首先要知道缓存(高速缓冲存储器)是什么 在多体并行存储系统中由于I/O设备向主存请求的级别高于CPU访存这就出现了CPU 等待I/0设备访存的现象致使CPU空等一段时间甚至可能等待几个主存周期从而降低了CPU的工作效率。为了避免CPU与I/O设备争抢访存可在CPU与主存之间加一级缓存(参见图4.3),这样主存可将CPU要取的信息提前送至缓存一旦主存在与I/O设备交换时CPU 可直接从缓存中读取所需信息不必空等而影响效率。 从另一角度来看主存速度的提高始终跟不上CPU的发展。据统计CPU的速度平均每年改进60%,而组成主存的动态RAM速度平均每年只改进7%,结果是CPU和动态RAM之间的速度间隙平均每年增大50%。例如100MHz的Pentium处理器平均每10ns就执行一条指令而动态RAM的典型访问时间为60~120ns。这也希望由高速缓存Cache 来解决主存与CPU速度的不匹配问题。
缓存的命中
在说明这两个问题之前。我们需要要解一个术语 Cache Line。缓存基本上来说就是把后面的数据加载到离自己近的地方对于CPU来说它是不会一个字节一个字节的加载的因为这非常没有效率一般来说都是要一块一块的加载的对于这样的一块一块的数据单位术语叫“Cache Line”
比如Cache Line是最小单位64Bytes所以先把Cache分布多个Cache Line比如L1有32KB那么32KB/64B 512 个 Cache Line。
在计算机读取数据的时候计算机会根据地址去访问如果数据在缓存上则称为命中成功直接就可以访问数据了。如果数据在主存上则称为命中失败就需要将主存上的数据移到缓存上这时就需要使用Cache来进行运输。
我们再与线性表联系起来。
顺序表的物理结构和逻辑结构的方面上都是连续的在数据在主存上的情况下数据被移到cache上面。同时因为对于CPU来说它一般来说都是要一块一块的加载的也就代表着加载的时候会将顺序表连带着后面的数据一并加载到cache上面也就节省了时间节约了空间提高了程序的运行效率。
链表双向带头循环链表的逻辑结构是不连续的但是它的物理结构却是不连续的。所以在CPU一块一块加载数据的时候在加载第一个数据的时候并不会连带着后面的数据去加载参考下图也就降低了程序运行的效率。同时因为有大量的无用的数据加载到缓存会造成数据的污染影响程序的性能。 想对缓存的命中有更深的了解的话可以参考陈皓大佬的文章《程序员相关的CPU缓存知识 》进一步了解。
与程序员相关的CPU缓存知识 | 酷 壳 - CoolShell
