數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)-數(shù)組

這篇具有很好參考價(jià)值的文章主要介紹了數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)-數(shù)組。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

數(shù)組

概述

定義

在計(jì)算機(jī)科學(xué)中，數(shù)組是由一組元素（值或變量）組成的數(shù)據(jù)結(jié)構(gòu)，每個(gè)元素有至少一個(gè)索引或鍵來標(biāo)識(shí)

In computer science, an array is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key

因?yàn)閿?shù)組內(nèi)的元素是連續(xù)存儲(chǔ)的，所以數(shù)組中元素的地址，可以通過其索引計(jì)算出來，例如：

int[] array = {1,2,3,4,5}

知道了數(shù)組的數(shù)據(jù)起始地址 BaseAddress，就可以由公式 BaseAddress + i * size 計(jì)算出索引 i 元素的地址

i 即索引，在 Java、C 等語言都是從 0 開始
size 是每個(gè)元素占用字節(jié)，例如 int 占 4，double 占 8

小測試

byte[] array = {1,2,3,4,5}

已知 array 的數(shù)據(jù)的起始地址是 0x7138f94c8，那么元素 3 的地址是什么？

答：0x7138f94c8 + 2 * 1 = 0x7138f94ca

空間占用

Java 中數(shù)組結(jié)構(gòu)為

8 字節(jié) markword
4 字節(jié) class 指針（壓縮 class 指針的情況）
4 字節(jié) 數(shù)組大小（決定了數(shù)組最大容量是 2^{32}）
數(shù)組元素 + 對(duì)齊字節(jié)（java 中所有對(duì)象大小都是 8 字節(jié)的整數(shù)倍[^12]，不足的要用對(duì)齊字節(jié)補(bǔ)足）

例如

int[] array = {1, 2, 3, 4, 5};

的大小為 40 個(gè)字節(jié)，組成如下

8 + 4 + 4 + 5*4 + 4(alignment)

隨機(jī)訪問性能

即根據(jù)索引查找元素，時(shí)間復(fù)雜度是 O(1)

動(dòng)態(tài)數(shù)組

java 版本

public class DynamicArray implements Iterable<Integer> {
    private int size = 0; // 邏輯大小
    private int capacity = 8; // 容量
    private int[] array = {};


    /**
     * 向最后位置 [size] 添加元素
     *
     * @param element 待添加元素
     */
    public void addLast(int element) {
        add(size, element);
    }

    /**
     * 向 [0 .. size] 位置添加元素
     *
     * @param index   索引位置
     * @param element 待添加元素
     */
    public void add(int index, int element) {
        checkAndGrow();

        // 添加邏輯
        if (index >= 0 && index < size) {
            // 向后挪動(dòng), 空出待插入位置
            System.arraycopy(array, index,
                    array, index + 1, size - index);
        }
        array[index] = element;
        size++;
    }

    private void checkAndGrow() {
        // 容量檢查
        if (size == 0) {
            array = new int[capacity];
        } else if (size == capacity) {
            // 進(jìn)行擴(kuò)容, 1.5 1.618 2
            capacity += capacity >> 1;
            int[] newArray = new int[capacity];
            System.arraycopy(array, 0,
                    newArray, 0, size);
            array = newArray;
        }
    }

    /**
     * 從 [0 .. size) 范圍刪除元素
     *
     * @param index 索引位置
     * @return 被刪除元素
     */
    public int remove(int index) { // [0..size)
        int removed = array[index];
        if (index < size - 1) {
            // 向前挪動(dòng)
            System.arraycopy(array, index + 1,
                    array, index, size - index - 1);
        }
        size--;
        return removed;
    }


    /**
     * 查詢?cè)?     *
     * @param index 索引位置, 在 [0..size) 區(qū)間內(nèi)
     * @return 該索引位置的元素
     */
    public int get(int index) {
        return array[index];
    }

    /**
     * 遍歷方法1
     *
     * @param consumer 遍歷要執(zhí)行的操作, 入?yún)? 每個(gè)元素
     */
    public void foreach(Consumer<Integer> consumer) {
        for (int i = 0; i < size; i++) {
            // 提供 array[i]
            // 返回 void
            consumer.accept(array[i]);
        }
    }

    /**
     * 遍歷方法2 - 迭代器遍歷
     */
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int i = 0;

            @Override
            public boolean hasNext() { // 有沒有下一個(gè)元素
                return i < size;
            }

            @Override
            public Integer next() { // 返回當(dāng)前元素,并移動(dòng)到下一個(gè)元素
                return array[i++];
            }
        };
    }

    /**
     * 遍歷方法3 - stream 遍歷
     *
     * @return stream 流
     */
    public IntStream stream() {
        return IntStream.of(Arrays.copyOfRange(array, 0, size));
    }
}

這些方法實(shí)現(xiàn)，都簡化了 index 的有效性判斷，假設(shè)輸入的 index 都是合法的

插入或刪除性能

頭部位置，時(shí)間復(fù)雜度是 O(n)

中間位置，時(shí)間復(fù)雜度是 O(n)

