Array數(shù)組的概念和用法

這篇文章主要介紹“Array數(shù)組的概念和用法”，在日常操作中，相信很多人在Array數(shù)組的概念和用法問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Array數(shù)組的概念和用法”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

成都創(chuàng)新互聯(lián)公司是由多位在大型網(wǎng)絡(luò)公司、廣告設(shè)計公司的優(yōu)秀設(shè)計人員和策劃人員組成的一個具有豐富經(jīng)驗的團隊，其中包括網(wǎng)站策劃、網(wǎng)頁美工、網(wǎng)站程序員、網(wǎng)頁設(shè)計師、平面廣告設(shè)計師、網(wǎng)絡(luò)營銷人員及形象策劃。承接：成都做網(wǎng)站、成都網(wǎng)站制作、成都外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站改版、網(wǎng)頁設(shè)計制作、網(wǎng)站建設(shè)與維護、網(wǎng)絡(luò)推廣、數(shù)據(jù)庫開發(fā),以高性價比制作企業(yè)網(wǎng)站、行業(yè)門戶平臺等全方位的服務(wù)。

數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)筆記。

數(shù)組概念

數(shù)組（Array）是一種線性表數(shù)據(jù)結(jié)構(gòu)。它用一組連續(xù)的內(nèi)存空間，來存儲一組具有相同類型的數(shù)據(jù), 并且不支持動態(tài)擴容。

線性表
線性表就是數(shù)據(jù)排成一條線一樣的數(shù)據(jù)結(jié)構(gòu)，每個線性表最多只有前后兩個方向，數(shù)組，鏈表丶隊列丶棧等都是線性表數(shù)據(jù)結(jié)構(gòu)。
非線性表
非線性表就是數(shù)據(jù)不規(guī)則，與線性表是相對立的，比如二叉樹丶堆丶等，在非線性表中，數(shù)據(jù)之間并不是簡單的前后關(guān)系。

數(shù)組隨機訪問

公式
```
address[i] = base_address + i * data_type_size
```
address[i] :下標 i 的地址值。
base_address：數(shù)組的首地址。
data_type_size：數(shù)組中每個元素的大小，也就是數(shù)據(jù)類型大小(字節(jié))，例如int是4個字節(jié)。

數(shù)組的增加和刪除

數(shù)組(Array) 在增刪查這三個動作中，查詢是高效的，但是增和刪是低效的，查詢高效是因為數(shù)組支持隨機訪問，時間復(fù)雜度是 O(1),這里就不多贅述了，但是在增加和刪除的動作中，因為會涉及數(shù)據(jù)搬移，所以時間復(fù)雜度是 O(n)，下面來詳細講解。

低效的"插入"和"刪除"
```
	int[] info = new int[6];
```
插入
數(shù)組 info是一個一維數(shù)組，其內(nèi)容是 33,44,66,77,88現(xiàn)在需要在下標 2的位置插入55，將其變成33 44 55 66 77 88的數(shù)組，這其中涉及將下標 2到下標 4的之間進行數(shù)據(jù)進行搬移，完成后在下標 2的位置插入 55, 其復(fù)雜度是 O(n)，但如果是在最后進行插入的話其復(fù)雜度是 O(1)。
刪除
還拿數(shù)組 info來舉例，數(shù)組刪除前其內(nèi)容是 33,44,00,55,66,77現(xiàn)在進行刪除操作，刪除下標為 2內(nèi)容，這其中涉及將下標 3 到 5 的內(nèi)容向前搬移，其操作的時間復(fù)雜度是 O(n)，如果是是刪除最后一位且后面沒有內(nèi)容，則其時間復(fù)雜度是O(1)。
因插入和刪除操作會涉及到數(shù)據(jù)搬移,所以說他是低效的。
CPU緩存**
Cpu緩存的最小單位是Cpu緩存行，一個緩存行大小通常是64字節(jié)(取決于CPU)，試想一下你正在遍歷一個長度為 16 的 long 數(shù)組 data[16]，原始數(shù)據(jù)自然存在于主內(nèi)存中，訪問過程描述如下：
1：訪問 data[0]，CPU core 嘗試訪問 CPU Cache，未命中。
2：嘗試訪問主內(nèi)存，操作系統(tǒng)一次訪問的單位是一個 Cache Line 的大小 — 64 字節(jié)，這意味著：既從主內(nèi)存中獲取3：到了 data[0] 的值，同時將 data[0] ~ data[7] 加入到了 CPU Cache 之中，
4：訪問 data[1]~data[7]，CPU core 嘗試訪問 CPU Cache，命中直接返回。
5：訪問 data[8]，CPU core 嘗試訪問 CPU Cache，未命中, 嘗試訪問主存，重復(fù)步驟2。
測試數(shù)組和Cpu緩存行
因Cpu緩存最小單位是緩存行(64字節(jié))，我么來測試一下二維數(shù)組的橫向遍歷和縱向遍歷的具體時間和性能。
代碼
```
package com.com.array;

/**
 * @Auther: lantao
 * @Date: 2019-06-24 15:52
 * @Company: 隨行付支付有限公司
 * @maill: lan_tao@suixingpay.com
 * @Description: TODO
 */
public class ArrayTest {

    static long[][] arr;

    public static void main(String[] args) {
        long sum = 0L;
        arr = new long[1024 * 1024][10];
        // 橫向遍歷
        long l = System.currentTimeMillis();
        for (int i = 0; i < 1024 * 1024; i++) {
            for (int j = 0; j < 10; j++) {
                sum += arr[i][j];
            }
        }
        System.out.println("Loop Time 橫向遍歷：" + (System.currentTimeMillis() - l) + "ms");

        long l1 = System.currentTimeMillis();
        // 縱向遍歷
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 1024 * 1024; j++) {
                sum += arr[j][i];
            }
        }
        System.out.println("Loop Time 縱向遍歷：" + (System.currentTimeMillis() - l) + "ms");
    }
}
```

結(jié)果：
Loop Time 橫向遍歷：14ms
Loop Time 縱向遍歷：83ms

總結(jié)：因橫向遍歷遍歷的是行，然后在循環(huán)行的每一列，Cpu緩存會緩存64字節(jié)大小的緩存行，所以可以減少cpu和主存之間的交互，直接和高速緩存交互，提升性能，縱向遍歷因每次循環(huán)都是不同的行，所以使緩存行沒有作用。

到此，關(guān)于“Array數(shù)組的概念和用法”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>

分享題目：Array數(shù)組的概念和用法
新聞來源：http://muchs.cn/article14/gdepge.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站營銷、移動網(wǎng)站建設(shè)、、微信公眾號、網(wǎng)站建設(shè)、網(wǎng)站策劃

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容

Array數(shù)組的概念和用法

數(shù)組概念

線性表

非線性表

數(shù)組隨機訪問

公式

數(shù)組的增加和刪除

低效的"插入"和"刪除"

插入

刪除

CPU緩存**

測試數(shù)組和Cpu緩存行