您当前的位置:首页 > 互联网百科 > 大数据

数据结构:从原理到实战–学习笔记01

时间:2020-07-26 11:51:17  来源:  作者:

 

数组内存模型

一维数组

当定义一个数组后

int[] data = new int[5];
1

内存模型如图所示

数据结构:从原理到实战–学习笔记01

 

这种连续空间的内存模型揭示了一个重要特性:随机访问(random access)random access:可以用同等的时间访问到一组数据中的任意一个元素。

我们可以用如下代码获取数组中的值:

data[0]
1

这种从 0 开始进行索引的编码方式被称为是“Zero-based Indexing”我们可以通过以下公式获取数组特定元素:

base_address + index * date_size = target_address
1

此公式保证了,不同的数组元素达到的时间是相同的。

二维数组

一般称为一维数组为 向量(Vector) 或 表(Table),数学上称二维数组为 矩阵(Matrix)

按照以下代码声明一个矩阵:

int[][] data = new int[2][3]
1

基于这个二维数组,我们是无法确定 data[0][1]的内存地址,因为这个问题涉及到二维数组在内存中的寻址方式。其本质是 行优先(Row-Major Order) 还是 列优先(Column-Major Order)

数据结构:从原理到实战–学习笔记01

 

在行优先内存模型中,每一行的相邻元素保存在相邻的连续内存空间中,这个二维数组内存模型如下所示:

数据结构:从原理到实战–学习笔记01

 

我们可以按照以下公式获取data[i][j]里的元素:

base_address + data_size * (i * number_of_column + j)
1

在列优先内存模型中,每一列的相邻元素保存在相邻的连续内存空间中,这个二维数组内存模型如下所示:

数据结构:从原理到实战–学习笔记01

 

我们可以按照以下公式获取data[i][j]里的元素:

base_address + data_size * (i * number_of_row + j)
1

CPU 在读取内存数据的时候,通常会有一个 CPU 缓存策略。也就是说,在 CPU 读取程序指定地址的数值时,CPU 会把和它地址相邻的一些数据也一并读取并放到更高一级的缓存中,比如 L1 或者 L2 缓存。当数据存放在这种缓存上的时候,读取的速度有可能会比直接从内存上读取的速度快 10 倍以上。

数组特点

高效的访问和低效的插入删除

数组的访问时间复杂度是 O(1)

对于保存基本类型Primitive Type)的数组来说,它们的内存大小在一开始就已经确定好了,我们称它为静态数组(Static Array)。静态数组的大小是无法改变的,所以我们无法对这种数组进行插入或者删除操作。但是在使用高级语言的时候,比如 JAVA,我们知道 Java 中的 ArrayList 这种 Collection 是提供了像 add 和 remove 这样的 API 来进行插入和删除操作,这样的数组可以称之为动态数组(Dynamic Array)

为了维持数组内存中的连续性,当插入一个数据时,需要把待插入节点及之后所有的数据都拷贝,然后给数组扩容,把拷贝的数据放入待插入节点之后,最后再在待插入节点插入目标值。删除元素同理,所以插入删除时间复杂度是 O(n)



