AG亚游集团 >iOS开发

100天iOS数据结构与算法实战 Day09 - iOS中数组的算法分析

2019-04-15 10:26 编辑: Gboy 分类:iOS开发 来源:人魔七七

前言

由于我们之前的栈以及后面的队列都是用数组实现的。所以我们了解下数组对于了解数据结构很有帮助。

C语言的世界里由于数组内存是连续的所以,所以删除和添加元素的时候会memmove内存的元素,如下所示。

添加

640 (1).gif

删除

640 (2).gif

总结:如果元素很多,移动效率会很低。

iOS中数组是怎么优化的呢?

iOS数组中为了优化上述问题采用了,circular buffer的数据结构来解决。

在头部删除

640 (3).gif

在头部添加

640 (4).gif

总结:在两端插入和删除都很快

在中间删除

640 (5).gif

总结:在中间插入或者删除尝试移动最小的内存量,因此它将最多移动一半的元素。

访问数组中的元素第一种情况

image.png

offset是2,size是5。我们获取数组index 0 的元素,所以要获取元素的offset等于2+0。由于size 5 ,大于获取元素的offset 2 。所以这时候数组index 0 的元素就是list[2],也就是如图offset所指的元素。

访问数组中的元素第二种情况

image.png

获取数组index 0 的元素,这时候获取的元素的offset等于4+0,则就是如图所示offset指向的元素。如果获取数组index 2 的元素,这时候获取的元素的offset等于4+2=6,但是6>size(5),所以需要减去size也就是(4+2)- 5=1,也就是如图offset1指向的元素。

总结所以获取数组元素的效率也是很高的。

数组的容量问题


  • 我们尽量在刚开始能预估容量大小,以防止频繁的扩容造成的效率问题。



  • 一旦有大量元素存在,然后你又删除的所剩无几,数组空间不会自动减小,需要你自己清除空间,这个技巧我们在栈中使用过。


结合数组API来分析

addObject

如果当前容量很充足,我们添加元素到数组是O(1)的操作。如果此时正好容量用完,需要扩充容量,这时候需要创建新的容器并copy过去,这时候是O(n)。

insertObject

如果在头尾两处插入,在容量充足情况下效率最高O(1)的操作。但是如果在中间插入则需要移动最多一半的元素,这时候是O(n)的操作。

removeLastObject

在尾部或者头部删除是O(1)操作。

removeObjectAtIndex

但是如果在中间删除则需要移动最多一半的元素,这时候是O(n)的操作。

initWithCapacity

上面已经介绍如果能提前预估容量可以有效避免扩容造成的性能问题。

这个扩容的过程是创建一个新的容器分配更大的空间,然后把旧的容器的元素们copy进来。这个扩容发生是恒定的时间,随着容量的变大,发生的次数会越来越少。

推荐阅读

AG亚游集团100天iOS数据结构与算法实战 Day02 - 栈 


AG亚游集团100天iOS数据结构与算法实战汇总


GitHubDemo地址

GitHubDemo ---> /github0686com/renmoqiqi/100-Days-Of-iOS-DataStructure-Algorithm

References

[1] GithubDemo: /github0686com/renmoqiqi/100-Days-Of-iOS-DataStructure-Algorithm

转载自公众号:人魔七七

搜索CocoaChina微信公众号:CocoaChina
微信扫一扫
订阅每日移动开发及APP推广热点资讯
公众号:
CocoaChina
上一篇:iOS如何区分App和SDK内部crash
下一篇:iOS 核心动画的性能调优
我来说两句
发表评论
您还没有登录!请登录注册
所有评论(0

综合评论

相关帖子

sina weixin mail 回到顶部
俄总理向普京提交新内阁名单:防长外长获留任 皇马这什么操作?新签4500万妖星下放到青年队 牛汇:特朗普会控制美联储吗 历史证明这并非不可能 老美列数据打MVP脸!87%vs46%这么看他真是瘤? 萧山妹子相亲直接被男方妈妈拒绝 只因她有个弟弟 轿车变“飞车”直冲屋顶 惊呆路人(图) 苹果力劝FCC为5G保留更多未授权频谱 北京市政交通一卡通充值今起可在线领取电子发票 洛帅教鞭落下敲定两个核心 战术司令官+新巨星骑手 卢指导夸张狠吹詹皇却挨喷!美球迷忍不了他了 一架美国军用直升机在伊拉克坠毁 已造成人员伤亡 俄批美在叙炮制化武袭击伪证 称俄若受威胁将还击
春节后食品价格持续下降 3月物价涨幅或现明显回调 腾讯音乐要赴美上市了 IPO估值超过250亿美元 新西兰毒品泛滥议员甩锅:都怪太平洋那些失败国家 葡西法三国签能源互联协议 法国4年内将关所有煤电厂 来自中国的邮轮时隔一年赴韩 中国游客仅14人 曼联有这悍将太幸福!穆帅扭转颓势还要倚靠他 全国人大这两个专门委员会主任委员为何先确定? 迄今为止美国对华实施6次“301调查” 专家:电子验证有漏洞 1条身份信息在黑市卖10元 我国台办前主任评价蔡英文\"执政\"作为 16个字一针… 关于蒂姆紧密的赛程安排 是明智的还是鲁莽的? 社科院三季度宏观经济分析报告:全球经济改革乏力
长安剑:最高法工作报告9句话 人大代表给予掌声 加西亚喜迎第一个孩子 女儿取名杜鹃纪念大师赛 大龄女老板半年相亲超10次 相亲十年只想找帅哥 女子结识网友被忽悠“投资” 5年被骗走百万 U23国足7月底集结备战 中超13队可享受亚运新政 伊朗国产新型反坦克导弹亮相 射程10公里(图) 打倒二1节花还只能靠三双!詹姆斯本季已没退路 新华社:美国豆农担心成为中美贸易摩擦受害者 中甲最佳阵容:深圳悍将3射1传 土炮密集临危救主 利润最高的不起眼行业 小投资冷门暴利行业 女生适合开什么店 小投资冷门暴利行业 AG亚游集团