引言
最近的工作有个需求,做视频直播的评论列表。 本人从未有过这样的工作经验,分析一下觉得需求也有些不好搞:
- 评论不是实时返回的,是客户端轮询接口。(大概两秒一次的频率)
- 评论是动态添加上去的,所以数据结构需要尾插入。
- 评论不能无限展示,达到一定数目需要头部删除,维持总量基本不变。
乍一看头删除尾插入的模式,链表LinkedList很完美。
遇到的问题
实际使用时,因为评论内容使用RecyclerView
展示,所以onBindViewHolder()
时会需要随机读取数据结构中的数据。
所以链表的劣势就无可回避了,当评论数据量到达200+时,RecyclerView评论列表滑动会有肉眼可见的卡顿。
众所周知,链表是链式结构,我们阅读LinkedList源码也会发现:
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
node(int)
通过二分法从头或从末尾遍历获取当前下标对应的元素。最坏情况下,需要size/2
次访问才能拿到我们指定的元素。
RecyclerView滑动时,一秒有十几次甚至几十次的下标访问,LinkedList的效率肯定不能满足要求。
不甚靠谱的解决方案
分析需求: 评论列表展示200条数据,当超过时,删除头部的评论以维持两百的数目。
问了一下需求SE,确认,并不要维持精准的200数目,所以做了如下调整:
数据达到
targetCapacity
(200)条时先不删除,等到超出粒度granularity
(100)时,再一次性删除granularity
条数据。
实现了如下CapacityKeepArrayList
import java.util.ArrayList;
import java.util.LinkedList;
/**
* 支持快速头删除维护的列表
* 需要适当计算 capacity 和 granularity
* @param <E>
*/
public class CapacityKeepArrayList<E> implements DynamicList<E> {
private LinkedList<ArrayList<E>> parent;
private ArrayList<E> child;
/**
* 列表的目标容量
*/
private int targetCapacity = 200;
/**
* 动态删除头部时的粒度
*/
private int granularity = 100;
private int aimSize;
private int size = 0;
public int getGranularity() {
return granularity;
}
public int getTargetCapacity() {
return targetCapacity;
}
public CapacityKeepArrayList(int targetCapacity, int granularity) {
this.targetCapacity = targetCapacity;
this.granularity = granularity;
aimSize = targetCapacity / granularity + 1;
parent = new LinkedList<>();
grow();
}
private void grow() {
child = new ArrayList<>(granularity);
parent.add(child);
}
/*
* return 超标数量
* 0 未超标
*/
@Override
public int add(E element) {
child.add(element);
size++;
ensureGranularity();
return ensureCapacity();
}
@Override
public void forceAdd(E element) {
child.add(element);
size++;
ensureGranularity();
}
/**
* 确保粒度不超标
*/
private void ensureGranularity() {
if (child.size() == granularity) {
grow();
}
}
/**
* 确保容量不超标,
* return 超标数量
* 0 未超标
*/
private int ensureCapacity() {
int amount = parent.size() -aimSize;
if (amount < 1) {
return 0;
}
for (int i = 0; i < amount; i++) {
parent.removeFirst();
}
size -= amount * granularity;
return amount * granularity;
}
@Override
public E get(int position) {
return parent.get(position / granularity).get(position % granularity);
}
@Override
public int size() {
return size;
}
}
根据需求,大概做出了这样的方案:
- 确定粒度后,每个粒度为一单位,使用
ArrayList
存储,保证当前粒度下,是能随机访问的。 - 然后用总容量除以粒度得到
aimSize
,维护一个长度为aimSize + 1
的链表作为最终的数据结构,元素就是每一粒度的ArrayList
。
最终的数据结构,选择链表或者ArrayList其实都行。 因为实际需求是容量200,粒度100,所以只有3个元素,使用链表相比ArrayList在访问时几乎没有性能差距。链表只是为了方便头删除。
至于为啥会有forceAdd()
不论容量是否超标都插入而不删除头部的方法,是因为当用户滑动评论,停留在某一条时,不能因为刷出新评论而把用户当前正在看的给删了。
此时,数据结构的容量不能维持在targetCapacity + granularity
以内,可能会无限膨胀,这也是我为啥没有选择头尾循环队列来实现此需求。
存在的问题
- 用户在评论页面停留时,数据结构的容量可能会无限膨胀,那么
aimSize
有可能很大,性能又会下降。 - 如果外层不使用LinkedList,而是ArrayList,那么在容量膨胀时,读取性能不会下降,但是下次删除时,没法一次性删掉头部多处的很多数据,多次头删除一条数据,ArrayList性能差。
- 没有考虑线程安全的问题。
关于1.2问题,能想到的解决方案是,完全使用数组来实现两层结构,自己实现ArrayList没有的头部多个元素删除的功能。
工作经验太少,所以,想问题可能太简单或者太复杂了。 不知有啥好些的方案。期望有人讨论一下。