爲什麼不能擴展數組？

當我們創建一個數組時，我們不能改變它的大小;它是固定的。好吧，看起來不錯，我們可以創建一個新的更大的數組，然後逐個複製這些數值，這個速度有點慢。它的技術背景是什麼？爲什麼不能擴展數組？

來源

2010-05-10 Mustafa

你在用什麼語言？ – 2010-05-10 18:15:19

您將需要指定您正在討論的編程語言。 – Kzqai 2010-05-10 18:15:39

這是一個非常廣泛的問題。要真正瞭解你必須知道計算機的內部工作原理。 – ChaosPandion 2010-05-10 18:15:49

這個問題沒有提到一種語言，所以我要選擇「C」陣列作爲我的答案。

將數組分配爲一塊內存。增長數組是有問題的，因爲唯一正確使用它的方法是在最後增加數組。對於N的增長，在下一個分配的地址之前，在數組末尾必須至少有N個空閒字節。

支持這種類型的分配需要將分配分散到虛擬地址空間。這既消除了將內存分配彼此靠近並用於增加分段的好處。這在大多數試圖將內存打包在一起並減少碎片的內存管理器面前飛來飛去。

在內存空間足夠的地方分配一個新陣列並複製數組根本沒有一個選項作爲一個通用的解決方案。之所以這樣，是因爲消費者通過指針可以看到數組的前一個位置。

int* array = malloc(int*someSize); 
int* pointer1 = &(arr[2]); 
growArray(&array, 12); // Can't move because pointer1 knows the address of the array

來源

2010-05-10 18:22:09 JaredPar

我覺得你很好，直到最後一段。它*是*可能的，你只需要小心，你不要留下任何懸掛的指針。無論如何，他都將此視爲Java。 – mpen 2010-05-10 18:25:25

@Mark，我將它改爲在文中包含「作爲一般解決方案」，以便更清楚地說明這一點。 – JaredPar 2010-05-10 18:29:08

+1很好的答案。 – helpermethod 2010-05-10 20:45:55

從根處開始的數組是一個連續的「數組」。其他數據可以佔用此區域內存之前和之後的數據，因此如果不分配適合新的更大容量的新的，不同區域的內存，將無法動態調整其大小。

來源

2010-05-10 18:16:04

這取決於語言。

在C語言（以及類似Java的類似語言）中，當您聲明一個像int ary[10]這樣的數組時，系統留出足夠的內存來保存10個整數。擴展它並不容易，因爲系統沒有留出任何額外的空間（因爲它不知道你是否想要擴展它或多少），並且可能正在使用陣列後出現的內存通過別的東西。所以，獲得更大數組的唯一方法是放置一個新的內存塊，它將容納擴展數組，然後複製舊內容並添加新項。

你是對的，這可能會很慢。解決它的一個辦法是聲明你的陣列比你需要的大，以便給你增長空間。特別是在較舊的電腦上，這可能會導致程序耗盡大量從未使用過的內存。

另一種解決方法是使用具有可擴展數組的高級語言。例如，Ruby允許您將更多項添加到數組中，而無需聲明內存或複製數組內容。

來源

2010-05-10 18:19:41 bta

但是，您應該意識到，在具有可變大小數組的語言中，數組可能仍會由固定大小的存儲支持，並在必要時進行擴展和複製。（或者它被實現爲一個鏈表，它避免了複製的需要，但是在訪問任意索引方面還有其他缺點。） – 2010-05-10 18:23:44

Ruby只是爲你做內存分配和數據拷貝。硬件層面沒有辦法解決這個問題。或者也許它使用的訪問時間較慢的數據結構，但實際上可以在不重新分配的情況下變大。 – phkahler 2010-05-10 18:26:51

@JS Bangs，phkahler-兩個好點。我的主要觀點是你不必擔心自己做這件事。 – bta 2010-05-10 22:40:22

取決於您的語言，但通常陣列排列爲內存中的一系列連續空間。這樣，您不必爲數組中的每個點存儲內存位置，只需存儲一個內存位置（數組的開始），然後添加一個偏移量（偏移量將是每個項的大小乘以索引你想要）找出某個特定條目在內存中的位置。

