數(shù)組

Yuqi 發(fā)布于2019-08-19 11:35 / 2288人閱讀

摘要：二數(shù)組擴容及拷貝數(shù)組的擴容數(shù)組是根據(jù)固定容量創(chuàng)建的，在必要的時候我們需要對數(shù)組進行擴容初始長度為下面決定需要對數(shù)組進行擴容對原數(shù)組進行內(nèi)容拷貝在對數(shù)組進行拷貝時除了利用循環(huán)遍歷數(shù)組元素進行拷貝外，推薦使用更高效的方法。

PS：如果覺得文章有什么地方寫錯了，哪里寫得不好，或者有什么建議，歡迎指點。

一、認識數(shù)組

數(shù)組是一種線性表數(shù)據(jù)結(jié)構(gòu)。它用一塊連續(xù)的內(nèi)存空間，來存儲相同類型的一組數(shù)據(jù)。

1. 概念的理解 線性表:

顧名思義，線性表就是數(shù)據(jù)排列成像一條線一樣的結(jié)構(gòu)。每個線性表上的數(shù)據(jù)最多只有前和后兩個方向，數(shù)組，鏈表，棧，隊列等都是典型的線性表結(jié)構(gòu)。

與其相對立的，在非線性表中，數(shù)據(jù)之間并不是簡單的前后關系，像樹，堆，圖等都是典型的非線性表。

連續(xù)的內(nèi)存空間和相同類型的數(shù)據(jù)：

即計算機分配連續(xù)的內(nèi)存單元來存儲數(shù)據(jù)，相同類型的數(shù)據(jù)即每個內(nèi)存單元的大小是相同的。

如聲明一個長度為 5 的 int 類型的數(shù)組 int[] arr = new int[5] ，計算機給數(shù)組分配了一塊連續(xù)的內(nèi)存空間，其中內(nèi)存塊的首地址為 base_address = 0xc0000160e0，每個內(nèi)存單元占 4 個字節(jié)：

2. 高效的隨機訪問

數(shù)組的一個特點是可以根據(jù)下標隨機訪問數(shù)組元素，其時間復雜度為 O(1)，那么它是如何實現(xiàn)的呢？

計算機分配的內(nèi)存單元存儲數(shù)據(jù)時，也會為內(nèi)存單元分配一個地址，然后可以通過地址來訪問內(nèi)存中的數(shù)據(jù)。由數(shù)組的內(nèi)存空間連續(xù)的特性，當需要訪問某個元素時，它會通過下面的尋址公式來計算出該元素存儲的內(nèi)存地址：

// 一維數(shù)組 arr[n]：
arr[i]_address = base_address + i * data_type_size

// 二維數(shù)組 arr[m][n]：
address = base_address + (i * n + j) * data_type_size

其中 data_type_size 表示數(shù)組中每個元素的大小，如在 int 型的數(shù)組 arr 中，data_type_size 就為 4 個字節(jié)。

這樣，便可以很快的根據(jù)內(nèi)存地址來讀取數(shù)據(jù)。

3. 低效的“插入”和“刪除”

在數(shù)組中，為了保持內(nèi)存數(shù)據(jù)的連續(xù)性，會導致插入、刪除這兩個操作比較低效。

例如在 插入操作 中，假設數(shù)組的長度為 n，若我們要在數(shù)組的第 k 個位置插入一個數(shù)據(jù)，為了把第 k 個位置騰出來給新的數(shù)據(jù)，我們需要將第 k ~ n 這部分的元素都順序地向后挪一位： arr[i] = arr[i-1] 。其時間復雜度為 O(n)。

而在 刪除操作 中，若我們要刪除數(shù)組的第 k 個元素，為了內(nèi)存的連續(xù)性，就需要將第 k ~ n 這部分的元素都順序地向前挪一位： arr[i] = arr[i+1] 。其時間復雜度為 O(n)。

插入和刪除操作的優(yōu)化

然而在很多我們不需要考慮數(shù)組中元素的有序性，數(shù)組只被當作一個存儲數(shù)據(jù)的集合的時候，為了避免大規(guī)模的數(shù)據(jù)搬移，我們可以對插入和刪除操作做一些優(yōu)化。例如：

