IT学习站-137zw.com

作者: 哈哈SE7
查看: 68|回复: 0

more +资源更新Forums

more +随机图赏Gallery

价值368元 从Docker到K8S实战视频教程 五年工程师主讲 百度云价值368元 从Docker到K8S实战视频教程 五年工程师主讲 百度云
价值299 opencv+tensorflow入门人工智能图像处理 百度云 网盘 下载价值299 opencv+tensorflow入门人工智能图像处理 百度云 网盘 下载
价值199元 Nginx中间件搭建负载均衡安全防护动静分离视频 ...价值199元 Nginx中间件搭建负载均衡安全防护动静分离视频 ...
价值348元 RabbitMQ消息中间件技术精讲2018视频教程 百度云价值348元 RabbitMQ消息中间件技术精讲2018视频教程 百度云
云豹直播平台全套源码无限制完美运营版(安卓+IOS)源码云豹直播平台全套源码无限制完美运营版(安卓+IOS)源码
Spring Security4企业权限管理视频,完整版课程下载Spring Security4企业权限管理视频,完整版课程下载

面试官: 100万个成员的数组取第一个和最后一个有性能差距吗?

面试官: 100万个成员的数组取第一个和最后一个有性能差距吗?

[复制链接]
哈哈SE7 | 显示全部楼层 发表于: 2019-11-14 12:00:07
哈哈SE7 发表于: 2019-11-14 12:00:07 | 显示全部楼层 |阅读模式
查看: 68|回复: 0

你还没有注册,无法下载本站所有资源,请立即注册!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本文首发于微信公众号「程序员面试官」
数组几乎可以是所有软件工程师最常用到的数据结构,正是因为如此,很多开发者对其不够重视.
而面试中经常有这样一类问题: 「100万个成员的数组取第一个和最后一个有性能差距吗?为什么?」
除此之外,我们在平时的业务开发中会经常出现数组一把梭的情况,大多数情况下我们都会用数组的形式进行操作,而有读源码习惯的开发者可能会发现,在一些底层库中,我们可能平时用数组的地方,底层库却选择了另外的数据结构,这又是为什么?
希望大家带着以上的问题我们进行讨论.
什么是数组

数组是计算机科学中最基本的数据结构了,绝大多数编程语言都内置了这种数据结构,也是开发者最常见的数据结构.
数组(英语:Array),是由相同类型的元素(element)的集合所组成的数据结构,分配一块连续的内存来存储.
当然,在一些动态语言中例如Python的列表或者JavaScript的数组都可能是非连续性的内存,也可以存储不同类型的元素.
比如我们有如下一个数组:其在内存中的表现应该是这样的:

面试官: 100万个成员的数组取第一个和最后一个有性能差距吗?  技术博客

我们可以看到,这个数组在内存中是以连续线性的形式储存的,这个连续线性的储存形式既有其优势又有其劣势,只有我们搞清楚优劣才能在以后的开发中更好地使用数组.
数组的特性

一个数据结构通常都有「插入、查找、删除、读取」这四种基本的操作,我们会逐一分析这些操作带来的性能差异.
首先我们要辨析一个概念--性能.
这里的性能并不是绝对意义上速度的快慢,因为不同的设备其硬件基础就会产生巨大的速度差异,这里的性能是我们在算法分析中的「复杂度」概念.
复杂度的概念可以移步算法分析
插入性能

我们已经知道数组是一段连续储存的内存,当我们要将新元素插入到数组k的位置时呢?这个时候需要将k索引处之后的所有元素往后挪一位,并将k索引的位置插入新元素.

面试官: 100万个成员的数组取第一个和最后一个有性能差距吗?  技术博客

我们看到这个时候需要进行操作的工作量就大多了,通常情况下,插入操作的时间复杂度是O(n).
删除性能

删除操作其实与插入很类似,同样我要删除数组之内的k索引位置的元素,我们就需要将其删除后,为了保持内存的连续性,需要将k之后的元素通通向前移动一位,这个情况的时间复杂度也是O(n).

面试官: 100万个成员的数组取第一个和最后一个有性能差距吗?  技术博客

查找性能

比如我们要查找一个数组中是否存在一个为2的元素,那么计算机需要如何操作呢?
如果是人的话,在少量数据的情况下我们自然可以一眼找到是否有2的元素,而计算机不是,计算机需要从索引0开始往下匹配,直到匹配到2的元素为止.

面试官: 100万个成员的数组取第一个和最后一个有性能差距吗?  技术博客

这个查找的过程其实就是我们常见的线性查找,这个时候需要匹配的平均步数与数组的长度n有关,这个时间复杂度同样是O(n).
读取性能

我们已经强调过数组的特点是拥有相同的数据类型和一块连续的线性内存,那么正是基于以上的特点,数组的读取性能非常的卓越,时间复杂度为O(1),相比于链表、二叉树等数据结构,它的优势非常明显.
那么数组是如何做到这么低的时间复杂度呢?
假设我们的数组内存起始地址为start,而元素类型的长度为size,数组索引为i,那么我们很容易得到这个数组内存地址的寻址公式:比如我们要读取arr[3]的值,那么只需要把3代入寻址公式,计算机就可以一步查询到对应的元素,因此数组读取的时间复杂度只有O(1).
性能优化

我们已经知道除了「读取」这一个操作以外,其他操作的时间复杂度都在O(n),那么有没有有效的方法进行性能优化呢?
查找性能优化

当数组的元素是无序状态下,我们只能用相对不太快的线性查找进行查找,当元素是有序状态(递增或者递减),我们可以用另一种更高效的方法--二分查找.
假设我们有一个有int类型组成的数组,以递增的方式储存:如果我们要查找值为6元素,按照线性查找的方式需要根据数组索引从0依次比对,直到碰到索引5的元素.
而二分查找的效率则更高,由于我们知道此数组的元素是有序递增排列的:
<ol>我们可以取一个索引为3的元素为中间值p
将p与目标值6进行对比,发现p的值4
137zw.com IT学习站致力于免费提供精品的java技术教程和python技术教程,CCNA书籍/资料/CCNP书籍/资料教程/CCIE书籍/资料/H3C学习/认证/一级建造师考试/微软学习/认证/包括基础教程和高级实战教程,同时也提供分享网站源码下载和互联网相关一系列的技术教程,我们想做的就是让知识分享更有价值!(IT学习站官方唯一域名地址:www.137zw.com 请谨防假冒网站!)本站所有资源全部收集于互联网或网友自行分享,分享目的仅供大家学习与参考,如无意中侵犯您的合法权益,请联系本站管理员进行删除处理!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

浙ICP备19022368号-1|Archiver|手机版|IT学习站-137zw.com

GMT+8, 2020-7-6 00:12 , Processed in 0.257347 second(s), 32 queries .

快速回复 返回顶部 返回列表