這也是爲什麼數組通常只包含一種類型，否則無法進行如此簡單的計算。確實允許存儲多種類型的語言實際上是創建一個普通數組，並將指針指向數組中的每個條目 - 所有指針的大小通常相同。這種間接成本的水平，這就是爲什麼「簡單」的語言往往慢一點。

無論如何，當你分配更多的內存時，你想把新的內存放在數組的末尾 - 否則你會用一個洞來分割你的內存 - 你爲什麼要這樣做？

所以你不能只是擴展陣列而不用物理移動它。

計算機已經這麼做了很多年了，所以大多數語言都有一些方法來分配新的內存塊，然後告訴CPU將所有條目都塊複製到新塊中，並更改指針來反映這一點，但通常（C，Java，...）他們把這個留給程序員用特定的命令來複制數組而不是爲你做（可能只是爲了讓你知道擴展數組不是「免費」的）

可以在數組末尾添加一個指針，以跳轉到要添加到數組末尾的新內存塊，但是現在您的數組查找速度已經變得相當緩慢了。

許多語言只是將數組作爲允許這種功能的集合來包裝。例如，Java Vector/ArrayList將自動爲您重新分配內存。鏈接列表實際上只是每次分配一個元素，並指向下一個元素。添加元素的速度非常快，但是元素5000非常慢（您必須讀取每個元素，而讀取元素1的數組與元素5000一樣快）

來源

2010-05-10 18:19:51

一般而言，編程語言有地方，分配的內存一個固定部分的東西的抽象。然後，從這種抽象出發，可以創建其他抽象，隱藏內存管理的複雜性，可能通過移動/複製數據。

大多數時候，array是固定的 - 一個（不知）低級別的抽象 - 而lists或collections被建立在陣列的頂部，並知道如何動態調整自己。

有時候這樣的低級抽象可以實現有效算法/優化。但是在大多數代碼中，您可以使用列表和集合，而不必擔心性能問題。

來源

2010-05-10 18:22:31 ewernli

是否可以更改數組的大小取決於您使用的是哪種語言。在那些不能增加數組大小的語言中，原因是數組佈局在內存中的連續位置，編譯器無法保證數組末尾的位置可以添加到數組中。許多編程語言都支持可擴展的數組類型，但這些語言只是簡單地爲您處理底層內存的重新分配和複製。

例如，在Curl編程語言中，存在具有大小和最大大小的FastArray類型。 max-size指定數組的最大大小，並確定將爲該數組分配多少內存。還有一種更通用的Array類型，它使用FastArray作爲它的底層實現，並且如果數組需要擴展超出底層FastArray的最大大小，它將替換FastArray實例。

來源

2010-05-10 18:24:31

回到彙編語言，我們有義務聲明變量所需的內存空間。這是數據段（DS）註冊表中的保留內存。

所以，大致看上去就像這樣（Borland的渦輪彙編）：

.DATA 
    myStringVariable DB "Hello world!", 13, 10 
    myArrayVariable DW "     " 'Reserving 20 bytes in memory (in a row) 

.CODE 

    MOV AX, @DATA 
    MOV DS, AX 
    ' ...

然後，一旦。數據段被分隔，它不能被改變，因爲.CODE段（CS）在稍後的幾個字節處開始。

因此，如果陣列本來可擴展的，像集合在.NET，數據會覆蓋的代碼，從而導致程序崩潰等

C/C++（3.0），帕斯卡（ 7.0），QBasic，PowerBasic和COM調試程序基於這種架構，並且可以做得比Assembler允許的更好。現在，我們現在可以用更靈活的技術根據需要隨時分配內存地址，並且只用一個變量來保存對它們的引用，這樣數組就可以通過集合進行擴展。但是在某些情況下，您需要精確的字節數量，比如網絡數據包等，例如數組仍然有用。另一個例子是將圖像存儲在數據庫中。你完全知道割大字節是一個圖像，所以你可以將它存儲在一個字節數組中（Byte []）。

也許我在這裏錯過了一些精度，我寫了我記憶中的舊我最喜歡的編程語言。也許一些人會提出一些更詳細的東西。

希望這會有所幫助！ =）

來源

2010-05-10 18:39:17

爲什麼不能擴展數組？

回答

相關問題