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

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

一、概述


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


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 BaseAddressBaseAddress,就可以由公式 B a s e A d d r e s s + i ∗ s i z e BaseAddress + i * sizeBaseAddress+i∗size 计算出索引 i ii 元素的地址


i ii 即索引,在 Java、C 等语言都是从 0 开始

s i z e sizesize 是每个元素占用字节,例如 i n t intint 占 4 44,d o u b l e doubledouble 占 8 88

小测试


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}2

32

数组元素 + 对齐字节(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},
};


内存图如下


83da25edd94229a203d1b4390556d63c_7f1e26ae64a446beb42e6472343473c7.png


二维数组占 32 个字节,其中 array[0],array[1],array[2] 三个元素分别保存了指向三个一维数组的引用


三个一维数组各占 40 个字节


它们在内层布局上是连续的


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


m mm 是外层数组的长度,可以看作 row 行

n nn 是内层数组的长度,可以看作 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 n0≤i<m,0≤j<n时,就相当于

先找到第 i ii 个内层数组(行)

再找到此内层数组中第 j jj 个元素(列)

小测试


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],如图所示


9e97c55f4115100ac5fdd29c89432202_108bcfc0781748bca770e01b37c053f2.png


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


4e3a07632297a434ffd4737fd469fba3_eae8ed223b1f404bb374c5d5b67e2b2d.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] 这些数据虽然读入了缓存,却没有及时用上,而缓存的大小是有限的,等执行到第九次内循环时


f0a02eed14de234379310baf3fce3169_9cc6355a378b4c10acdd99eb86da5bde.png


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


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


举一反三


I/O 读写时同样可以体现局部性原理


数组可以充分利用局部性原理,那么链表呢?


答:链表不行,因为链表的元素并非相邻存储


五、越界检查


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


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


代码位置:openjdk\src\hotspot\share\oops\arrayOop.hpp

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


举一反三


I/O 读写时同样可以体现局部性原理


数组可以充分利用局部性原理,那么链表呢?


答:链表不行,因为链表的元素并非相邻存储


五、越界检查


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


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


代码位置:openjdk\src\hotspot\share\oops\arrayOop.hpp

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

相关文章
|
2月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
69 1
|
2月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
81 0
|
10月前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
1038 6
|
6月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
188 10
 算法系列之数据结构-二叉树
|
6月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
157 3
 算法系列之数据结构-Huffman树
|
6月前
|
算法 Java
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
191 22
|
6月前
|
存储 监控 算法
关于员工上网监控系统中 PHP 关联数组算法的学术解析
在当代企业管理中,员工上网监控系统是维护信息安全和提升工作效率的关键工具。PHP 中的关联数组凭借其灵活的键值对存储方式,在记录员工网络活动、管理访问规则及分析上网行为等方面发挥重要作用。通过关联数组,系统能高效记录每位员工的上网历史,设定网站访问权限,并统计不同类型的网站访问频率,帮助企业洞察员工上网模式,发现潜在问题并采取相应管理措施,从而保障信息安全和提高工作效率。
90 7
|
7月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
199 30
|
7月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
305 25
|
7月前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
282 23

热门文章

最新文章