Android高性能编码三：数据结构和算法优化

TPS(Transaction Per Second)
TPS为每秒处理的事务数，是系统吞吐量的指标，在搜索系统中也用QPS(Query Per Second)衡量。TPS一般与响应时间反相关。

通常所说的性能问题就是指响应时间过长、系统吞吐量过低。

Android高性能编码一：多线程并发或分布式提高TPS

Android高性能编码二：利用缓存提高TPS

Android高性能编码四：代码优化

这里我们介绍数据结构和算法对性能的影响。

Java语言和Android源码里面有很多现成的轮子，我们在使用这些数据结构的时候，要知其所以然，从源码分析这些数据结构的原理和特点，选取最适合的拿来用。

1.使用SparseArray、ArrayMap代替HashMap

SparseArray指的是稀疏数组(Sparse array),所谓稀疏数组就是数组中大部分的内容值都未被使用（或都为零），在数组中仅有少部分的空间使用。因此造成内存空间的浪费，为了节省内存空间，并且不影响数组中原有的内容值，我们可以采用一种压缩的方式来表示稀疏数组的内容。

google推荐使用其代替HashMap, 其内部实现了压缩算法，可以进行矩阵压缩，大大减少了存储空间，节约内存。此外它的查找算法是二分法，提高了查找的效率。

数据量小于1000时，使用ArrayMap可以避免HashMap内存翻倍的问题，以int为key的HashMap可以用SparseArray代替，缺点是乱序查找添加删除效率不如HashMap

ArrayMap的使用并不能提升反应时间，却能够节省内存空间，当数据量很大时，使用ArrayMap,以时间换空间，防止出现OOM。Bundle实现使用了ArrayMap。

ArrayMap与HashMap有四点不同

a.储存方式不同

ArrayMap储存数据和HashMap不同，它没有Entry这个东西，而是用数组来保存数据

b.扩容操作不同

HashMap容量不足时，会新建double容量table返回，而ArrayMap采用copy方式，并且收缩数组，释放不必要的容量。

c.数组可收缩

去掉不使用的容量，节省空间。

d.查找方式不同

ArrayMap采用二分查找，查找效率比HashMap高，但是插入数据会涉及大量的数据搬移

和SparseArray一样，数据量适中时（小于1000）使用ArrayMap可以避免HashMap内存翻倍的问题。数据条数大于1000时乱序操作效率很低，不推荐使用。

2.根据情况选择适合的collection容器

根据实际情况选择ArrayList或者LinkedList。

a.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
b.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
c.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。

3.根据实际情况，选择合适的算法

a.关于查找的算法很多种：基本查找、二分查找、二叉树、斐波那契等

它们时间复杂度和空间复杂度不同，选择适合的算法事半功倍

比如一个顺序队列n个数据，选择基本查找的时间复杂度为O(n)，而二分查找时间复杂度为O(log 2 n)，显然n越大，基本查找消耗的时间越久，性能损耗越高。

再比如，查询某个文件，你可以采用基本查找、也可以先排序、再进行二分查找。

4.采用ConcurrentHashMap处理需要线程同步的Map

ConcurrentHashMap相较于HashMap,它是线程同步的，而且不是简单的加锁而已，而是采用了分段加锁的技术segment（类似HashTable）来进行加锁，性能比单纯的全局加锁提升10几倍。

5.可以尝试自己造轮子

现成的数据结构不一定是最好的，他们往往是最稳定的，它们的都不是凭空产生的，条件合适，可以自己写数据结构，自己造的肯定最适合你。

总之，用于现实世界的存储，我们使用的工具和建模。每种数据结构有自己的优点和缺点，根据实际情况采用合适的数据结构。
而算法，在这么多的数据中如何做到最快的插入，查找，删除，也是在追求更快。

数据结构和算法重要性远不止这些，它是一门很高深的学科，摘录一段对数据结构和算法比较深刻的描述

如果说 Java 是自动档轿车，C 就是手动档吉普。数据结构呢？是变速箱的工作原理。你完全可以不知道变速箱怎样工作，就把自动档的车子从 A 开到 B，而且未必就比懂得的人慢。写程序这件事，和开车一样，经验可以起到很大作用，但如果你不知道底层是怎么工作的，就永远只能开车，既不会修车，也不能造车。如果你对这两件事都不感兴趣也就罢了，数据结构懂得用就好。但若你此生在编程领域还有点更高的追求，数据结构是绕不开的课题。

Java 替你做了太多事情，那么多动不动还支持范型的容器类，加上垃圾收集，会让你觉得编程很容易。但你有没有想过，那些容器类是怎么来的，以及它存在的意义是什么？最粗浅的，比如 ArrayList 这个类，你想过它的存在是多么大的福利吗——一个可以随机访问、自动增加容量的数组，这种东西 C 是没有的，要自己实现。但是，具体怎么实现呢？如果你对这种问题感兴趣，那数据结构是一定要看的。甚至，面向对象编程范式本身，就是个数据结构问题：怎么才能把数据和操作数据的方法封装到一起，来造出 class / prototype 这种东西？

此外，很重要的一点是，数据结构也是通向各种实用算法的基石，所以学习数据结构都是提升内力的事情。

摘自Java数据结构和算法(一)——开篇

参考文章

java 中几种常用数据结构

Java数据结构和算法(一)——开篇

Android内存优化：ArrayMap

HashMap，ArrayMap，SparseArray源码分析及性能对比

更多相关文章

随机推荐