文档章节

Array数组

 七英里的旅行
发布于 08/16 15:16
字数 1183
阅读 1
收藏 0

数据结构课程学习笔记。

数组概念

数组(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和主存之间的交互直接和高速缓存交互,提升性能,纵向遍历因每次循环都是不同的行,所以使缓存行没有作用。

    博客地址:https://lantaogithub.github.io

    简书:https://www.jianshu.com/u/bfb9a9657eb8

    CSDN:https://blog.csdn.net/qq_30257149

    开源中国:https://my.oschina.net/u/3948555

    掘金:https://juejin.im/user/5c8c6f00e51d456b5f17b357/activities

    思否:https://segmentfault.com/u/qifengliao_5d26ec86187b5

© 著作权归作者所有

粉丝 0
博文 10
码字总数 39523
作品 0
昌平
高级程序员
私信 提问
PHP 数组函数 汇总

1. array_filter 使用回调函数过滤数组中是值。 该函数把输入数组中的每个键值传给回调函数。 如果回调函数返回 true,则把输入数组中的当前键值返回结果数组中。数组键名保持不变。 array_...

U_KNOW
2018/01/08
0
0
PHP之数组函数

键值操作   数组的每个元素都是由键值对组成,通过元素的键名来访问对应的键值。关于键值操作有arrayvalues()、arraykeys()、inarray()、arrayflip()和array_reverse()这5个常用函数 arra...

jjjssswww
2017/06/06
0
0
PHP 数组用法

array() 函数用于创建数组。在 PHP 中,有三种类型的数组: 索引数组 - 带有数字索引的数组 关联数组 - 带有指定的键的数组 多维数组 - 包含一个或多个数组的数组 list(var1,var2...) var1 ...

林夏夕
2016/02/02
73
0
php 操作数组 (合并,拆分,追加,查找,删除等)

合并数组 array_merge()函数将数组合并到一起,返回一个联合的数组。所得到的数组以第一个输入数组参数开始,按后面数组参数出现的顺序依次迫加。其形式为: Php代码 收藏代码 array array_...

mdoo
2016/09/04
28
0
php中的数组函数学习记录2

1、检查给定的键名或索引是否存在于数组中——arraykeyexists 用法:arraykeyexists($key(mixed),$input(array))返回TRUE和FALSE $inputarray=array("1"=>"java","op"=>"R","act"=>"python"......

mrmusic
2016/03/23
54
0

没有更多内容

加载失败,请刷新页面

加载更多

最简单的获取相机拍照的图片

  import android.content.Intent;import android.graphics.Bitmap;import android.os.Bundle;import android.os.Environment;import android.provider.MediaStore;import andr......

MrLins
17分钟前
1
0
说好不哭!数据可视化深度干货,前端开发下一个涨薪点在这里~

随着互联网在各行各业的影响不断深入,数据规模越来越大,各企业也越来越重视数据的价值。作为一家专业的数据智能公司,个推从消息推送服务起家,经过多年的持续耕耘,积累沉淀了海量数据,在...

个推
19分钟前
4
0
第三方支付-返回与回调注意事项

不管是支付宝,微信,还是其它第三方支付,第四方支付,支付机构服务商只要涉及到钱的交易都要进行如下校验,全部成功了才视为成功订单 1.http请求是否成功 2.校验商户号 3.校验订单号及状态...

Shingfi
22分钟前
3
0
简述Java内存分配和回收策略以及Minor GC 和 Major GC(Full GC)

内存分配: 1. 栈区:栈可分为Java虚拟机和本地方法栈 2. 堆区:堆被所有线程共享,在虚拟机启动时创建,是唯一的目的是存放对象实例,是gc的主要区域。通常可分为两个区块年轻代和年老代。更...

DustinChan
27分钟前
4
0
Excel插入批注:可在批注插入文字、形状、图片

1.批注一直显示:审阅选项卡-------->勾选显示批注选项: 2.插入批注快捷键:Shift+F2 组合键 3.在批注中插入图片:鼠标右键点击批注框的小圆点【重点不可以在批注文本框内点击】----->调出批...

东方墨天
51分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部