专栏首页FREE SOLO为什么数组查询效率高于链表?

为什么数组查询效率高于链表?

为什么数组查询效率高于链表?

1.首先了解到电脑中存在多种不同的存储器,如下表

CPU 寄存器 – immediate access (0-1个CPU时钟周期) CPU L1 缓存 – fast access (3个CPU时钟周期) CPU L2 缓存 – slightly slower access (10个CPU时钟周期) 内存 (RAM) – slow access (100个CPU时钟周期) 硬盘 (file system) – very slow (10,000,000个CPU时钟周期)

各级别的存储器速度差异非常大,CPU寄存器速度是内存速度的100倍! 这就是为什么CPU产商发明了CPU缓存。 而这个CPU缓存,就是数组和链表的区别的关键所在。

CPU缓存会把一片连续的内存空间读入,因为数组结构是连续的内存地址,所以数组全部或者部分元素被连续存在CPU缓存里面,平均读取每个元素的时间只要3个CPU时钟周期。 而链表的节点是分散在堆空间里面的,这时候CPU缓存帮不上忙,只能是去读取内存,平均读取时间需要100个CPU时钟周期。这样算下来,数组访问的速度比链表快33倍! (这里只是介绍概念,具体的数字因CPU而异)。

2.寻址操作次数链表要多一些。数组只需对 [基地址+元素大小*k] 就能找到第k个元素的地址,对其取地址就能获得该元素。链表要获得第k个元素,首先要在其第k-1个元素寻找到其next指针偏移,再将next指针作为地址获得值,这样就要从第一个元素找起,多了多步寻址操作,当数据量大且其它操作较少时,这就有差距了。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2019Java面试题:对ORM理解如何?

    什么是“持久化” ? 持久(Persistence),即把数据(如内存中的对象)保存到可永久保存的存储设备中(如磁盘)。持久化的主要应用是将内存中的数据存储在...

    葆宁
  • tcp/ip模型应用数据整条发送流程

    1、某进程(也就是在应用层)准备好待传输数据,若目的地址是域名则要先通过DNS解析成IP地址

    葆宁
  • 再识云计算前世今生来世

    云计算,当我第一次听说这个词的时候,是在2015年吧。可以说直到现在对于这个概念都不是十分理解。直到上个月看了这本书《大话云计算》。

    葆宁
  • 软件性能测试(连载6)

    08:26am up 7 min, 2 users, load average: 0.17, 0.16, 0.12

    小老鼠
  • 走进科学之揭开神秘的"零拷贝"

    "零拷贝"这三个字,想必大家多多少少都有听过吧,这个技术在各种开源组件中都使用了,比如kafka,rocketmq,netty,nginx等等开源框架都在其中引...

    用户5397975
  • 物理CPU CPU核数 逻辑CPU 几核几线程的概念详解

    物理CPU 物理CPU就是计算机上实际配置的CPU个数。在linux上可以打开cat /proc/cpuinfo 来查看,其中的physical id就是每...

    我是李超人
  • 如何查看 Linux 服务器性能参数指标?

    这里只是一些简单的工具查看系统的相关参数,当然很多工具也是通过分析加工 /proc、/sys 下的数据来工作的,而那些更加细致、专业的性能监测和调优,可能还需要...

    lyb-geek
  • 服务器病了吗? Linux 服务器的那些性能参数指标

    小小科
  • Linux 服务器性能出问题,排查下这些参数指标

    一个基于 Linux 操作系统的服务器运行的同时,也会表征出各种各样参数信息。通常来说运维人员、系统管理员会对这些数据会极为敏感,但是这些参数对于开发者来说也十...

    马哥linux运维
  • Linux 服务器性能出问题,排查下这些参数指标

    一个基于 Linux 操作系统的服务器运行的同时,也会表征出各种各样参数信息。通常来说运维人员、系统管理员会对这些数据会极为敏感,但是这些参数对于开发者来说也十...

    小小科

扫码关注云+社区

领取腾讯云代金券