数组--数据结构--黑马

devtools/2024/9/24 20:39:29/

数组

定义

数组有一组元素(值或变量)组成的数据结构,每个元素有至少一个索引或键来标识

数组内的元素是连续存储的,所以数组中元素的地址可以通过索引计算出来,例如,

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

当知道数组中0索引的地址,假设为 b b b,那么索引为1的地址为 b + 4 b+4 b+4 ,因为是整数数组,一个元素占用4个字节,其他索引的地址是 b + s i z e ∗ i b + size*i b+sizei ,其中 s i z e size size 为整数占用字节大小4。

由此,知道数组的数据起始地址 B a s e A d d r e s s BaseAddress BaseAddress ,可由公式 B a s e A d d r e s s + s i z e ∗ i BaseAddress+size*i BaseAddress+sizei 计算出索引 i i i 处的元素地址

  • i i i 即为索引,在Java、C等语言中索引从0开始;
  • s i z e size size 为每个元素占用的字节大小,例如, i n t int int 占4个字节, d o u b l e double double 占8个字节, c h a r char char 占一个字节, s h o r t short short 占2个字节等,如下所示。
    在这里插入图片描述

小测试

java">byte[] array = {1, 2, 3, 4, 5};

已知array的数据的起始地址为 0 x 7138 f 94 c 8 0x7138f94c8 0x7138f94c8 ,那么索引为2元素为3的地址为多少?

因为是byte,则一个元素占用一个字节,索引为2的地址为起始地址 + 2 * 1,即, 0 x 7138 f 94 c 8 + 2 ∗ 1 = 0 x 7138 f 94 c a 0x7138f94c8 + 2 * 1 = 0x7138f94ca 0x7138f94c8+21=0x7138f94ca ,因为是十六进制,索引8+2为10,即为a,

性能

空间占用

Java中的数据结构

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

例如

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

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

java">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 = new int[capacity];private int[] array = {};  // 初始,空数组占用空间比开始长度为capacity的数组占用空间小,在添加元素检查时,初始化容量为capacity的数组// 尾部添加元素public void addLast(int vlaue) {add(size, value);}// 在指定索引位置插入元素pubic void add(int index, int value) {if (index < 0 || index > size) {System.out.println("索引错误");}// 检查数组容量是否满,size == capacitycheckAndGrow();if (index >= 0 && index < size) {System.arraycopy(array, index, array, index + 1, size - index);}  array[index] = value;size++;}// 删除指定索引的元素public int remove(int index) {int value = array[index];if  (index < size - 1) {System.arraycopy(array, index + 1, array, index, size - index - 1);}size--;return value;}// 根据索引查找元素public int get(int index) {return array[index];}// 遍历数组元素,使用foreachpublic void foreach() {for(int i = 0; i < size; i++) {System.out.println(i);}}// 遍历方法1 使用函数式接口作为参数传递public void foreach1(Consumer<Integer> consumer) {for(int i = 0; i < size; i++) {consumer.accept(array[i]);}}// 遍历方法2 迭代器遍历@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {int index = 0;@Overridepublic boolean hasNext() {  // 是否有下一个元素return index < size;}@Overridepublic Integer next() {  // 返回当前索引元素,并移动到下一个元素return array[index++];}};}// 遍历方法3 使用流的方法public IntStream stream() {return IntStream.of(Array.copyOfRange(array, 0, size)); // 拷贝左闭右开}// 检查容量是否满public void checkAndGrow() {if (size == 0) {return new int[capacity];}if (size == capacity) {// 进行扩容capacity += capacity >> 1;int[] newArray = new int[capacity];System.arraycopy(array, 0, newArray, 0, size);array = newArray;}}}

性能

查询

根据索引查询元素,时间复杂度为 O ( 1 ) O(1) O(1) ;

插入或删除

头部插入,时间复杂度 O ( n ) O(n) O(n)

中间插入,时间复杂度 O ( n ) O(n) O(n)

尾部插入,时间复杂度 O ( 1 ) O(1) O(1)

二维数组

java">int[][] array = {{11, 12, 13, 1415},{21, 22, 23, 2425},{31, 32, 33, 34, 35},
};

在这里插入图片描述

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

局部性原理