如果要將某個數(shù)據(jù)插入到第 k 個位置，可以直接將第 k 為的數(shù)據(jù)搬移到數(shù)組元素的末尾，然后將新的元素值直接賦值給第 k 個元素；

如果要將第 k 個元素刪除，可以直接將數(shù)組的最后一個元素賦值給第 k 個元素，然后刪除最后一個元素即可。

這樣，其時間復雜度就會降為 O(1) 。

4. 容器與數(shù)組的比較

對于數(shù)組類型，Java 中的 ArrayList 容器是基于數(shù)組實現(xiàn)的，那么二者相比各有什么優(yōu)點和適用場景呢？

ArrayList 的優(yōu)勢是方便，適合在一般的業(yè)務中使用。它將很多數(shù)組的操作細節(jié)封裝起來了，如數(shù)據(jù)的插入、刪除、數(shù)組的擴容。ArrayList 無法存儲基本類型，比如 int、double，需要封裝為 Integer、Double 類，而自動裝箱/拆箱的操作會有一定的性能消耗；

相對于容器來說，數(shù)組的使用雖然麻煩一點，但它的性能會優(yōu)于容器，更適合用于底層的開發(fā)和追求極致性能的優(yōu)化。

二、數(shù)組擴容及拷貝 1. 數(shù)組的擴容

數(shù)組是根據(jù)固定容量創(chuàng)建的，在必要的時候我們需要對數(shù)組 arr 進行擴容：

// 初始長度為 10
int[] arr = new int[10];
for (int i = 0; i < arr.length; i++) {
    arr[i] = i+1;
}
...
// 下面決定需要對數(shù)組 arr 進行擴容
int[] newArr = new int[arr.length*2];

// 對原數(shù)組進行內(nèi)容拷貝
for (int i = 0; i < arr.length; i++) {
    newArr[i] = arr[i];
}

arr = newArr;

在對數(shù)組進行拷貝時除了利用 for 循環(huán)遍歷數(shù)組元素進行拷貝外，推薦使用更高效的 System.arraycopy() 方法。

2. System.arraycopy() 方法拷貝數(shù)組

System.arraycopy() 使用 native 關鍵字修飾，大大加快程序性能，為 JVM 內(nèi)部固有方法。它通過手工編寫匯編或其他優(yōu)化方法來進行 Java 數(shù)組拷貝，這種方式比起直接在 Java 上進行 for 循環(huán)或 clone 是更加高效的。數(shù)組越大體現(xiàn)地越明顯。

該方法用于從指定源數(shù)組中進行拷貝操作，可以指定開始位置，拷貝指定長度的元素到指定目標數(shù)組中。其聲明如下：

public static native void arraycopy(Object src,  int srcPos, Object dest, int destPos, int length);

參數(shù)說明：

src：要被復制的數(shù)組，

srcPos：被復制的數(shù)組開始復制的下標，

dest：目標數(shù)組，也就是要把數(shù)據(jù)放進來的數(shù)組，

destPos：從目標數(shù)組第幾個下標開始放入數(shù)據(jù)，

length：被復制的數(shù)組中拿幾個數(shù)值放到目標數(shù)組中；

例，數(shù)組 arr 進行擴容：

// 初始長度為 10
int[] arr = new int[10];
for (int i = 0; i < arr.length; i++) {
    arr[i] = i+1;
}
...
// 下面決定需要對數(shù)組 arr 進行擴容
int[] newArr = new int[arr.length*2];
System.arraycopy(arr,0,newArr,0,10); // 對原數(shù)組進行內(nèi)容拷貝
arr = newArr;

絕大部分數(shù)組和基于數(shù)組實現(xiàn)的容器（ArrayList 等）的擴容都是基于 System.arraycopy() 方法進行操作的。

歡迎您的點贊、收藏和評論！
（完）

GPU云服務器云服務器 java數(shù)組數(shù)組相加多維數(shù)組轉(zhuǎn)一維數(shù)組數(shù)組java二維數(shù)組二維數(shù)組轉(zhuǎn)換一維數(shù)組

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/77472.html

C語言進階：指針的進階

