数组概念

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

知道了数组的数据起始地址BaseAddress,就可以由公式BaseAddress+i*size计算出索引i元素的地址
·i即索引，在Java、C语言等都是从0开始
·size表示每个元素占用字节，例如int占四个字节，double占八个字节

空间占用，Java中数组结构为
·8字节 markword
·4字节 class指针(压缩class指针的情况)
·4字节 数组大小(决定了数组最大容量是2的32次方)
·数组元素+对齐字节(Java中所有对象大小都是8字节的整数倍，不足的要用对齐字节补齐)
例如
int[] array = {1,2,3,4,5}的大小为40个字节，组成如下：
8 + 4 + 4 + 5*4 + 4(alignemnt补齐字节)

动态数组基本属性

1
2
3
4
//动态数组的三个基本属性
    private int size = 0;   //逻辑大小
    private int capacity = 8;   //容量。ArrayList中的初始容量是10，Java中默认扩容1.5倍扩容
    private int[] array = {};   //没引用默认空减少内存消耗，添加第一个元素后才给容量(懒惰初始化)

添加元素

1
2
3
4
5
6
7
8
9
10
    /**
     * 向最后位置size添加新值
     *
     * @param element 待添加数的值
     */
    public void addLast(int element) {
//        array[size] = element;
//        size++;
        add(size, element);
    }

上面的代码可以被下面的代码替代，转为调用add方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 在任意索引插入新值(不可以超过size的值)
 *
 * @param index   索引位置
 * @param element 待添加元素
 */
public void add(int index, int element) {
    /*if (index >= 0 && index <= size) {
        System.arraycopy(array, index, array, index + 1, size - index);
        array[index] = element;
        size++;
    }else if(size == index){    这里就是addLast方法的变种,直接合并
        array[index] = element;
        size++;
    }*/
    //有同类项直接合并

    //容量检查
    checkAndGrow();
    //添加逻辑
    if (index >= 0 && index < size) {
        /*数组拷贝
        在array数组的index索引开始拷贝，拷贝到array中，从index+1开始拷贝，拷贝长度为size-index
        */
        System.arraycopy(array, index, array, index + 1, size - index);
        array[index] = element;
        size++;
    } else {
        //直接抛异常不走下面的语句
    }
    array[index] = element;
    size++;
}

检查容量(判定是否需要扩容)

1
2
3
4
5
6
7
8
9
10
11
12
13
private void checkAndGrow() {
        //if判断代表初始数组长度是0，懒惰初始化，只有add了才会变成默认的长度8
        if (size == 0) {
            array = new int[capacity];
        } else if (size == capacity) {  //容量检查
            //进行扩容,1.5倍,1.618倍,2倍
            capacity += capacity >> 1;
            int[] newArray = new int[capacity];
            //在array数组的0索引开始拷贝，拷贝到newArray中，从0开始拷贝，拷贝长度为size
            System.arraycopy(array, 0, newArray, 0, size);
            array = newArray;
        }
    }

删除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 删除元素
 * @param index
 * @return
 */
public int remove(int index) {   //[0..size]
    int removed = array[index];
    //在array数组的index+1开始拷贝，拷贝到array中，从index开始拷贝，拷贝长度为size-index-1
    //后面的数覆盖掉删除的数
    if (index < size - 1) {//如果在数组末尾则不需要再拷贝数组了直接删除
        System.arraycopy(array, index + 1, array, index, size - index - 1);
    }
    size--;
    return removed;
}

遍历方法

遍历方法1(常规for循环)

1
2
3
4
5
6
7
8
9
/**
 * 查询元素
 *
 * @param index 索引位置，在[0..size]区间内
 * @return 该索引位置的元素
 */
public int get(int index) { //[0...size]
    return array[index];
}

遍历方法2(函数式接口)

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 遍历方法2
 *
 * @param consumer 遍历要执行的操作，入参：每个元素
 */
public void foreach(Consumer<Integer> consumer) {  //参数传函数式接口Consumer，它可以接收一个参数并且没有返回值
    for (int i = 0; i < size; i++) {
        //consumer提供array[i]
        //返回void
        consumer.accept(array[i]);
    }
}

测试用例

