【算法之旅】基础数据结构之数组

拼搏现实的明天。 2023-09-25 19:28 19阅读 0赞

![请添加图片描述][ea689b325bd64e3d99e44e943c5dbdb3.png]  
一名软件工程专业学生的算法之旅，记录自己从零开始学习数据结构与算法，从小白的视角学习数据结构：数组、对象/结构、字符串、队列、栈、树、图、堆、平衡树/线段树等，学习算法：枚举、排序、搜索、计数、分治策略、动态规划、贪心、回溯、图论、数论、字符串算法等，欢迎加入我，一起来学吧！

#### 基础数据结构之数组 ####

*   *   *  一、概述
         *  二、动态数组
         *  三、二维数组
         *  四、局部性原理
         *  五、越界检查
         *  五、越界检查

#### 一、概述 ####

**定义**：在计算机科学中，数组是由一组元素（值或变量）组成的数据结构，每个元素有至少一个索引或键来标识

> 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*

因为数组内的元素是**连续存储**的，所以数组中元素的地址，可以通过其索引计算出来，例如：

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

知道了数组的**数据**起始地址  B a s e A d d r e s s BaseAddress BaseAddress，就可以由公式  B a s e A d d r e s s + i ∗ s i z e BaseAddress + i \* size BaseAddress\+i∗size 计算出索引  i i i 元素的地址

*   i i i 即索引，在 Java、C 等语言都是从 0 开始
 *   s i z e size size 是每个元素占用字节，例如  i n t int int 占  4 4 4， d o u b l e double double 占  8 8 8

**小测试**

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

已知 array 的**数据**的起始地址是 0x7138f94c8，那么元素 3 的地址是什么？

> 答：0x7138f94c8 + 2 \* 1 = 0x7138f94ca

**空间占用**

Java 中数组结构为

*  8 字节 markword
 *  4 字节 class 指针（压缩 class 指针的情况）
 *  4 字节 数组大小（决定了数组最大容量是  2 32 2^\{32\} 232）
 *  数组元素 + 对齐字节（java中所有对象大小都是 8 字节的整数倍\[^12\]，不足的要用对齐字节补足）

例如

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

array的大小为 40 个字节，组成如下

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

**随机访问性能**

即根据索引查找元素，时间复杂度是  O ( 1 ) O(1) O(1)

#### 二、动态数组 ####

**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) {
        
                // 向后挪动, 空出待插入位置
                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) {
        
                // 进行扩容, 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) {
        
                // 向前挪动
                System.arraycopy(array, index + 1,
                        array, index, size - index - 1);
            }
            size--;
            return removed;
        }
    
    
        /**
         * 查询元素
         *
         * @param index 索引位置, 在 [0..size) 区间内
         * @return 该索引位置的元素
         */
        public int get(int index) {
        
            return array[index];
        }
    
        /**
         * 遍历方法1
         *
         * @param consumer 遍历要执行的操作, 入参: 每个元素
         */
        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() {
         // 有没有下一个元素
                    return i < size;
                }
    
                @Override
                public Integer next() {
         // 返回当前元素,并移动到下一个元素
                    return array[i++];
                }
            };
        }
    
        /**
         * 遍历方法3 - stream 遍历
         *
         * @return stream 流
         */
        public IntStream stream() {
        
            return IntStream.of(Arrays.copyOfRange(array, 0, size));
        }
    }

*  这些方法实现，都简化了 index 的有效性判断，假设输入的 index 都是合法的

**插入或删除性能**

头部位置，时间复杂度是  O ( n ) O(n) O(n)

中间位置，时间复杂度是  O ( n ) O(n) O(n)

尾部位置，时间复杂度是  O ( 1 ) O(1) O(1)（均摊来说）

#### 三、二维数组 ####

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

内存图如下

![7f1e26ae64a446beb42e6472343473c7.png][]

*  二维数组占 32 个字节，其中 array\[0\]，array\[1\]，array\[2\] 三个元素分别保存了指向三个一维数组的引用
 *  三个一维数组各占 40 个字节
 *  它们在内层布局上是**连续**的

更一般的，对一个二维数组  A r r a y \[ m \] \[ n \] Array\[m\]\[n\] Array\[m\]\[n\]

*   m m m 是外层数组的长度，可以看作 row 行
 *   n n n 是内层数组的长度，可以看作 column 列
 *  当访问  A r r a y \[ i \] \[ j \] Array\[i\]\[j\] Array\[i\]\[j\]， 0 ≤ i < m , 0 ≤ j < n 0\\leq i \\lt m, 0\\leq j \\lt n 0≤i<m,0≤j<n时，就相当于
    
     *  先找到第  i i i 个内层数组（行）
     *  再找到此内层数组中第  j j j 个元素（列）

**小测试**

Java 环境下（不考虑类指针和引用压缩，此为默认情况），有下面的二维数组

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

已知 array **对象**起始地址是 0x1000，那么 23 这个元素的地址是什么？

