定义
在计算机科学中,数组是由一组元素(值或变量)组成的数据结构,每个元素有至少一个索引或键来标识
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}
知道了数组的数据起始地址
,就可以由公式
计算出索引
元素的地址
即索引,在 Java、C 等语言都是从 0 开始
是每个元素占用字节,例如
占
,
占
小测试
byte[] array = {1,2,3,4,5}
已知 array 的数据的起始地址是 0x7138f94c8,那么元素 3 的地址是什么?
答:0x7138f94c8 + 2 * 1 = 0x7138f94ca
空间占用
Java 中数组结构为
)
例如
int[] array = {1, 2, 3, 4, 5};
的大小为 40 个字节,组成如下
8 + 4 + 4 + 5*4 + 4(alignment)
随机访问性能
即根据索引查找元素,时间复杂度是
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));
}
}
插入或删除性能
头部位置,时间复杂度是
中间位置,时间复杂度是
尾部位置,时间复杂度是
(均摊来说)
int[][] array = {
{11, 12, 13, 14, 15},
{21, 22, 23, 24, 25},
{31, 32, 33, 34, 35},
};
内存图如下
更一般的,对一个二维数组
是外层数组的长度,可以看作 row 行
是内层数组的长度,可以看作 column 列
,
时,就相当于
个内层数组(行)
个元素(列)
小测试
Java 环境下(不考虑类指针和引用压缩,此为默认情况),有下面的二维数组
byte[][] array = {
{11, 12, 13, 14, 15},
{21, 22, 23, 24, 25},
{31, 32, 33, 34, 35},
};
已知 array 对象起始地址是 0x1000,那么 23 这个元素的地址是什么?
答:
这里只讨论空间局部性
对效率的影响
比较下面 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 执行为例,第一次内循环要读入
这条数据,由于局部性原理,读入
的同时也读入了
,如图所示
但很遗憾,第二次内循环要的是
这条数据,缓存中没有,于是再读入了下图的数据
这显然是一种浪费,因为
包括
这些数据虽然读入了缓存,却没有及时用上,而缓存的大小是有限的,等执行到第九次内循环时
缓存的第一行数据已经被新的数据
覆盖掉了,以后如果再想读,比如
,又得到内存去读了
同理可以分析 ij 函数则能充分利用局部性原理加载到的缓存数据
举一反三
java 中对数组元素的读写都有越界检查,类似于下面的代码
bool is_within_bounds(int index) const
{
return 0 <= index && index < length();
}
openjdk\src\hotspot\share\oops\arrayOop.hpp
只不过此检查代码,不需要由程序员自己来调用,JVM 会帮我们调用
将数组内两个区间内的有序元素合并
例
[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 > iEnd) {
System.arraycopy(a1, j, a2, k, jEnd - j + 1);
}
if (j > jEnd) {
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);