专栏首页Unity Technology数据结构与算法(一)

数据结构与算法(一)

其实我们编程基本上就是在和数据打交道

int ,string ,GameObject等等数据类型...

数据结构是什么呢?

数据结构就是指数据的组织形式

string Str1 = "Hello";
string Str2 = "Unity";
Debug.Log (Str1+","+Str2);

Str1与Str2变量引用着不同的字符串.变量的顺序影响着输出结果.

但是,数据结构不仅仅用于组织数据,它极大的影响代码的速度,当我们采用合适的数据结构将会大大提高程序的运行速度,相反采用不合适的数据结构程序会被托到崩溃.一旦对于数据结构有了系统化的认知,那么你的代码将会十分优雅与高效.

  • 数据结构的基础:数组

不管你学的是什么语言,第一个接触的数据结构大概率是数组,那么你真的懂数组吗?

数组,顾名思义,就是数据的组合,储存的都是同一类型的数据,在塔防游戏中,有的程序员会将敌人放入数组中.

假如,在塔防游戏中,A类防御塔只可以攻击地面的怪物,第N波敌人中有"地精","兽人","狼"这3种怪物,它们按照顺序走进了防御的攻击范围,那么,加入防御塔需要把在攻击范围内的怪物都用数组记录下来:

地精(Clone)

兽人(Clone)

狼(Clone)

那么,防御塔有3种攻击模式:1.最近2.最远3.随机

如果玩家选择了最近,防御塔又如何知道离他最近的是"地精(Clone)"呢?

我们会用索引来表示每个怪物在数组中的位置

地精(Clone)0

兽人(Clone)1

狼(Clone)2

若想分析某个数据结构的性能,首先得分析程序是怎么操作这一数据的.

对于数据而言,操作的方法有:"读取","查找","插入","删除".研究这4种操作的运行速度,即完成操作需要几步,这就有点像"把大象装冰箱"的问题了.

"完成这个操作需要几步"这是一个十分重要的判断方法,PS:后续会对这些做一个详细展开说明(大O计步发,算法等).

当你在unity中声明了一个长度为3数组,unity会在内存中开辟一个连续空间来存放你声明的数组,即使数组里面什么都没有,但是这3个空间是留给你的数组的.

每个数组的元素在内存中都有序号,假设下图中红色的部分是留给上面说的长度为3的数组的.

100001

100002

100003

100004

100005

100006

100007

100008

100009地精(Clone)

100010兽人(Clone)

100011狼(Clone)

100012

100013

100014

100015

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

  • 读取:因为在数组中每个数据有一个下标,且数组在内存中有地址,所以当我们需要找这个数组中下表为1的数据的时候,程序会直接跳到该索引并获取存在此处的值.不管你的数组长度是3还是300,查找就是一步到位.剧透一下,记下步骤数的就是大O记步法.这个后面再说.
  • 查找:如果我们要查找"狼(Clone)"这条数据,我们一眼就可以看到,是在数组的最后方,但是程序没有眼,看不到,只能一个一个的去比对,那么像在最后的这种情况,我们称之为最坏的情况,也就是说你数组有多长就要比较多少次.
  • 插入:当需要在数组中插入一个数据的时候,比如我们要在数组的开头插入一个数据 100009 史莱姆(Clone) 100010 地精(Clone) 100011 兽人(Clone) 100012 狼(Clone) 那么会看到所有的元素都向后移了一位,一个长度为N的数组,在数组开头插入一条数据,那么程序所执行的步骤是,向后移动了N个步骤,插入操作1个步骤,一共的步骤是N+1. 如果是在最后插入一条数据则不需要N步骤向后移动的步骤,直接可以在最后增加.
  • 删除:删除和插入是差不多的操作,比如我要在最后删除一个数据,那么只需要删除这一个步骤就完成了,加入我删除的是第一个数据,那么需要的就是删除+N步骤的数据向前移动了.
  • 数据结构的基础:集合

这里说的集合是List<T>.

集合,它是一种不能有重复数据的数据结构,它的这点特性决定了它与数组的区别,也就是说,这是它唯一与数组不一样的地方.所以在"读取","查找","插入","删除"就有一点不同

读取:这与数组一样 ,都是一步到位

查找:这与数组一样,都需要一个一个的比对

插入:由于集合的特性,在插入之前需要判断在已知的集合里面有没有这个数据,假如插入的数据在第一位,但是这个相同数据在末尾,那么首先就是N步的查找.如果末尾的和要插入的不一样,那么就是N+1步骤才能完成操作.

删除:和插入是一样的,都是首先要看是不是有相同的元素

总结

通过讲解了数组与集合的数据结构,分析程序的操作步骤(也就是性能),采用合适的数据结构,决定你的程序是承受压力还是崩溃.

不同的数据结构有不同的时间复杂度(上面所说的步骤数),那么就可以使用数据结构对比各种算法,找出性能最优的.这将是后续文章讲解的.

本文分享自微信公众号 - 游戏程序员聚集地(Game_Programmer),作者:Jtro

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-01-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构与算法(一)

    但是,数据结构不仅仅用于组织数据,它极大的影响代码的速度,当我们采用合适的数据结构将会大大提高程序的运行速度,相反采用不合适的数据结构程序会被托到崩溃.一旦对于...

    LittleU
  • 数据结构与算法(二)

    上篇文章介绍了两种数据结构,数组与集合,集合与数组特性基本相同,不同的是集合中的元素是不能相同的.所以在执行插入的时候,集合比数组多了一步"查重"的操作,这是一...

    LittleU
  • 数据结构与算法(二)

    上篇文章介绍了两种数据结构,数组与集合,集合与数组特性基本相同,不同的是集合中的元素是不能相同的.所以在执行插入的时候,集合比数组多了一步"查重"的操作,这是一...

    LittleU
  • 数据结构与算法(一)

    但是,数据结构不仅仅用于组织数据,它极大的影响代码的速度,当我们采用合适的数据结构将会大大提高程序的运行速度,相反采用不合适的数据结构程序会被托到崩溃.一旦对于...

    LittleU
  • 科幻电影看多了 碰到多维数组 请冷静一下

    说在前面的话:其实越是基础的知识,讲起来难度越大,因为越是基础,它就越偏向底层,你看得到的知识就那么多,但是你看不到的地方有大量的你暂时不需要知道的知识,所以只...

    用户5745563
  • Java面试之数组

    Array:它是数组,申明数组的时候就要初始化并确定长度,长度不可变,而且它只能存储同一类型的数据,比如申明为String类型的数组,那么它只能存储S听类型数据...

    黄桂期
  • 算法题之优势洗牌

    给定两个大小相等的数组 A 和 B,A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。

    挥刀北上
  • 全面解密QQ红包技术方案:架构、技术实现、移动端优化、创新玩法等

    自 2015 年春节以来,QQ 春节红包经历了企业红包(2015 年)、刷一刷红包(2016 年)和 AR 红包(2017 年)几个阶段,通过不断创新玩法,活跃...

    JackJiang
  • 光刻机之战

    航空发动机一直被誉为人类顶尖工业皇冠上的明珠。但最近十年,不断挑战物理学极限的半导体光刻机,大有挑战明珠之王的趋势。

    镁客网
  • 最快速的视野管理算法

    本文提出一种利用无序数组、双向链表、位标记进行视野管理的算法,可以将每次增、删、查视野列表的复杂度降为O(1)。

    王杰

扫码关注云+社区

领取腾讯云代金券