京东金融一面——数组和链表区别?为什么链表查找慢?数组查找快?为什么连续内存就方便查找?(查找速度快)

xiaoxiao2021-03-01  13

面试官怒怼(也是我太紧张,没说清楚,这里总结,其实也要说到CPU的一些东西,平时没注意)

数组与链表的优缺点;

数组: 优点:使用方便 ,查询效率 比链表高,内存为一连续的区域 缺点:大小固定,不适合动态存储,不方便动态添加 链表: 优点:可动态添加删除 大小可变 ,内存可能是不连续内存,链式存储。 缺点:只能通过顺次指针访问,查询效率低

链表和数组的本质差异

1 在访问方式上 数组可以随机访问其中的元素 链表则必须是顺序访问,不能随机访问 2 空间的使用上 链表可以随意扩大 数组则不能

从CPU的角度

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而异)

总结一下, 各种存储器的速度差异很大,在编程中绝对有必要考虑这个因素。 比如,内存速度比硬盘快1万倍,所以程序中应该尽量避免频繁的硬盘读写;CPU缓存比内存快几十倍,在程序中尽量多加利用。

另外贴一些CPU参数,感觉原来都没了解过,o(╥﹏╥)o

CPU性能衡量参数-主频,MIPS,CPI,时钟周期,机器周期,指令周期 1,主频

主频 = 时钟频率,它是指CPU内部晶振的频率,常用单位为MHz,它反映了CPU的基本工作节拍;

时钟频率又称主频,它是指CPU内部晶振的频率,常用单位为MHz,它反映了CPU的基本工作节拍;

2,时钟周期

时钟周期 t =1/ f; 主频的倒数

3,机器周期

机器周期 = m*t ;一个机器周期包含若干个时钟周期

4,指令周期

指令周期 = m*t*n; 执行一条指令所需要的时间,一般包含若干个机器周期

5,CPI

CPI = m*n; 平均每条指令的平均时钟周期个数

指令周期 = CPI×机器周期 = n(CPI=n)×m×时钟周期=nm/主频f, 注意指令周期单位是s或者ns,CPI无量纲

参考:https://en.wikipedia.org/wiki/Cycles_per_instruction

6,MIPS(MillionInstructions Per Second)

MIPS = 每秒执行百万条指令数 = 1/(CPI×时钟周期)= 主频/CPI

MFLOPS 每秒百万浮点运算次数。

表示秒钟所能执行的指令条数,对于微型计算机可用CPU的主频和每条指令的执行所需的时钟周期来衡量。

参考链接

转载请注明原文地址: https://www.6miu.com/read-3849942.html

最新回复(0)