Array数组的概念和用法

这篇文章主要介绍“Array数组的概念和用法”，在日常操作中，相信很多人在Array数组的概念和用法问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”Array数组的概念和用法”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

成都创新互联公司是由多位在大型网络公司、广告设计公司的优秀设计人员和策划人员组成的一个具有丰富经验的团队，其中包括网站策划、网页美工、网站程序员、网页设计师、平面广告设计师、网络营销人员及形象策划。承接：成都做网站、成都网站制作、成都外贸网站建设、网站改版、网页设计制作、网站建设与维护、网络推广、数据库开发,以高性价比制作企业网站、行业门户平台等全方位的服务。

数据结构课程学习笔记。

数组概念

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据, 并且不支持动态扩容。

• 线性表

  线性表就是数据排成一条线一样的数据结构，每个线性表最多只有前后两个方向，数组，链表丶队列丶栈等都是线性表数据结构。

• 非线性表

  非线性表就是数据不规则，与线性表是相对立的，比如二叉树丶堆丶等，在非线性表中，数据之间并不是简单的前后关系。

数组随机访问

• 公式

  address[i] = base_address + i * data_type_size

  address[i] :下标 i 的地址值。

  base_address：数组的首地址。

  data_type_size：数组中每个元素的大小，也就是数据类型大小(字节)，例如int是4个字节。

数组的增加和删除

数组(Array) 在增删查这三个动作中，查询是高效的，但是增和删是低效的，查询高效是因为数组支持随机访问，时间复杂度是 O(1),这里就不多赘述了，但是在增加和删除的动作中，因为会涉及数据搬移，所以时间复杂度是 O(n)，下面来详细讲解。

• 低效的"插入"和"删除"

  	int[] info = new int[6];

  插入

  数组 info是一个一维数组，其内容是 33,44,66,77,88现在需要在下标 2的位置插入55，将其变成33 44 55 66 77 88的数组，这其中涉及将下标 2到下标 4的之间进行数据进行搬移，完成后在下标 2的位置插入 55, 其复杂度是 O(n)， 但如果是在最后进行插入的话其复杂度是 O(1)。

  

  删除

  还拿数组 info来举例，数组删除前其内容是 33,44,00,55,66,77现在进行删除操作，删除下标为 2内容，这其中涉及将下标 3 到 5 的内容向前搬移，其操作的时间复杂度是 O(n)，如果是是删除最后一位且后面没有内容，则其时间复杂度是O(1)。

  

  因插入和删除操作会涉及到数据搬移,所以说他是低效的。

  CPU缓存**

  Cpu缓存的最小单位是Cpu缓存行，一个缓存行大小通常是64字节(取决于CPU)，试想一下你正在遍历一个长度为 16 的 long 数组 data[16]，原始数据自然存在于主内存中，访问过程描述如下：

  1：访问 data[0]，CPU core 尝试访问 CPU Cache，未命中。

  2：尝试访问主内存，操作系统一次访问的单位是一个 Cache Line 的大小 — 64 字节，这意味着：既从主内存中获取3：到了 data[0] 的值，同时将 data[0] ~ data[7] 加入到了 CPU Cache 之中，

  4：访问 data[1]~data[7]，CPU core 尝试访问 CPU Cache，命中直接返回。

  5：访问 data[8]，CPU core 尝试访问 CPU Cache，未命中, 尝试访问主存，重复步骤2。

  测试数组和Cpu缓存行

  因Cpu缓存最小单位是缓存行(64字节)，我么来测试一下二维数组的横向遍历和纵向遍历的具体时间和性能。

  代码

  package com.com.array;
  
  /**
   * @Auther: lantao
   * @Date: 2019-06-24 15:52
   * @Company: 随行付支付有限公司
   * @maill: lan_tao@suixingpay.com
   * @Description: TODO
   */
  public class ArrayTest {
  
      static long[][] arr;
  
      public static void main(String[] args) {
          long sum = 0L;
          arr = new long[1024 * 1024][10];
          // 横向遍历
          long l = System.currentTimeMillis();
          for (int i = 0; i < 1024 * 1024; i++) {
              for (int j = 0; j < 10; j++) {
                  sum += arr[i][j];
              }
          }
          System.out.println("Loop Time 横向遍历：" + (System.currentTimeMillis() - l) + "ms");
  
          long l1 = System.currentTimeMillis();
          // 纵向遍历
          for (int i = 0; i < 10; i++) {
              for (int j = 0; j < 1024 * 1024; j++) {
                  sum += arr[j][i];
              }
          }
          System.out.println("Loop Time 纵向遍历：" + (System.currentTimeMillis() - l) + "ms");
      }
  }

• 结果：
  Loop Time 横向遍历：14ms
  Loop Time 纵向遍历：83ms

• 总结：因横向遍历遍历的是行，然后在循环行的每一列，Cpu缓存会缓存64字节大小的缓存行，所以可以减少cpu和主存之间的交互，直接和高速缓存交互，提升性能，纵向遍历因每次循环都是不同的行，所以使缓存行没有作用。

到此，关于“Array数组的概念和用法”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注创新互联网站，小编会继续努力为大家带来更多实用的文章！