尾部位置，時(shí)間復(fù)雜度是 O(1)（均攤來說）

二維數(shù)組

int[][] array = {
    {11, 12, 13, 14, 15},
    {21, 22, 23, 24, 25},
    {31, 32, 33, 34, 35},
};

內(nèi)存圖如下
數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)-數(shù)組

二維數(shù)組占 32 個(gè)字節(jié)，其中 array[0]，array[1]，array[2] 三個(gè)元素分別保存了指向三個(gè)一維數(shù)組的引用
三個(gè)一維數(shù)組各占 40 個(gè)字節(jié)
它們?cè)趦?nèi)層布局上是連續(xù)的

更一般的，對(duì)一個(gè)二維數(shù)組 Array[m][n]

m 是外層數(shù)組的長度，可以看作 row 行
n 是內(nèi)層數(shù)組的長度，可以看作 column 列
當(dāng)訪問 Array[i][j]，0\leq i \lt m, 0\leq j \lt n時(shí)，就相當(dāng)于
- 先找到第 i 個(gè)內(nèi)層數(shù)組（行）
- 再找到此內(nèi)層數(shù)組中第 j 個(gè)元素（列）

小測試

Java 環(huán)境下（不考慮類指針和引用壓縮，此為默認(rèn)情況），有下面的二維數(shù)組

byte[][] array = {
    {11, 12, 13, 14, 15},
    {21, 22, 23, 24, 25},
    {31, 32, 33, 34, 35},
};

已知 array 對(duì)象起始地址是 0x1000，那么 23 這個(gè)元素的地址是什么？

答：

起始地址 0x1000

外層數(shù)組大?。?6字節(jié)對(duì)象頭 + 3元素 * 每個(gè)引用4字節(jié) + 4 對(duì)齊字節(jié) = 32 = 0x20

第一個(gè)內(nèi)層數(shù)組大?。?6字節(jié)對(duì)象頭 + 5元素 * 每個(gè)byte1字節(jié) + 3 對(duì)齊字節(jié) = 24 = 0x18

第二個(gè)內(nèi)層數(shù)組，16字節(jié)對(duì)象頭 = 0x10，待查找元素索引為 2

最后結(jié)果 = 0x1000 + 0x20 + 0x18 + 0x10 + 2*1 = 0x104a

局部性原理

這里只討論空間局部性

cpu 讀取內(nèi)存（速度慢）數(shù)據(jù)后，會(huì)將其放入高速緩存（速度快）當(dāng)中，如果后來的計(jì)算再用到此數(shù)據(jù)，在緩存中能讀到的話，就不必讀內(nèi)存了
緩存的最小存儲(chǔ)單位是緩存行（cache line），一般是 64 bytes，一次讀的數(shù)據(jù)少了不劃算啊，因此最少讀 64 bytes 填滿一個(gè)緩存行，因此讀入某個(gè)數(shù)據(jù)時(shí)也會(huì)讀取其臨近的數(shù)據(jù)，這就是所謂空間局部性

對(duì)效率的影響

比較下面 ij 和 ji 兩個(gè)方法的執(zhí)行效率

int rows = 1000000;
int columns = 14;
int[][] a = new int[rows][columns];

StopWatch sw = new StopWatch();
sw.start("ij");
ij(a, rows, columns);
sw.stop();
sw.start("ji");
ji(a, rows, columns);
sw.stop();
System.out.println(sw.prettyPrint());

ij 方法

public static void ij(int[][] a, int rows, int columns) {
    long sum = 0L;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            sum += a[i][j];
        }
    }
    System.out.println(sum);
}

ji 方法

public static void ji(int[][] a, int rows, int columns) {
    long sum = 0L;
    for (int j = 0; j < columns; j++) {
        for (int i = 0; i < rows; i++) {
            sum += a[i][j];
        }
    }
    System.out.println(sum);
}

執(zhí)行結(jié)果

0
0
StopWatch '': running time = 96283300 ns
---------------------------------------------
ns         %     Task name
---------------------------------------------
016196200  017%  ij
080087100  083%  ji

可以看到 ij 的效率比 ji 快很多，為什么呢？

緩存是有限的，當(dāng)新數(shù)據(jù)來了后，一些舊的緩存行數(shù)據(jù)就會(huì)被覆蓋
如果不能充分利用緩存的數(shù)據(jù)，就會(huì)造成效率低下

以 ji 執(zhí)行為例，第一次內(nèi)循環(huán)要讀入 [0,0] 這條數(shù)據(jù)，由于局部性原理，讀入 [0,0] 的同時(shí)也讀入了 [0,1] … [0,13]，如圖所示
數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)-數(shù)組
但很遺憾，第二次內(nèi)循環(huán)要的是 [1,0] 這條數(shù)據(jù)，緩存中沒有，于是再讀入了下圖的數(shù)據(jù)

