數(shù)組

一、定義

在計算機科學中，數(shù)組是由一組元素（值或變量）組成的數(shù)據(jù)結構，每個元素有至少一個索引或鍵來標識

因為數(shù)組內的元素是連續(xù)存儲的，所以數(shù)組中元素的地址，可以通過其索引計算出來，例如：int[] array = {1,2,3,4,5}

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

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

二、空間占用

Java 中數(shù)組結構為

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

int[] array = {1, 2, 3, 4, 5};的大小為 40 個字節(jié)，組成如下

image.png

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

數(shù)組隨機訪問性能：即根據(jù)索引查找元素，時間復雜度是 O(1)

三、動態(tài)數(shù)組

動態(tài)數(shù)組的增刪改查

package com.hcx.algorithm.arr;

import java.util.Arrays;
import java.util.Iterator;
import java.util.function.Consumer;
import java.util.stream.IntStream;

/**
 * @Title: DynamicArray.java
 * @Package com.hcx.algorithm.arr
 * @Description: 動態(tài)數(shù)組
 * @Author: hongcaixia
 * @Date: 2024/12/26 17:02
 * @Version V1.0
 */
public class DynamicArray implements Iterable<Integer>{

    // 邏輯大小
    private int size = 0;

    // 容量
    private int capacity = 8;

    private int[] arr = {};

    /**
     * 往最后位置插入元素
     * @param element
     */
    public void addLast(int element) {
//        arr[size] = element;
//        size++;
        addIndex(size, element);
    }

    /**
     * 按照索引添加元素
     * @param index
     * @param element
     */
    public void addIndex(int index, int element) {

        //檢查容量
        checkAndGrow();

        if(index>0 && index<size){
            System.arraycopy(arr,index,arr,index+1,size-index);
        }
        arr[index]=element;
        size++;
    }

    /**
     * 檢查容量并擴容
     */
    private void checkAndGrow() {
        //第一次添加 創(chuàng)建初始容量的數(shù)組
        if (size == 0) {
            arr = new int[capacity];
        } else if (size == capacity) {
            //擴容為原來的1.5倍
            capacity += capacity >> 1;
            int[] newArr = new int[capacity];
            System.arraycopy(arr, 0, newArr, 0, size);
            arr = newArr;
        }
    }

    /**
     * 根據(jù)索引移除元素
     * @param index
     * @return
     */
    public int remove(int index) {
        int removed = arr[index];

        // 不是最后一個元素才需要移動
        if (index < size - 1) {
            System.arraycopy(arr, index + 1, arr, index, size - index - 1);
        }
        size--;
        return removed;
    }



    /**
     * 遍歷數(shù)組
     * @param consumer
     */
    public void foreach(Consumer<Integer> consumer){
        for (int i = 0; i < size; i++) {
            consumer.accept(arr[i]);
        }
    }

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

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

            //返回當前元素，指針移動到下一個元素
            @Override
            public Integer next() {
                return arr[i++];
            }
        };
    }

    /**
     * stream 遍歷
     * @return
     */
    public IntStream stream() {
        return IntStream.of(Arrays.copyOfRange(arr, 0, size));
    }
}

插入或刪除性能
頭部位置，時間復雜度是 O(n)
中間位置，時間復雜度是 O(n)
尾部位置，時間復雜度是 O(1)（均攤來說）

四、二維數(shù)組

int[][] array = {
    {11, 12, 13, 14, 15},
    {21, 22, 23, 24, 25},
    {31, 32, 33, 34, 35},
};
內存圖.png
  • 二維數(shù)組占 32 個字節(jié)，其中 array[0]，array[1]，array[2] 三個元素分別保存了指向三個一維數(shù)組的引用
  • 三個一維數(shù)組各占 40 個字節(jié)
  • 它們在內層布局上是連續(xù)的

對一個二維數(shù)組 Array[m][n]

  • m 是外層數(shù)組的長度，可以看作 row 行
  • n 是內層數(shù)組的長度，可以看作 column 列
  • 當訪問 Array[i][j]，0\leq i \lt m, 0\leq j \lt n時，就相當于
    • 先找到第 i 個內層數(shù)組（行）
    • 再找到此內層數(shù)組中第 j 個元素（列）
byte[][] array = {
    {11, 12, 13, 14, 15},
    {21, 22, 23, 24, 25},
    {31, 32, 33, 34, 35},
};

已知 array 對象起始地址是 0x1000，那么 23 這個元素的地址:

  • 起始地址 0x1000
  • 外層數(shù)組大小：16字節(jié)對象頭 + 3元素 * 每個引用4字節(jié) + 4 對齊字節(jié) = 32 = 0x20
  • 第一個內層數(shù)組大?。?6字節(jié)對象頭 + 5元素 * 每個byte1字節(jié) + 3 對齊字節(jié) = 24 = 0x18
  • 第二個內層數(shù)組，16字節(jié)對象頭 = 0x10，待查找元素索引為 2
  • 最后結果 = 0x1000 + 0x20 + 0x18 + 0x10 + 2*1 = 0x104a

五、局部性原理

只討論空間局部性

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

對效率的影響
比較 ij 和 ji 兩個方法的執(zhí)行效率

public class TestCacheLine {

    /**
     * 二維數(shù)組遍歷，先行后列
     * @param a
     * @param rows
     * @param cols
     */
    public static void ij(int[][] a, int rows, int cols) {
        long sum = 0L;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                sum += a[i][j];
            }
        }
        System.out.println(sum);
    }

    /**
     * 二維數(shù)組遍歷，先列后行
     * @param a
     * @param rows
     * @param cols
     */
    public static void ji(int[][] a, int rows, int cols) {
        long sum = 0L;
        for (int j = 0; j < cols; j++) {
            for (int i = 0; i < rows; i++) {
                sum += a[i][j];
            }
        }
        System.out.println(sum);
    }

    public static void main(String[] args) {
        int rows = 1000000;
        int cols = 15;
        int[][] arr = new int[rows][cols];
        StopWatch sw = new StopWatch();
        sw.start();
        ij(arr, rows, cols);
        sw.stop();
        System.out.println("=====ij: "+sw.getElapsedTimeInNanos());  //15531671

        sw.start();
        ji(arr, rows, cols);
        sw.stop();

        System.out.println("=====ji: "+sw.getElapsedTimeInNanos()); // 77156768

    }
}

ij 的效率比 ji 快很多:

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

以 ji 執(zhí)行為例，第一次內循環(huán)要讀入 [0,0] 這條數(shù)據(jù)，由于局部性原理，讀入 [0,0] 的同時也讀入了 [0,1] ... [0,13]，如圖所示（但是這個數(shù)據(jù)對于ij的執(zhí)行，是用上了的）

image.png

但很遺憾，第二次內循環(huán)要的是 [1,0] 這條數(shù)據(jù)，緩存中沒有，于是再讀入了下圖的數(shù)據(jù)

image.png

因為 [0,1] ... [0,13] 包括 [1,1] ... [1,13] 這些數(shù)據(jù)雖然讀入了緩存，卻沒有及時用上，而緩存的大小是有限的，等執(zhí)行到第九次內循環(huán)時

image.png

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

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

六、越界檢查

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

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

此檢查代碼，不需要由程序員自己來調用，JVM 會幫我們調用

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

友情鏈接更多精彩內容