1
2
3
4
5
6
7
8
9
10
11
12
13
@Test
    @DisplayName("遍历测试2")
    public void test2(){
        DynamicArray dynamicArray = new DynamicArray();
        dynamicArray.addLast(1);
        dynamicArray.addLast(2);
        dynamicArray.addLast(3);
        dynamicArray.addLast(4);

        dynamicArray.forEach((element)->{
            System.out.println(element);
        });
    }

遍历方法3(迭代器遍历)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 遍历方法3 迭代器遍历
 *
 * @return
 */
@Override
public Iterator<Integer> iterator() {
    return new Iterator<Integer>() {
        int i = 0;

        @Override
        public boolean hasNext() {  //有没有下一个元素，返回值布尔表示有没有,假不执行next退出迭代器
            return i < size;
        }

        @Override
        public Integer next() {     //返回当前元素，并移动到下一个元素
            return array[i++];
        }
    };
}

测试用例

1
2
3
4
5
6
7
8
9
10
11
12
13
@Test
    @DisplayName("遍历测试3")
    public void test3(){
        DynamicArray dynamicArray = new DynamicArray();
        dynamicArray.addLast(1);
        dynamicArray.addLast(2);
        dynamicArray.addLast(3);
        dynamicArray.addLast(4);

        for (Integer element : dynamicArray) {  //执行增强for会执行hasNext()   next方法
            System.out.println(element);
        }
    }

遍历方法4(stream流)

1
2
3
4
5
6
7
8
/**
 * 遍历方法4 stream流遍历
 *
 * @return
 */
public IntStream stream() {
    return IntStream.of(Arrays.copyOfRange(array, 0, size));//包头不包尾
}

测试用例

1
2
3
4
5
6
7
8
9
10
11
12
13
@Test
    @DisplayName("遍历测试4")
    public void test4(){
        DynamicArray dynamicArray = new DynamicArray();
        dynamicArray.addLast(1);
        dynamicArray.addLast(2);
        dynamicArray.addLast(3);
        dynamicArray.addLast(4);

        dynamicArray.stream().forEach(element->{
            System.out.println(element);
        });
    }

二维数组

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

假设寻找25，那么表示为array[1][4]
~ i=外层数组索引位置
~ j=内层数组索引位置

缓存与局部性原理

局部性原理(这里只讨论空间局部性)

~cpu读取内存(速度慢)数据后，会将其放入高数缓存(速度快)当中，如果后来的计算再用到此数据，在缓存中就能够找到的话，就不必读内存了。

~缓存的最小存储单位是缓存行(cache line)，一般是64bytes，一次只读少量数据不划算，由此最少读64bytes填满一个缓存行，由此读入某个数据时也会读取其临近的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 /**
 * ij循环效率最高
 * 因为在内存读取[0][0]时会自动给缓存读满一个缓存行(64个字节),会往下读下面的比如[0][1]、[0][2]...
 * 当cpu算到[0][1]时，因为上一次的缓存中已经有[0][1]的数据了所以直接在缓存拿不需要去内存了，由此速度极快
 * 后面以此类推，充分利用了缓存机制
 * @param a
 * @param rows
 * @param columns
 */
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效率比较低
 * 因为在内存读取[0][0]时会自动给缓存读满一个缓存行(64个字节),会往下读下面的比如[0][1]、[0][2]...
 * 但是二层循环是i自增，找的是[1][0]元素，缓存中没有，所以只能去内存里面找，也会往下读[1][1]、[1][2]...
 * 后面以此类推，假设缓存存满了，那么就会按照旧的被新的覆盖原则覆盖数据，没用上数据就被覆盖了，效率肯定低
 * @param a
 * @param rows
 * @param columns
 */
public static void ji(int[][] a,int rows, int columns){
    long sum =0L;
    for (int j = 0; j < rows; j++) {
        for (int i = 0; i < columns; i++) {
            sum += a[i][j];
        }
    }
    System.out.println(sum);
}

总结
CPU(皮秒) 缓存 内存(纳秒)
cpu要计算必须从内存中读取数据，数组存储再内存中(读)
cpu计算完会把结果写回内存(写)
由于内存跟不上cpu的运算速度，所以引用缓存概念，即先从缓存里面找数据，没有再去内存找
内存中的数据会复制一份给缓存，一般来说会一次性放64个字节放入缓存(64称为一个缓存行cache line)