這顯然是一種浪費(fèi)，因?yàn)?[0,1] … [0,13] 包括 [1,1] … [1,13] 這些數(shù)據(jù)雖然讀入了緩存，卻沒有及時(shí)用上，而緩存的大小是有限的，等執(zhí)行到第九次內(nèi)循環(huán)時(shí)
數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)-數(shù)組

緩存的第一行數(shù)據(jù)已經(jīng)被新的數(shù)據(jù) [8,0] … [8,13] 覆蓋掉了，以后如果再想讀，比如 [0,1]，又得到內(nèi)存去讀了

同理可以分析 ij 函數(shù)則能充分利用局部性原理加載到的緩存數(shù)據(jù)

舉一反三

I/O 讀寫時(shí)同樣可以體現(xiàn)局部性原理
數(shù)組可以充分利用局部性原理，那么鏈表呢？

答：鏈表不行，因?yàn)殒湵淼脑夭⒎窍噜彺鎯?chǔ)

越界檢查

java 中對(duì)數(shù)組元素的讀寫都有越界檢查，類似于下面的代碼

bool is_within_bounds(int index) const        
{ 
    return 0 <= index && index < length(); 
}

代碼位置：openjdk\src\hotspot\share\oops\arrayOop.hpp

只不過此檢查代碼，不需要由程序員自己來調(diào)用，JVM 會(huì)幫我們調(diào)用

練習(xí)

E01. 合并有序數(shù)組

將數(shù)組內(nèi)兩個(gè)區(qū)間內(nèi)的有序元素合并

例

[1, 5, 6, 2, 4, 10, 11]

可以視作兩個(gè)有序區(qū)間

[1, 5, 6] 和 [2, 4, 10, 11]

合并后，結(jié)果仍存儲(chǔ)于原有空間

[1, 2, 4, 5, 6, 10, 11]

方法1

遞歸

每次遞歸把更小的元素復(fù)制到結(jié)果數(shù)組

merge(left=[1,5,6],right=[2,4,10,11],a2=[]){
    merge(left=[5,6],right=[2,4,10,11],a2=[1]){
        merge(left=[5,6],right=[4,10,11],a2=[1,2]){
            merge(left=[5,6],right=[10,11],a2=[1,2,4]){
                merge(left=[6],right=[10,11],a2=[1,2,4,5]){
                    merge(left=[],right=[10,11],a2=[1,2,4,5,6]){
						// 拷貝10，11
                    }
                }
            }
        }
    }
}

代碼

public static void merge(int[] a1, int i, int iEnd, int j, int jEnd,
                              int[] a2, int k) {
    if (i > iEnd) {
        System.arraycopy(a1, j, a2, k, jEnd - j + 1);
        return;
    }
    if (j > jEnd) {
        System.arraycopy(a1, i, a2, k, iEnd - i + 1);
        return;
    }
    if (a1[i] < a1[j]) {
        a2[k] = a1[i];
        merge(a1, i + 1, iEnd, j, jEnd, a2, k + 1);
    } else {
        a2[k] = a1[j];
        merge(a1, i, iEnd, j + 1, jEnd, a2, k + 1);
    }
}

測試

int[] a1 = {1, 5, 6, 2, 4, 10, 11};
int[] a2 = new int[a1.length];
merge(a1, 0, 2, 3, 6, a2, 0);

方法2

代碼

public static void merge(int[] a1, int i, int iEnd,
                             int j, int jEnd,
                             int[] a2) {
    int k = i;
    while (i <= iEnd && j <= jEnd) {
        if (a1[i] < a1[j]) {
            a2[k] = a1[i];
            i++;
        } else {
            a2[k] = a1[j];
            j++;
        }
        k++;
    }
    if (i > leftEnd) {
        System.arraycopy(a1, j, a2, k, jEnd - j + 1);
    }
    if (j > rightEnd) {
        System.arraycopy(a1, i, a2, k, iEnd - i + 1);
    }
}

測試

int[] a1 = {1, 5, 6, 2, 4, 10, 11};
int[] a2 = new int[a3.length];
merge(a1, 0, 2, 3, 6, a2);

歸并排序代碼備份文章來源地址http://www.zghlxwxcb.cn/news/detail-465353.html

public static void split(int[] a1, int i, int j, int[] a2) {
    System.out.println("i=" + i + " j=" + j + " a1=" + Arrays.toString(Arrays.copyOfRange(a1, i, j + 1)));
    if (i == j) {
        return;
    }
    int m = (i + j) >>> 1;
    split(a1, i, m, a2);
    split(a1, m + 1, j, a2);
    //merge(a1, i, m, m+1, j, a2); // 非遞歸
    //merge(a1, i, m, m + 1, j, a2, i); // 遞歸
    System.arraycopy(a2, i, a1, i, (j - i + 1));
    System.out.println("i=" + i + " m=" + m + " j=" + j + " a1=" + Arrays.toString(a1) + " a2=" + Arrays.toString(a2));
}


int[] a1 = {1, 5, 6, 2, 4, 10, 11};
int[] a2 = new int[a1.length];
split(a1, 0, a1.length - 1, a2);
System.out.println(Arrays.toString(a1));

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)-數(shù)組的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！