摘要：本章節(jié)在此基礎上，對語言階段指針進行更深層次的研究。數(shù)組指針的類型由數(shù)組類型決定，先找出數(shù)組的類型去掉名就是類型。相當于數(shù)組指針所指向數(shù)組的數(shù)組名。數(shù)組指針指向整個數(shù)組，將其看作二維數(shù)組并解引用得到一行的首元素，從而遍歷訪問。 ...

浠ラ箍 2021-09-02 15:15 評論0 收藏0
犀牛書——CHAP7：數(shù)組

摘要：數(shù)組有以下特點無類型數(shù)組元素可以是任意元素。因此，當小于數(shù)組最大索引時，大于的數(shù)組元素會被刪除。原數(shù)組不會改變將數(shù)組元素轉(zhuǎn)換為字符串并連接在一起。默認將數(shù)組元素用，連接，傳入的參數(shù)即為連接符。 showImg(https://box.worktile.com/view/fcfcdf2c99b14edfb6768085955ae253?pid=4b0845b09ca94218a955f8...

Alfred 2019-08-19 18:40 評論0 收藏0
JS基礎06「數(shù)組」

摘要：為了維持此規(guī)則不變化，數(shù)組有兩個特殊的行為。運算符對數(shù)組返回并且對于除了函數(shù)以外的所有對象都是如此。解決方案是檢查對象的類屬性，對數(shù)組而言該屬數(shù)組數(shù)組是值的有序集合。每個值叫做一個元素，而每個元素在數(shù)組中有一個位置，以數(shù)字表示，稱為索引。 JavaScript 數(shù)組是無類型的，數(shù)組元素可以是任意類型，并且同一個數(shù)組中的不同元素也可能有不同的類型。數(shù)組的元素甚至也可能是對象或其他數(shù)組...

forrest23 2019-08-26 10:58 評論0 收藏0
JavaScript數(shù)組

摘要：與稀疏數(shù)組對立的為密集數(shù)組，密集數(shù)組的索引會被持續(xù)的創(chuàng)建，并且其元素的數(shù)量等于其長度。創(chuàng)建一個長度為的數(shù)組，并初始化了個元素使用構(gòu)造函數(shù)創(chuàng)建數(shù)組對象的時候，關鍵字是可以省略的。另外使用和刪除元素是影響數(shù)組的長度的。說明：本文只總結(jié)了JavaScript數(shù)組在web端的行為，不包括NodeJs端的行為。本文不涉及類型化數(shù)組（TypedArray）的討論、總結(jié)。一、什么是數(shù)組數(shù)組的定...

HtmlCssJs 2019-08-23 10:23 評論0 收藏0
java知識體系梳理-->數(shù)組

摘要：知識體系梳理流程圖一維數(shù)組數(shù)組概述數(shù)組是指一組數(shù)據(jù)的集合，數(shù)組中的每個數(shù)據(jù)被稱作元素。定義打印數(shù)組元素方法按照給定的格式打印題目分析通過觀察發(fā)現(xiàn)，要實現(xiàn)按照指定格式，打印數(shù)組元素操作。按照這種方式，數(shù)組循環(huán)多圈以后，就完成了數(shù)組元素的排序。知識體系梳理流程圖 showImg(https://segmentfault.com/img/bVXwAi?w=902&h=652); 一維數(shù)組 ...

james 2019-08-15 12:23 評論0 收藏0
《javascript高級程序設計》筆記_數(shù)組稀疏數(shù)組 偽數(shù)組

摘要：數(shù)組是數(shù)據(jù)的有序列表，與其他語言不同的是，數(shù)組的每一項可以保存任何類型的數(shù)據(jù)。如下的代碼創(chuàng)建的就是一個密集數(shù)組稀疏數(shù)組與密集數(shù)組相反，并不強制要求數(shù)組元素是緊密相連的，即允許間隙的存在。數(shù)組是數(shù)據(jù)的有序列表，與其他語言不同的是，ECMAScript 數(shù)組的每一項可以保存任何類型的數(shù)據(jù)。也就是說，可以用數(shù)組的第一個位置來保存字符串，用第二位置來保存數(shù)值，用第三個位置來保存對象，以此類...

pepperwang 2019-08-21 11:56 評論0 收藏0