衡水信息港:一本正经的聊数据结构(2):数组与向量

admin 2个月前 (10-04) 科技 87 1

前文传送门:

一本正经的聊数据结构(1):时间庞大度

弁言

这个系列没有死,我还在更新。

最近事情太多了,这篇文章也是断断续续写了好几天才凑完。

上一篇我们先容了一个基础观点「时间庞大度」,这篇我们来看第一个真正意义上的数据结构「数组」。

那为什么题目中还会有一个向量呢?这个是什么器械?

不要急,且听我逐步道来。

内存

在聊数组之前,需要先领会一个硬件,这个就是我们电脑上内存。

先领会一下内存的物理组织,一样平常内存的形状都长这样:

上面那一个一个的小黑块就是内存颗粒,我们的数据就是存放在谁人内存颗粒内里的。

每一个内存颗粒叫做一个 chip 。每个 chip 内部,是由 8 个 bank 组成的。大致长这样(灵魂画手挖掘机先生最先上线):

而每一个 bank 是一个二维平面上的矩阵,矩阵中每一个元素中都是保留了 1 个字节,也就是 8 个 bit ,好比这样:

以是准确的来讲,我们的数据就是放在那一个一个的元素中的。

数组

在 C 、C++ 、Java ,都将数组作为一个基础的数据类型内置。

很可惜,在 Python 中未将数组作为一个基础的数据类型,虽然 Python 中的 list 和数组很像,然则我更愿意叫它列表,而不是数组。

那么数组究竟是啥呢,我这里借用下邓俊辉先生「数据结构」中的界说:

若聚集 S 由 n 个元素组成,且各元素之间具有一个线性顺序,则可将它们存放于起始于地址 A 、物理位置延续的一段存储空间,并统称作数组( array ) ,通常以 A 作为该数组的标识。详细地,数组 A[] 中的每一元素都唯一对应于某一下标编号,在多数高级程序设计语言中,一样平常都是从 0 最先编号,依次是 0 号、 1 号、 2 号、 ...、 n - 1 号元素。

其中,对于任何 0 <= i < j < n , A[i] 都是 A[j] 的前驱( predecessor ) , A[j] 都是 A[i] 的后继( successor ) 。特别地,对于任何 i >= 1, A[i - 1] 称作 A[i] 的直接前驱( intermediatep redecessor ) ;对于任何 i <= n - 2 , A[i + 1] 称作 A[i] 的直接后继( intermediate successor ) 。 任一元素的所有前驱组成其前缀( prefix ) ,所有后继组成其后缀( suffix ) 。

观点永远都是这么的死板、乏味以及看不懂。

没关系,继续我的非本职工作「灵魂画手」。

首先领会第一个知识点,数组是放在内存里的,内存的结构我们前面先容过了,那么数组简朴明白就是放在一个一个格子里的,就像这样:

现实上不是这么放的哈,简朴明白可以先这么明白,这个涉及到内存对齐的知识,有兴趣的同砚可以度娘领会下。

便于明白,我在字母 A 后面加上了数字,这个数字明白为编号,并且是从 0 最先的。

这个结构让我想起了糖葫芦:

数组中的数字就像是穿在棍子上的山楂,大晚上的看的有点流口水。

前驱和后继可以看下面这张图:

A3 是 A4 的直接前驱, A5 是 A4 的直接后继,而排在 A4 前面的都叫 A4 的前驱,排在 A4 后面的都叫 A4 的后继。

向量

那么啥是向量( vector )呢?

这个器械可以简朴明白为数组的升级版,在种种编程语言中,大多数都对向量的实现做了内置,不外很可惜,在 Python 中,向量未成为一个基础的数据结构。

那么我就只能对照着 Java 来聊了,向量这个数据结构在 Java 中的实现是:java.util.Vector ,用过 Vector 的应该都是上古程序员了,这个工具类是随同 JDK1.0 就有的,然则后面逐渐的弃用,缘故原由我们后面有机遇再聊,就不在这多说了。

第一个要聊的问题是,我们在使用数组的时刻有什么不方便的地方?这个问题换一种问法,实在就是为什么我们需要使用向量(vector)。

首先,我们在使用数组的时刻,需要声明数组的巨细,由于程序需要凭据我们声明的数组巨细去向内存申请空间,这就很尴尬了,若是在一个我并不清晰后续可能会用若干空间的场景中,我就没有办法去声明一个数组,由于数组是定长的。

然后就是数组需要是统一数据类型,好比我一个数组若是放入了数组,那么就不能再放入字符串,就不提加倍庞大的数据结构,这完全都是由于数组的特征决议的,由于数组在内存上是延续的。