只讨论空间局限性

  • cpu读取内存数组后,会将其放入到高速缓存中(速度快),如果后面的计算使用到此数据,只需要到高速缓存中获取,不需要到内存中读取,从而节省时间。
    个字节,其中 array[0],array[1],array[2] 三个元素分别指向三个一维数组的引用;
  • 三个一维数组占用40个字节
  • 它们在内存布局上是连续

局部性原理

只讨论空间局限性

  • cpu读取内存数组后,会将其放入到高速缓存中(速度快),如果后面的计算使用到此数据,只需要到高速缓存中获取,不需要到内存中读取,从而节省时间。
  • 缓存的最小存储单元为一个缓存行(cache line), 一般为64bytes,一次读取数据若少不划算,因此最少读64bytes填满缓存行,因此在读取某个数据时,会将临近数据一起读取,即为空间局部性

http://www.ppmy.cn/devtools/94217.html

相关文章

训练 Transfomer 模型的内存消耗计算

目录 model 内存gradients 内存activates 内存 经典图打底&#xff1a; 训练深度模型的内存消耗主要有以下几个部分&#xff1a; 存储模型可训练参数存储梯度存储反向传播中间变量&#xff0c;例如&#xff1a; L ( Y − Y ^ ) 2 Y ^ X T W ∂ L ∂ W − 2 ( Y − Y ^ ) …

mesh格式转换:glb转ply——使用Blender烘焙贴图到顶点色

1. 导入glb文件 选择shading后&#xff0c;选中物体&#xff0c;就能看到下面的节点树。 2. 创建顶点颜色 这个时候我们可以看到模型的顶点颜色是纯白色的。 2. 将贴图付给材质 原来&#xff1a; 现在&#xff1a; 3. 切换渲染器并烘焙顶点颜色 第三行选择CPU渲染或者GPU…

前端纯数组转树形结构

问题描述 前端需要处理后端返回的数据&#xff0c;展示如下。 解决方式 因为使用ProTable组件&#xff0c;那么数据只要携带children字段&#xff0c;就可以如上图展示。 方式一&#xff1a;后端返回数据的时候&#xff0c;直接封装好&#xff0c;如下&#xff1a; const…

Nginx异常关闭之中了挖矿病毒kswapd0

问题描述&#xff1a;系统突然无法访问了&#xff0c;登录服务器看了一下是因为Nginx服务关闭&#xff0c;重启后过了几天仍然异常关闭 系统&#xff1a;CentOS 7&#xff0c;Nginx 1.20 尝试解决过程&#xff1a;1、查询nginx/logs/error.log、系统日志&#xff0c;都没有查…

Springboot 级联json数据写入Mysql数据库

在Spring Boot应用程序中&#xff0c;将级联JSON数据写入MySQL数据库通常涉及使用JPA&#xff08;Java Persistence API&#xff09;和Hibernate进行实体关系映射。以下是一个完整的示例&#xff0c;包括如何定义实体、配置级联关系、处理JSON数据并将其保存到数据库中。 目录…

MySQL 存储引擎之InnoDB

InnoDB 存储引擎是一个非常重要的组件&#xff0c;它提供了许多高级特性&#xff0c;如事务支持、行级锁定、多版本并发控制 (MVCC) 和外键约束等。InnoDB 是 MySQL 5.5 及更高版本中的默认存储引擎&#xff0c;并且被广泛应用于需要高可靠性和并发性的应用程序中。 InnoDB 的…

汽车补光照明实验太阳光模拟器光源

汽车补光照明实验概览 汽车补光照明实验是汽车照明领域的一个重要环节&#xff0c;它涉及到汽车照明系统的性能测试和优化。实验的目的在于确保汽车在各种光照条件下都能提供良好的照明效果&#xff0c;以提高行车安全。实验内容通常包括但不限于灯光的亮度、色温、均匀性、响应…

uniapp3.0实现图片上传公用组件上传uni-file-picker,uni.uploadFile

用uniapp3.0的写法组合式api&#xff0c;setup形式封装一个图片上传公用组件&#xff0c;要求 1、使用uni-file-picker选择文件 2、uni.uploadFile上传图片 3、要能支持上传接口动态化 4、支持删除如片列表中已上传项 5、可以预览已上传列表图片 6、支持动态化限制图片格…