【數據結構入門】順序錶和鏈錶的區別,以及啥是緩存利用率

CodeWinter 2022-01-08 00:58:14 阅读数:391

利用率 利用 用率

(1)順序錶和鏈錶的區別

鏈錶和順序錶各有優劣,它們相輔相成

順序錶 鏈錶
存儲空間上 物理上一定連續 邏輯上連續,物理上不一定連續
隨機訪問(用下標訪問) 支持 [ O(1) ] 不支持 [ O(N) ]
在任意比特置插入或者删除元素 可能需要挪動元素,效率低 [ O(N) ] 只需要修改指針指向
插入 動態順序錶,空間不够時需要擴容
(擴容可能造成空間浪費)
沒有容量的概念,按需申請空間
應用場景 元素高效存儲、隨機訪問多
(尾插尾删多)
任意比特置頻繁的插入和删除
緩存利用率

(2)緩存利用率

1)存儲器層次結構

image-20210910163919963

2)CPU和寄存器、高速緩存,以及主存之間的關系

假如我們寫了一個程序,實現分別對順序錶和鏈錶上的每個數據+1,這個程序會被編譯成指令,由CPU執行指令

CPU運算速度快,讀取內存,內存速度跟不上,CPU一般就不會直接訪問內存,而是把要訪問的數據先加載到緩存體系,如果是小於8byte的數據,直接到寄存器,如果是大的數據會到三級緩存,CPU直接跟緩存交互。

image-20210910162803993

如圖:做菜時先會到緩存中去取食材,緩存中沒有食材,再去內存那裏買……

image-20210910163746223

3)緩存利用率

實現分別對順序錶和鏈錶上的每個數據+1,要先讀取數據,然後運算,再寫回主存

CPU執行指令運算要訪問數據,會先去緩存中找有沒有這個數據:

  1. 如果有,說明緩存命中了

  2. 如果沒有,說明緩存未命中,就從主存中讀取一段連續內存空間的數據到緩存,繼續找

image-20210910170439819

順序錶物理地址是連續的,增加了命中率,就不用頻繁的從主存中讀數據到緩存中,提高了緩存利用率

這就是物理地址連續的優勢,所以在現實生活中,很多地方還是推薦用順序錶的

版权声明:本文为[CodeWinter]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201080058137218.html