.Net Array 和 List 差異
Array 和 List 差異
最近看到很多面試回答跟文章，跟我所理解的實在是差蠻多的，做個筆記記錄一下。
最近最常看到的答案就是底下：
一、Array 的記憶體位置是連續的，List 則不是
二、Array 輪詢的速度較快，因為他的記憶體位置是連續的
三、Array 無法動態新增或刪除元素，但 List 可以
有關於有關於第一點我有一些不同的看法~~
首先是記憶體位置連續這件事
先用「值」型別來說，也就是 int, long這種的。
這種值型別在用 Array 時記憶體位置在 Heap 裡面是連續的沒錯。但 List 又何嘗不是？？
.Net Reference 裡面的原碼可以很清楚的看到， List 的實做也是用 Array，根本就沒有不同…
簡單來說，List 只是把 Array 包裝起來讓用的人更方便而已。
這真的讓我很搞不懂，所謂的記憶體沒有連續的依據到底是從哪來的……
再來說說「參照」型別，也就是常用的 class
當宣告 Class Array 時，指的是在 Heap 裡面要一塊「連續」的記憶體，而這每一個記憶體是「等著」要用來存放後面 New Class 時的記憶體位置。
用以下的程式來註解說明：
using System;
public class Program
{
public class Student
{
public int Id;
}
public static void Main()
{
//ls 這個變數會在 stack 裡面有一個位置，裡面存放的是指向 Heap 的一塊連續記憶體的位置
//而 Heap 記憶體所分配的大小也跟 Class 有多少 Property 無關，
//因為它只需要夠放接下來 New Class 的時後的記憶體位置即可
Student[] ls = new Student[10];
//這裡就是把這個 Class 的記憶體位置放到 Array 的第一個元素裡面
ls[0] = new Student();
Console.WriteLine(ls[0].Id);
}
}
就參照型別來說，在 Heap 裡面也稱不上是連續，頂多就是存放 New Class 的記憶體位置有連續而已。但實際要讀取 class 資料時，還是散落在記憶體各地。
結論：List 的記憶體到底哪裡沒有連續……
結下來是第二點，記憶體連續為何較快？
很多的面試者都有寫這個答案，但問的時後都沒有人回答過，這似乎隱約的說明，答案只是從谷歌大神抄來的…
記憶體連續為何會快，可以說到 memory spatial locality & temporal locality 這二個特性。
spatial 是指假設程式某一個位置的記憶體資料，緊接著下一個位置的資料有很高的機會也會存取。
temporal 是指已經被放到記憶體的資料，有很高的機會會再被使用第二次、第三次等等。
所以 spatial 為例，電腦在讀取記憶體（DRAM）資料放到 cache（L1, L2）時，會把臨近的資料先一起放到 cache。
所以當 cpu 是在 iterate 資料並且資料在記憶體裡面的存放又是連續時， cache 的命中率就會大大的提升，不用再去 DRAM 抓一次。
最常被人提到的例子，就是寫一個全部都是數字的二維陣列，然後用 row by row 來跑迴圈。接著再用 column by column 來跑一次迴圈。
當數量越多的時後， row by row 的效率一定會遠大於 column by column。