那么遇到了上面的问题怎么办,固然是解决问题咯,这样,数组的第一个升级版 Vector 就出来了,在建立的时刻不需要声明巨细,然后放入的数据纷歧定都要是统一个数据类型,好比我想放数字就放数字,想放聚集就放聚集,想放字符串就放字符串。

声明一点,向量( Vector )的实现是通过数组来实现的。

在 Java 的 Vector 的源代码中可以很清晰的找到证据:

protected Object[] elementData;

动态扩容

这里就会泛起第一个问题,数组是定长的,那么向量为什么可以不定长?

固然是向量会自动扩容啦~~~~~

说到自动扩容,不禁让我想起来上面谁人糖葫芦,当棍子放不下山楂还想往上放怎么办,固然是把棍子变长点咯:

固然,我们在程序中扩容并不是直接把原有数组加长,由于数组的要求是物理空间必须地址延续,而我们却无法保证,其尾部总是预留了足够空间可供拓展。

以是能想到的做法就是另行申请一个容量更大的数组,并将原数组中的成员团体搬迁至新的空间,好比这样:

那么,问题又发生一个,每次变长(扩容)的时刻,变长(扩容)若干合适呢?

由于每次扩容的时刻,元素的搬迁都需要破费分外的时间,这对性能是一个消耗,我们并不希望这个消耗过大,那么是不是可以一次扩容扩的足够大呢?固然也不行,这样会造成内存的虚耗,虽然内存廉价,但也不是这么虚耗的。

好比初始长度是 10 ,第一次扩容直接扩容到 100 ,第二次到 1000 ,这个就太夸张了,这里可以直接参考 JDK 的源码,看下大神是怎么扩容的。

篇幅缘故原由我就不带人人在这看 Java 的源码了,直接说效果,照顾下学 Python 的同砚:

在 Java 中 Vector 的初始长度界说为 10 ,当元素个数跨越原有容量长度 1 时,举行扩容,每次扩容的巨细是原容量的 1 倍,那么就是第一次扩容是从 10 变成了 20 。

至于为什么是扩大 1 倍而不是其他这里就不展开讨论了,现实上 Java 在另一个数据结构列表( List )中扩容的巨细是 0.5 倍 + 1 。

差别数据类型

照样拿上面的糖葫芦举例子,若是一个杆上只能穿山楂,那么它是一个糖葫芦(数组),然则,只想穿山楂的糖葫芦不是一个好糖葫芦。

但我在吃山楂的同时还想吃臭豆腐,小龙虾,扇贝,生蚝,帝王蟹,成年人的天下,就是我全都要这么朴实无华。

然后糖葫芦开启了超进化模式:

变成了下面这玩意:

这个功能在 Java 中的实现是通过 Object 数组来实现的,由于 Object 在 Java 中是所有类的超类,这个接触过 Java 的同砚应该都清晰,若是没有接触过 Java ,可以这么明白,借用道德经里一句话:

道生一,一生二,二生三,三生万物

而这个 Object 就是谁人一,由这个一才发生了丰富多彩的 Java 天下,以是 Object 数组是可以转化为任何类型的。

小结

小结一下吧,我们聊了一个最简朴的数据结构,数组,还从数组中引申出来了向量( Vector ),很遗憾,Python 中没有这两个基础数据结构。

在向量( Vector )中,我们先容了向量( Vector )的两个差别于数组的特征,一个是动态扩容,另有一个是向量中可以放差别的数据类型,这对比数组极大的方便了我们一样平常的使用。

顺便说一句,虽然许多数据结构都是基于数组的,包罗本文先容的 Vector ,另有后面会先容到的列表 List ,然则我们在现实的使用中是很少会直接使用数组的,基本上都是使用数组的超进化体。

参考

https://zhuanlan.zhihu.com/p/83449008

,

诚信在线赌博正规吗

诚信在线赌博正规吗(现:阳光在线官网)现已开放诚信在线手机版、诚信在线电脑客户端下载。诚信在线娱乐游戏公平、公开、公正,用实力赢取信誉。

Sunbet声明:该文看法仅代表作者自己,与本平台无关。转载请注明:衡水信息港:一本正经的聊数据结构(2):数组与向量

网友评论

  • (*)

最新评论

  • AllbetGmaing下载 2020-10-04 00:00:09 回复

    联博开奖www.326681.com采用以太坊区块链高度哈希值作为统计数据,联博以太坊统计数据开源、公平、无任何作弊可能性。联博统计免费提供API接口,支持多语言接入。冲就对了

    1

文章归档

站点信息

  • 文章总数:794
  • 页面总数:0
  • 分类总数:8
  • 标签总数:1433
  • 评论总数:425
  • 浏览总数:34829