数组查询为什么比链表快

Posted by Steven on 2020-07-25

1、寻址操作次数链表要多一些。

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

该回答源自:http://tieba.baidu.com/p/5069120437

2、一个常见的编程问题

遍历同样大小的数组和链表, 哪个比较快? 如果按照大学教科书上的算法分析方法,你会得出结论,这2者一样快, 因为时间复杂度都是 O(n)。 但是在实践中, 这2者却有极大的差异。 通过下面的分析你会发现, 其实数组比链表要快很多。
首先介绍一个概念:memory hierarchy (存储层次结构),电脑中存在多种不同的存储器,如下表

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时钟周期)
(数据来自 http://www.answers.com/topic/locality-of-reference)

3、CPU缓存

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

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

该回答源自:https://blog.csdn.net/Islandww/article/details/72511737

推荐文章