COCOS2D-X 3.0新的数据结构

  次阅读 作者:智能小宝 来源:互联网 2015-09-27 15:31 我要评论(0)

基础数据结构在游戏开发中至关重要,可能每一帧某个逻辑需要从一个数组中查找,删除,添加数据,或者从一个字典中快速存/取一个值,游戏引擎本身也要对UI树进行遍历,排序等操作。基础数据的操作速度影响着程序的性能,而基础数据的使用方法则影响着开发效率。当然我们应该尽量避免游戏中每一帧频繁的迭代和查找计算,应尽可能地将结果缓存起来。

C++标准库已经提供了数组(std::vector),字典(std::map)等比较优秀的基础数据结构,然而它们不支持Cocos2d-x的内存管理方式(关于Cocos2d-x内存管理,参见第三章)。在Cocos2d-x 2.x及之前的版本中,Cocos2d-x提供CCArray和CCDictionary来结合Cocos2d-x的内存管理方式一起工作,但是它们却不能很好地支持标准库中的迭代器操作,这在一定程序上影响着开发效率。

Cocos2d-x 3.0用Vector和Map代替了之前的CCArray和CCDictionary,新的容器类使用模板类来避免了不必要的数据类型转换,同时能够完美地支持标准库中的各种迭代操作,例如std::find(),std::sort()等等。实际上,在3.0中Vector和Map是对标准库中std::vector和std::unordered_map的封装,使其能够结合Cocos2d-x的内存管理方式。我们可以从以下三个方面来理解新的数据结构的特点。

1.2.6.1 Map的性能

对于Map,Cocos2d-x默认使用std::unordered_map,std::unordered_map将每个key值转化为hash值存储,并按照hash值排序,所以它不是实际的字典中Key或者Value值的存储顺序。unordered_map对于单个Key值的查找有更快的速度,它只需要将Key转化为hash值,然后做一次或者多次相等比较,其复杂度为O(n),而std::map的find复杂度为O(log2(n)),它在每个元素之间使用小于比较。

std::unordered_map初始化的时候分配一定数量(通常很少)的buckets来存储Key/Value对,每个bucket对应一个hash值。hash值是基于buckets的数量来计算的,所以当新增元素的时候,一个bucket可能就会对应多个hash值,造成冲突,std::unordered_map就需要重新计算所有hash值(rehash),这会造成一定的性能问题。所以如果你需要在短时间内插入一定数量的数据,最好使用resverve方法来设定buckets的数量,减少不必要的rehash计算。当然如果只是偶尔插入或者删除数据,则不必这么做,因为resverve会增加unordered_map的内存占用。

另一个需要注意的地方是std::hash的计算,std::unordered_map使用特殊的hash算法,当其类型为整数时,直接将其自身作为hash值,这减少hash值的计算量。所以,游戏中应尽量使用整型作为 Map的Key值类型,这会大大提升Map的性能,参见引用4和5。

1.2.6.2 与Cocos2d-x内存管理的结合

在2.x的使用场景中,CCArray和CCDictionary通常被分配在堆上,我们不得不需要考虑在适当的地方释放其内存。新的容器类不再继承自Ref(2.x中的CCObject),新的容器类通常应该被分配在栈上来使用,这简化了内存管理,我们应该将精力放在容器元素而不是容器本身的内存管理上。

Vector中的T和Map中的V必须是Ref类型,因为它们需要结合Cocos2d-x的内存管理方式一起工作。这简化了容器中元素的内存管理,这主要体现在两个方面。

以任何形式新加入到容器中的左值都会执行retain()方法使引用计数+1,以Vector为例,比如拷贝构造函数,赋值操作符,pushBack,replace,insert:

class MyClass : public Ref

{};

void testVector()

{

auto c1= new MyClass();

c1->autorelease();

auto c2=new MyClass();

c2->autorelease();

CCLOG(“reference count c1:%d & c2:%d”,c1->getReferenceCount(),c2->getReferenceCount());

Vector v1;

v1.pushBack(c1);

v1.insert(1, c2);

CCLOG(“reference count c1:%d & c2:%d”,c1->getReferenceCount(),c2->getReferenceCount());

v1.popBack();

CCLOG(“reference count c1:%d & c2:%d”,c1->getReferenceCount(),c2->getReferenceCount());

Vector v2=Vector(v1);

CCLOG(“reference count c1:%d & c2:%d”,c1->getReferenceCount(),c2->getReferenceCount());

Vector v3=v1;

CCLOG(“reference count c1:%d & c2:%d”,c1->getReferenceCount(),c2->getReferenceCount());

本站文章信息来源于网络以及网友投稿,本站只负责对文章进行整理、排版、编辑,是出于传递更多信息之目的,并不意味着赞同其观点或证实其内容的真实性。如果您有什么意见或建议,请联系QQ28-1688-302!

人工智能实验室
相关文章相关文章
  • 英国研发“杀生”机器人 通过生命体获取能量

    英国研发“杀生”机器人 通过生命体获取能量

  • 未来两年人工智能要怎么走?看这篇就够了

    未来两年人工智能要怎么走?看这篇就够了

  • 无人驾驶汽车如何改变城市生活?听听他们怎么说

    无人驾驶汽车如何改变城市生活?听听他们怎么说

  • 韩春雨称已能重复实验结果 近期将有消息公布

    韩春雨称已能重复实验结果 近期将有消息公布

网友点评网友点评
阅读推荐阅读推荐

据国外媒体报道,在过去两年内,聊天机器人(chatbot)、人工智能以及机器学习的研发和采用取得了巨大进展。许多初创公司正利用人工智能和...

霍金 视觉中国 图 英国著名物理学家霍金(Stephen Hawking)再次就人工智能(AI)发声,他认为:对于人类来说,强大AI的出现可能是最美妙的...

文|郑娟娟 今年,人工智能(AI) 60岁了。在AI60岁的时候,笔者想要介绍一下AI100,一个刚刚2岁的研究项目,但它的预设寿命是100年,甚至更长...

AlphaGo与李世石的人机大战,为大众迅速普及了人工智能的概念。 但对谷歌而言,除了下围棋,现在的人工智能进展到哪一步了?未来,人工智能...