Tags:数据结构   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
1 概述数据结构和内部编码 无传统关系型数据库的 Table 模型schema 所对应的db仅以编号区分。同一 db 内,key 作为顶层模型,它的值是扁平化的。即 db 就是key的命名空间。 key...【详细内容】
2021-11-01  Tags: 数据结构  点击:(28)  评论:(0)  加入收藏
Redis常用的数据结构有 string list set zset hashstringstring 是 Redis 的基本的数据类型,一个 key 对应一个 value。string 类型是二进制安全的,Redis的string可以包含任...【详细内容】
2021-10-12  Tags: 数据结构  点击:(36)  评论:(0)  加入收藏
遵从所有教材以及各类数据结构相关的书书籍,我们先从线性表开始入门。今天这篇文章更偏概念,是关于有线性表的一个知识点的汇总。上文说过,物理结构是用于确定数据以何种方式存...【详细内容】
2021-07-19  Tags: 数据结构  点击:(94)  评论:(0)  加入收藏
1. 线性表线性表是一类最简单、最常用的数据结构。简单来说,一个线性表是n个元素的有限序列,其中n≥0,通常表示为(a1,a2,...,an)。其特点是,在非空的数据元素集合中:(1)存在唯一的一个...【详细内容】
2021-06-09  Tags: 数据结构  点击:(139)  评论:(0)  加入收藏
Mysql索引数据结构下面列举了常见的数据结构 二叉树 红黑树 Hash表 B-Tree(B树)Select * from t where t.col=5我们在执行一条查询的Sql语句时候,在数据量比较大又不加索引的情...【详细内容】
2021-06-07  Tags: 数据结构  点击:(90)  评论:(0)  加入收藏
Redis五种数据结构如下: 1.String 字符串类型是redis中最基本的数据类型,一个key对应一个value。String类型是二进制安全的,意思是 redis 的 string 可以包含任何数据。如数字,...【详细内容】
2021-04-14  Tags: 数据结构  点击:(208)  评论:(0)  加入收藏
一、栈栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈...【详细内容】
2021-04-06  Tags: 数据结构  点击:(266)  评论:(0)  加入收藏
序列是python中最基本的数据结构。所谓的序列,指的是可以连续存放多个值的内存空间,序列中的每个元素都会有一个数字,即它的位置或索引。通过这个索引就能找到序列中的元素 。...【详细内容】
2021-02-24  Tags: 数据结构  点击:(197)  评论:(0)  加入收藏
不要虚度每一天,你的经验就是这样积累出来,然后用在了你的事情上面。 一:摘要概述很多 redis 的使用者都可以清晰明白的道出Redis中常用的对象如string、list、hash、set、zset...【详细内容】
2021-01-18  Tags: 数据结构  点击:(167)  评论:(0)  加入收藏
速介绍8种常用数据结构数据结构是一种特殊的组织和存储数据的方式,可以使我们可以更高效地对存储的数据执行操作。数据结构在计算机科学和软件工程领域具有广泛而多样的用途...【详细内容】
2020-12-18  Tags: 数据结构  点击:(93)  评论:(0)  加入收藏
▌简易百科推荐
张欣安科瑞电气股份有限公司 上海嘉定 201801 摘要:随着电力行业各系统接入,海量数据涌现,如何利用电网信息化中大量数据,对客户需求进行判断分析,服务于营销链条,提升企业市场竞...【详细内容】
2021-12-14  安科瑞张欣    Tags:大数据   点击:(9)  评论:(0)  加入收藏
1、什么是数据分析结合分析工具,运用数据分析思维,分析庞杂数据信息,为业务赋能。 2、数据分析师工作的核心流程:(1)界定问题:明确具体问题是什么;●what 发生了什么(是什么)●why 为...【详细内容】
2021-12-01  逆风北极光    Tags:大数据   点击:(25)  评论:(0)  加入收藏
在实际工作中,我们经常需要整理各个业务部门发来的数据。不仅分散,而且数据量大、格式多。单是从不同地方汇总整理这些原始数据就花了大量的时间,更不用说还要把有效的数据收集...【详细内容】
2021-11-30  百数    Tags:数据   点击:(21)  评论:(0)  加入收藏
数据作为新的生产要素,其蕴含的价值日益凸显,而安全问题却愈发突出。密码技术,是实现数据安全最经济、最有效、最可靠的手段,对数据进行加密,并结合有效的密钥保护手段,可在开放环...【详细内容】
2021-11-26  炼石网络    Tags:数据存储   点击:(17)  评论:(0)  加入收藏
导读:网易大数据平台的底层数据查询引擎,选用了Impala作为OLAP查询引擎,不但支撑了网易大数据的交互式查询与自助分析,还为外部客户提供了商业化的产品与服务。今天将为大家分享...【详细内容】
2021-11-26  DataFunTalk    Tags:大数据   点击:(15)  评论:(0)  加入收藏
导读:数据挖掘是一种发现知识的手段。数据挖掘要求数据分析师通过合理的方法,从数据中获取与挖掘项目相关的知识。作者:赵仁乾 田建中 叶本华 常国珍来源:华章科技数据挖掘是一...【详细内容】
2021-11-23  华章科技  今日头条  Tags:数据挖掘   点击:(20)  评论:(0)  加入收藏
今天再给大家分享一个不错的可视化大屏分析平台模板DataColour。 data-colour 可视化分析平台采用前后端分离模式,后端架构设计采用微服务架构模式。 前端技术:Angularjs、Jq...【详细内容】
2021-11-04  web前端进阶    Tags:DashboardClient   点击:(39)  评论:(0)  加入收藏
在Kubernetes已经成了事实上的容器编排标准之下,微服务的部署变得非常容易。但随着微服务规模的扩大,服务治理带来的挑战也会越来越大。在这样的背景下出现了服务可观测性(obs...【详细内容】
2021-11-02  大数据推荐杂谈    Tags:Prometheus   点击:(40)  评论:(0)  加入收藏
同一产品对老客户的要价竟然比新客户要高?这是当下“大数据杀熟”的直接结果。近年来,随着平台经济的蓬勃发展,大数据在为用户服务之外,也引发了多种不合理现象。为了有效遏制“...【详细内容】
2021-10-29    海外网   Tags:大数据   点击:(31)  评论:(0)  加入收藏
本人03年开始从事贸易行业,多年来一直致力于外贸获客和跨境电商选品等领域,最近有些小伙伴反馈海关数据演示的都挺好为啥用起来不是那么回事?大家看到数据时关注的有产品、采购...【详细内容】
2021-10-28  QD云龙    Tags:数据   点击:(33)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条