当前位置: 首页 > news >正文

中国网站设计师seo搜索引擎优化工程师招聘

中国网站设计师,seo搜索引擎优化工程师招聘,wordpress 侧导航栏,做郑州的购物网站用什么名目录 一、顺序表和链表的区别(其他链表存在缺陷,比较意义不大,这里用带头双向循环链表与顺序表进行比较) 1.1插入、扩容与随机访问 二、缓存利用率的比较 2.1前置知识 详解及补充知识(本文仅为比较顺序表及链表&am…

目录

一、顺序表和链表的区别(其他链表存在缺陷,比较意义不大,这里用带头双向循环链表与顺序表进行比较)

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缓存知识

http://www.hrbkazy.com/news/24091.html

相关文章:

  • 哪家网站专做女性服装seo主要做哪些工作
  • 微信做引流网站百度快照查询
  • 自己建设购物网站磁力狗
  • 西安做网站的公司报价引流推广网站平台
  • 网页制作教程哔哩哔哩seo优化培训学校
  • 台州网站建设 网站制作 网站设计免费网站服务器安全软件下载
  • 做网站的生产方式北京百度公司地址在哪里
  • 浙江省工程建设协会网站seo导航
  • ssh实训做网站代码下载企业网站seo优化公司
  • 常州溧阳市建设局网站推广文案怎么写吸引人
  • 临朐营销型网站建设排名检测
  • 旅游网页设计模板图凡科seo网站优化收藏
  • 济宁网站开发公司seo整体优化步骤怎么写
  • 网站内页设置多少个关键字最好小红书seo优化
  • 中国移动官方网站登录入口网站单向外链推广工具
  • 在日本做网站的公司有哪些一个新手怎么去运营淘宝店铺
  • 网站公安备案多久审核宁波网站推广制作
  • vs2017 asp网站开发b站推广网站mmm
  • 股票配资网站建设网站热度查询
  • 响应式网站有什么区别网站更新seo
  • WordPress显示插件苏州seo按天扣费
  • 今科网站建设公司百度云搜索引擎入口 百度网盘
  • 小程序模板源代码广东做seo的公司
  • 河南省城市建设网站搜索引擎排名国内
  • 地区网站建设济南seo顾问
  • 东莞长安网站制作百度推广产品有哪些
  • 拉萨网站建设多少钱软文代发代理
  • 电商平台倒闭seo品牌优化百度资源网站推广关键词排名
  • 网站开发和推广的不同黑马培训
  • 上海做网站的公司排名小广告模板