数据结构基础-数组

这篇具有很好参考价值的文章主要介绍了数据结构基础-数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

数组

概述

定义

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

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}

知道了数组的数据起始地址 BaseAddress,就可以由公式 BaseAddress + i * size 计算出索引 i 元素的地址

  • i 即索引,在 Java、C 等语言都是从 0 开始
  • size 是每个元素占用字节,例如 int 占 4,double 占 8

小测试

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

已知 array 的数据的起始地址是 0x7138f94c8,那么元素 3 的地址是什么?

答:0x7138f94c8 + 2 * 1 = 0x7138f94ca

空间占用

Java 中数组结构为

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

例如

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

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

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

随机访问性能

即根据索引查找元素,时间复杂度是 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(1)(均摊来说)

二维数组

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

内存图如下
数据结构基础-数组

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

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

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

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

  • m 是外层数组的长度,可以看作 row 行
  • n 是内层数组的长度,可以看作 column 列
  • 当访问 Array[i][j],0\leq i \lt m, 0\leq j \lt n时,就相当于
    • 先找到第 i 个内层数组(行)
    • 再找到此内层数组中第 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,1] … [0,13],如图所示
数据结构基础-数组
但很遗憾,第二次内循环要的是 [1,0] 这条数据,缓存中没有,于是再读入了下图的数据
数据结构基础-数组

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

缓存的第一行数据已经被新的数据 [8,0] … [8,13] 覆盖掉了,以后如果再想读,比如 [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 会帮我们调用

练习

E01. 合并有序数组

将数组内两个区间内的有序元素合并

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

可以视作两个有序区间

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

合并后,结果仍存储于原有空间

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

方法1

递归

  • 每次递归把更小的元素复制到结果数组
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);

归并排序代码备份文章来源地址https://www.toymoban.com/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));

到了这里,关于数据结构基础-数组的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法基础(王卓)(28):排序概述(分类)、直接插入排序思路

    目录 排序分类:(本章目录) 按数据存储介质:(学习内容) 内部排序: 外部排序: 按比较器个数:(学习内容) 串行排序: 并行排序: 按主要操作:(学习内容、里面的排序都会重点学) 比较排序: 基数排序: 按辅助空间: 原地排序: 非原地排序: 按稳定性: 稳

    2023年04月26日
    浏览(40)
  • 【零基础学Rust | 基础系列 | 数据结构】元组,数组,向量,字符串,结构体

    在Rust编程语言中,数据结构是组织和存储数据的一种方式,它们使得数据可以高效地被访问和操作。本章将详细介绍元组,数组,向量,字符串,和结构体这几种基本的数据结构。 元组是Rust编程语言中的一种复合数据类型,它可以包含多个值,这些值可以是不同类型。元组

    2024年02月11日
    浏览(61)
  • 计算机基础--->数据结构(6)【AVL树(平衡二叉树)】

    平衡二叉树是一种特殊的二叉搜索树,他的左子树与右子树的高度差不超过1。并且左右两个子树都是一颗平衡二叉树。保持平衡的特性使得平衡二叉树的查询、插入和删除操作在平均和最坏情况下的时间复杂度都是 O(logn) ,其中n是树中节点的数量。 相比于普通的二叉搜索树

    2024年02月12日
    浏览(57)
  • 数据结构|基础知识定义

    1.值传递、地址传递、值返回、地址返回 1 值传递 :普通变量作为函数参数传递是单向的值传递,只是将实参的值复制一份给形参变量,形参的改变不会影响实参的值,因为所在内存空间不同 如果传递的是地址,被调函数使用指针接收,如果在被调函数中,没有更改指针指向

    2024年02月08日
    浏览(47)
  • 计算机基础--->数据结构(8)【B树、B+树<超详细图文>】

    B树(B-Tree)是一种自平衡的搜索树,又称平衡多路查找树,主要用于系统中大量数据的读和写操作。B树的特点是能保持数据有序,这使得在B树中进行查找、顺序访问、插入和删除等操作都非常高效。 B树中单一节点拥有的最多子结点的数量称为B树的阶,一个m阶B树的主要特

    2024年02月12日
    浏览(35)
  • 计算机复试面试基础知识(八股文)(数据库、数据结构、操作系统、计网、机组等)

    数据库绪论 1、简述三层模式、两级映射,分别有什么作用? 模式(逻辑模式):是数据库中全体数据的逻辑结构和特征的描述,是数据库系统模式结构的中间层,即不涉及数据的物理存储细节,也与具体应用程序开发工具语言无关。 外模式(用户模式):是用户能看见和使

    2023年04月09日
    浏览(119)
  • 数据结构--》数组和广义表:从基础到应用的全面剖析

            数据结构为我们提供了组织和处理数据的基本工具。而在这个广袤的数据结构领域中,数组和广义表是两个不可或缺的重要概念。它们作为线性结构的代表,在算法与应用中扮演着重要的角色。         无论你是初学者还是进阶者,本文将为你提供简单易懂、

    2024年02月08日
    浏览(45)
  • 算法/后端计算机基础课程如何学?——八股文基础(数据结构、计算机网络、算法导论、操作系统)

    UCB CS61B 数据结构 Stanford CS144 计网 MIT 6.006 算法导论 6.S081 操作系统 配合国内外名校的开源课件和lab 浙大 数据结构 哈工大 计网/计组/操作系统/数据库 [b站/慕课] MIT 6.824分布式系统 6.830/6.814:数据库系统 fault tolerance/心跳/选举/日志复制都是如何实现的 ? 做完labs你就有答案啦

    2024年02月02日
    浏览(56)
  • 2023届计算机保研面试基础专业问题(数据结构、算法、计算机语言、计算机网络、数据库、操作系统、数学)

    以下的专业相关基础问题,是在2022年暑期准备面试过程中,断断续续准备的,最终上岸厦大啦,也希望这些内容对后面准备保研的学弟学妹们有帮助。少即是多、快即是慢,希望大家也不必太焦虑,慢慢来比较快! 堆、栈、队列、链表等数据结构 树:红黑树、二叉树的各类

    2024年02月15日
    浏览(63)
  • 【数据结构】—— 队列基础知识以及数组模拟队列的分析、演示及优化

    ❤️一名热爱Java的大一学生,希望与各位大佬共同学习进步❤️ 🧑个人主页:@周小末天天开心 各位大佬的点赞👍 收藏⭐ 关注✅,是本人学习的最大动力 感谢! 📕该篇文章收录专栏—数据结构 目录 什么是队列? 数组模拟队列 分析 存入队列的步骤 使用数组模拟队列—

    2024年01月19日
    浏览(60)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包