数据结构和算法学习记录——总结顺序表和链表(双向带头循环链表)的优缺点、CPU高速缓存命中率

简介: 数据结构和算法学习记录——总结顺序表和链表(双向带头循环链表)的优缺点、CPU高速缓存命中率

顺序表和链表

两个结构各有优势,严格来说,他们是相辅相成的。

顺序表

优点

  1. 支持随机访问(用下标访问),需要随机访问结构支持的算法可以很好的适用。
  2. CPU高速缓存命中率较高

缺点

  1. 在头部或中部插入删除数据时,时间效率低。O(N)
  2. 是占用的连续的物理空间,空间不够时需要进行扩容。
  • 扩容有一定程度的空间消耗
  • 为了避免频繁扩容,一般我们都按倍数去扩容,用不完的这个空间就存在了空间浪费

链表(双向带头循环链表)

优点

  1. 任意位置插入删除数据都很方便,时间效率高。O(1)
  2. 可以按需申请空间。(用多少申请多少,且不会造成空间消耗)

缺点

  1. 不支持随机访问(用下标访问)。这意味着:一些排序和二分查找等在这种结构上并不适用。
  2. 链表存储一个值,同时也要存储链接指针,也有一定的消耗(很小)。
  3. CPU高速缓存命中率较低。

简单解释CPU高速缓存命中率

存储体系大类别的分,可以分为带电存储和不带电存储。

主存往上是带电存储,往下是不带电存储。


了解CPU高速缓存命中率需要多加了解的两个存储设备:三级缓存、寄存器


寄存器的速度是非常快的,而主存的速度相对来说很慢,当CPU要进行计算时,对于小的数据:会将数据从主存加载到寄存器中,计算完之后再返回内存;对于大的数据:则是会将数据加载到三级缓存中,寄存器从缓存中拿取数据进行计算,计算完再返回内存。



在访问存储数据1的内存位置 0x00123400时,会先看它是否存在于缓存中。

如果在,就直接访问;如果不在,就先加载到缓存中,再进行访问。

加载时,会加载一块连续的内存,假设一次加载20个字节(具体大小取决于硬件体系)。那顺序表的一块空间就能一次被命中到多个(即加载到多个的数据);而链表的内存空间不一定连续,可能加载的一块连续空间中命中不到链表的下一个结点。


end

目录
相关文章
|
1天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
|
1天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
|
1天前
|
机器学习/深度学习 数据采集 监控
算法金 | DL 骚操作扫盲,神经网络设计与选择、参数初始化与优化、学习率调整与正则化、Loss Function、Bad Gradient
**神经网络与AI学习概览** - 探讨神经网络设计,包括MLP、RNN、CNN,激活函数如ReLU,以及隐藏层设计,强调网络结构与任务匹配。 - 参数初始化与优化涉及Xavier/He初始化,权重和偏置初始化,优化算法如SGD、Adam,针对不同场景选择。 - 学习率调整与正则化,如动态学习率、L1/L2正则化、早停法和Dropout,以改善训练和泛化。
3 0
算法金 | DL 骚操作扫盲,神经网络设计与选择、参数初始化与优化、学习率调整与正则化、Loss Function、Bad Gradient
|
9天前
|
存储 算法
顺序表经典算法
顺序表经典算法
|
14天前
|
缓存 负载均衡 NoSQL
Redis系列学习文章分享---第十四篇(Redis多级缓存--封装Http请求+向tomcat发送http请求+根据商品id对tomcat集群负载均衡)
Redis系列学习文章分享---第十四篇(Redis多级缓存--封装Http请求+向tomcat发送http请求+根据商品id对tomcat集群负载均衡)
30 1
|
14天前
|
存储 缓存 NoSQL
Redis系列学习文章分享---第十三篇(Redis多级缓存--JVM进程缓存+Lua语法)
Redis系列学习文章分享---第十三篇(Redis多级缓存--JVM进程缓存+Lua语法)
31 1
|
6天前
|
Dart 算法 JavaScript
C#数据结构与算法入门教程,值得收藏学习!
C#数据结构与算法入门教程,值得收藏学习!
|
14天前
|
缓存 NoSQL Java
Redis系列学习文章分享---第四篇(Redis快速入门之Java客户端--商户查询缓存+更新+双写一致+穿透+雪崩+击穿+工具封装)
Redis系列学习文章分享---第四篇(Redis快速入门之Java客户端--商户查询缓存+更新+双写一致+穿透+雪崩+击穿+工具封装)
21 0
|
14天前
|
算法 Java
《JVM由浅入深学习【八】 2024-01-12》JVM由简入深学习提升分(JVM的垃圾回收算法)
《JVM由浅入深学习【八】 2024-01-12》JVM由简入深学习提升分(JVM的垃圾回收算法)
9 0
|
15天前
|
机器学习/深度学习 人工智能 算法
技术经验解读:【转】完美洗牌算法学习
技术经验解读:【转】完美洗牌算法学习