对门户网站建设情况的报告,黄村网站建设公司,wordpress dux2.0,百度seo发帖推广目录概述动态数组二维数组局部性原理越界检查概述
定义
在计算机科学中#xff0c;数组是由一组元素#xff08;值或变量#xff09;组成的数据结构#xff0c;每个元素有至少一个索引或键来标识 In computer science, an array is a data structure consisting of a col…
目录概述动态数组二维数组局部性原理越界检查概述
定义
在计算机科学中数组是由一组元素值或变量组成的数据结构每个元素有至少一个索引或键来标识 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}知道了数组的数据起始地址 BaseAddressBaseAddressBaseAddress就可以由公式 BaseAddressi∗sizeBaseAddress i * sizeBaseAddressi∗size 计算出索引 iii 元素的地址
iii 即索引在 Java、C 等语言都是从 0 开始sizesizesize 是每个元素占用字节例如 intintint 占 444doubledoubledouble 占 888
小测试
byte[] array {1,2,3,4,5}已知 array 的数据的起始地址是 0x7138f94c8那么元素 3 的地址是什么 答0x7138f94c8 2 * 1 0x7138f94ca 空间占用
Java 中数组结构为
8 字节 markword4 字节 class 指针压缩 class 指针的情况4 字节 数组大小决定了数组最大容量是 2322^{32}232数组元素 对齐字节java 中所有对象大小都是 8 字节的整数倍[^12]不足的要用对齐字节补足
例如
int[] array {1, 2, 3, 4, 5};的大小为 40 个字节组成如下
8 4 4 5*4 4(alignment)随机访问性能
即根据索引查找元素时间复杂度是 O(1)O(1)O(1)
逻辑大小和物理大小
数组的物理大小是它的数组单元的总数或者说是在创建数组的时候用来指定其容量的数字。
数组的逻辑大小是它当前已供应用程序使用的项的数目。
当数组总是满的时候不用担心他俩的区别但是这种情况很少。
通常逻辑大小的物理大小会告诉我们数组状态的几件重要的事
如果逻辑大小为0数组为空则说明该数组不包含数据项如果数组包含的数据项数组最后一项的索引为逻辑大小减1如果逻辑大小等于物理大小数组已经被数据填满。
动态数组
java 版本
import java.util.Arrays;
import java.util.Iterator;
import java.util.function.Consumer;
import java.util.stream.IntStream;/*** author Ethan* date 2023/3/20* description*/
public class Ds01DynamicArray implements IterableInteger {/*** 逻辑大小*/private int size 0;/*** 容量*/private int capacity 8;/*** 初始化数组为空*/private int[] array {};/*** 向任意位置添加元素** param index 索引位置* param element 待添加元素*/public void add(int index, int element) {// 检查容量大小不够要扩容checkAndGrow();// 如果插入的位置效益逻辑大小那么要先把位置腾出来索引位置以后得元素都要后移一位if (index 0 index size) {// 向后挪动, 空出待插入位置使用数组的copy方法// 从哪书分别是源数组、源数组起始位置、目标数组、目标数组的起始位置、copy元素个数System.arraycopy(array, index,array, index 1, size - index);}// 在指定位置插入元素array[index] element;// 逻辑大小1size;}/*** 向最后位置 [size] 添加元素** param element 待添加元素*/public void addLast(int element) {// 复用任意位置添加元素插入位置是逻辑大小add(size, element);}/*** 容量检查不够进行扩容*/private void checkAndGrow() {// 容量检查if (size 0) {array new int[capacity];} else if (size capacity) {// 进行扩容, 1.5 1.618 2capacity 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];// 如果要删除的元素索引小于逻辑大小-1那么把目标索引的后面元素都向前移动一位if (index size - 1) {// 向前挪动System.arraycopy(array, index 1,array, index, size - index - 1);}// 逻辑大小-1size--;return removed;}/*** 查询元素** param index 索引位置, 在 [0..size) 区间内* return 该索引位置的元素*/public int get(int index) {return array[index];}/*** 遍历方法1** param consumer 遍历要执行的操作, 入参: 每个元素*/public void foreach(ConsumerInteger consumer) {// 使用Consumer把拿到的元素交给调用者来使用具体使用方法取决于调用者for (int i 0; i size; i) {// 提供 array[i]// 返回 voidconsumer.accept(array[i]);}}/*** 遍历方法2 - 迭代器遍历这个类要实现Iterator接口*/Overridepublic IteratorInteger iterator() {// 使用匿名内部类直接返回一个迭代器实现接口的两个方法return new IteratorInteger() {int i 0;Overridepublic boolean hasNext() { // 有没有下一个元素return i size;}Overridepublic 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},
};内存图如下 最上面的二维数组占 32 个字节其中 array[0]array[1]array[2] 三个元素分别保存了指向三个一维数组的引用 三个一维数组各占 40 个字节 它们在内层布局上是连续的
更一般的对一个二维数组 Array[m][n]Array[m][n]Array[m][n]
mmm 是外层数组的长度可以看作 row 行nnn 是内层数组的长度可以看作 column 列当访问 Array[i][j]Array[i][j]Array[i][j]0≤im,0≤jn0\leq i \lt m, 0\leq j \lt n0≤im,0≤jn时就相当于 先找到第 iii 个内层数组行再找到此内层数组中第 jjj 个元素列
小测试
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]如图所示 但很遗憾第二次内循环要的是 [1,0][1,0][1,0] 这条数据缓存中没有于是再读入了下图的数据 这显然是一种浪费因为 [0,1]...[0,13][0,1] ... [0,13][0,1]...[0,13] 包括 [1,1]...[1,13][1,1] ... [1,13][1,1]...[1,13] 这些数据虽然读入了缓存却没有及时用上而缓存的大小是有限的等执行到第九次内循环时 缓存的第一行数据已经被新的数据 [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 会帮我们调用
