阅读 729

[架构基本功]TreeSet排序研究

Android组件化架构

近来在优化一些写好的排序,所以会对数据结构考虑得更深入,为什么面试都喜欢面试数据结构,面试对数据结构得熟悉层度,很大的情况下是因为只有数据结构熟悉了,才能用更少时间找到优化时间和空间的方法。

估计很多人都有过排序的经验,估计也很多会用到Collections里面的一些数据结构,例如List Set 等等。

这一节我们讨论的是TreeSet。

TreeSet有什么好处呢?

插入的同时就立刻进行排序,你只需要设定好比较器,就能按照设定来进行排序,因为他是一个红黑树,树的特征是拥有排序。同时他是个Set,只要比较器认为是同一个,就会被去重。

TreeSet使用的结构

其内部是使用了TreeMap,Set值保存在Map的key中,value存了一个Object,Map中如果Key值相同会被认为是同一个,这样就能够实现数据去重。TreeMap内部维护的是一个红黑树。因为是树状结构,那么其查询效率和插入效率都是log(n),当然对应耗时,会因为红黑树平衡调整,会有相应的耗时。

TreeSet不是线性安全的,线性安全需要使用ConcurrentSkipListSet。内部是SkipList(跳表)结构实现,在理论上能够在O(log(n))时间内完成查找、插入、删除操作。

跳表.png
跳表本质是一个链表,只是链表节点中会记录一定跨度后的的链表节点地址。

####属性变更问题 TreeSet可以指定比较器Comparator,可以通过类中继承Comparable来进行比较迭代。但是里面的属性变化了,不会重新触发排序。需要重新插入排序。例如,TreeSet保存的类文件,类中包含一些列表,列表数据组装并且同时插入到TreeSet,正好比较器需要比较列表中元素的属性,这时候,因为列表是一直在变化的。会出现,类文件插入到TreeSet的时候,再变更类文件中列表的属性,是无法触发TreeSet中自动排序的。TreeSet无法判断到其对象变更情况。

你可以采取的策略是

1.插入到TreeSet前需要确定类文件属性不再变更。

2.触发变更的时候,重新将其赋值到TreeMap当中,更新比较。

####去重问题 如果比较器中返回为0 ,Set中认为是相等的,会执行去重操作。如果比较器逻辑有问题,可能会触发死循环比较。

####比较器效率问题 TreeSet是边插入边比较,而Collections.sort函数应用场景是List队列当中,两者都能是用比较器来完成操作。

ThreeSet的底层实现是红黑树,它在创建set的过程中实现排序。Collections.sort是在对整个集合进行排序,按道理来说使用TreeSet插入集合元素直至建立整个TreeSet过程中实现排序在时间方面要比Collections.sort对整个集合进行排序效率要高很多,因为它在每次搜索要插入的位置时耗费的时间为log(n),n代表的是当前集合的长度,但实验表明使用Collections.sort对集合进行排序时间耗费要少些。

性能比较.png

出现这种情况的原因是

1.TreeSet的搜索时间为log(n),明显上是比List有优势的。

2.TreeSet在插入的时候需要先创建节点,而List比较并不需要增加额外节点。

3.TreeSet基于红黑树,那么其每次插入都需要检查和维护红黑树平衡,如果失衡会触发红黑树结构调整。

基于2,3两点,无疑会比List更加耗时,数据越多,效率差距越明显。当然这里没有加入List的插入创建节点时间,就算将插入时间加入进来,估计效率上海市Collections.sort占优。

Android组件化群1

Android组件化群2

关注下面的标签,发现更多相似文章
评论