> 答：
> 
>  *  起始地址 0x1000
>  *  外层数组大小：16字节对象头 + 3元素 \* 每个引用4字节 + 4 对齐字节 = 32 = 0x20
>  *  第一个内层数组大小：16字节对象头 + 5元素 \* 每个byte1字节 + 3 对齐字节 = 24 = 0x18
>  *  第二个内层数组，16字节对象头 = 0x10，待查找元素索引为 2
>  *  最后结果 = 0x1000 + 0x20 + 0x18 + 0x10 + 2\*1 = 0x104a

#### 四、局部性原理 ####

这里只讨论空间局部性

*  cpu 读取内存（速度慢）数据后，会将其放入高速缓存（速度快）当中，如果后来的计算再用到此数据，在缓存中能读到的话，就不必读内存了
 *  缓存的最小存储单位是缓存行（cache line），一般是 64 bytes，一次读的数据少了不划算啊，因此最少读 64 bytes 填满一个缓存行，因此读入某个数据时也会读取其**临近的数据**，这就是所谓**空间局部性**

**对效率的影响**

比较下面 ij 和 ji 两个方法的执行效率

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);
    }

执行结果

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

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

*  缓存是有限的，当新数据来了后，一些旧的缓存行数据就会被覆盖
 *  如果不能充分利用缓存的数据，就会造成效率低下

以 ji 执行为例，第一次内循环要读入  \[ 0 , 0 \] \[0,0\] \[0,0\] 这条数据，由于局部性原理，读入  \[ 0 , 0 \] \[0,0\] \[0,0\] 的同时也读入了  \[ 0 , 1 \] . . . \[ 0 , 13 \] \[0,1\] ... \[0,13\] \[0,1\]...\[0,13\]，如图所示

![在这里插入图片描述][108bcfc0781748bca770e01b37c053f2.png]

但很遗憾，第二次内循环要的是  \[ 1 , 0 \] \[1,0\] \[1,0\] 这条数据，缓存中没有，于是再读入了下图的数据

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-e5mI6NGt-1679804958775)(.\\imgs\\image-20221104164716282.png)\]][img-e5mI6NGt-1679804958775_._imgs_image-20221104164716282.png]

这显然是一种浪费，因为  \[ 0 , 1 \] . . . \[ 0 , 13 \] \[0,1\] ... \[0,13\] \[0,1\]...\[0,13\] 包括  \[ 1 , 1 \] . . . \[ 1 , 13 \] \[1,1\] ... \[1,13\] \[1,1\]...\[1,13\] 这些数据虽然读入了缓存，却没有及时用上，而缓存的大小是有限的，等执行到第九次内循环时

![在这里插入图片描述][9cc6355a378b4c10acdd99eb86da5bde.png]

缓存的第一行数据已经被新的数据  \[ 8 , 0 \] . . . \[ 8 , 13 \] \[8,0\] ... \[8,13\] \[8,0\]...\[8,13\] 覆盖掉了，以后如果再想读，比如  \[ 0 , 1 \] \[0,1\] \[0,1\]，又得到内存去读了

同理可以分析 ij 函数则能充分利用局部性原理加载到的缓存数据

**举一反三**

1.  I/O 读写时同样可以体现局部性原理
2.  数组可以充分利用局部性原理，那么链表呢？
    
    > 答：链表不行，因为链表的元素并非相邻存储

#### 五、越界检查 ####

java 中对数组元素的读写都有越界检查，类似于下面的代码

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

*  代码位置：`openjdk\src\hotspot\share\oops\arrayOop.hpp`

只不过此检查代码，不需要由程序员自己来调用，JVM 会帮我们调用

**举一反三**

1.  I/O 读写时同样可以体现局部性原理
2.  数组可以充分利用局部性原理，那么链表呢？
    
    > 答：链表不行，因为链表的元素并非相邻存储

#### 五、越界检查 ####

java 中对数组元素的读写都有越界检查，类似于下面的代码

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

*  代码位置：`openjdk\src\hotspot\share\oops\arrayOop.hpp`

只不过此检查代码，不需要由程序员自己来调用，JVM 会帮我们调用

[ea689b325bd64e3d99e44e943c5dbdb3.png]: https://img-blog.csdnimg.cn/ea689b325bd64e3d99e44e943c5dbdb3.png
[7f1e26ae64a446beb42e6472343473c7.png]: https://img-blog.csdnimg.cn/7f1e26ae64a446beb42e6472343473c7.png
[108bcfc0781748bca770e01b37c053f2.png]: https://img-blog.csdnimg.cn/108bcfc0781748bca770e01b37c053f2.png
[img-e5mI6NGt-1679804958775_._imgs_image-20221104164716282.png]: https://img-blog.csdnimg.cn/eae8ed223b1f404bb374c5d5b67e2b2d.png
[9cc6355a378b4c10acdd99eb86da5bde.png]: https://img-blog.csdnimg.cn/9cc6355a378b4c10acdd99eb86da5bde.png