[转]数据结构的优缺点

转自:Java情侠的空间

类型 优点 缺点
数组 插入块,如果知道下标,可以非常快的存储 查找慢,删除慢,大小固定
有序数组 比无序数组查找快 删除和插入慢,大小固定
提供后进先出方式的存取 效率低
队列 提供先进先出的方式存取 效率低
链表 插入,删除快 查找慢
二叉树 查找,插入,删除都快 如果非平衡就很慢,删除的算法复杂
红黑树 查找,插入,删除都快 算法复杂
哈希表 如果关键字已知则存取极快,插入块 删除慢,如果不知道关键字则存取很慢,对存储空间使用不充分
插入,删除快,对最大数据项的存取很快 对其他存储项很慢

Array/Vector/AS3DS/ds/dsforas 性能比较


AS3DS是我们常用的数据结构,后来polygonal又开发了ds,国人也开发了一套dsforas。那么,这些常用的数据结构与AS3原生的Array和Vector,性能上有何区别?我在网上只找到了这篇,该文也没有给出一个直观的演示,因此决定自己来测试一下。

测试平台:

  • AS3DS: v1.04
  • ds: v1.23
  • dsforas: r25
  • Flash Player: v10.2.152.26
类型 写入(ms) 读取(ms)
Array 452 132
Vector 256 130
SLinkedList 2708 1718
SSL 1266 222
LinkedList 1498 1392

注意:

  • 这次测试只是针对单链表测试了1000000个随机数的顺序写入和读取速度,不能代表整体性能。(链表的性能特点看这里:数据结构的优缺点
  • 使用AS3DS,文件增大4K;使用ds,文件增大16K。
  • AS3DS和ds不能在一个项目中测试,因为很多类名重复,必须分开测试。

继续阅读Array/Vector/AS3DS/ds/dsforas 性能比较