可隨機訪問(

NO IMAGE

引言

最近的工作有個需求,做視頻直播的評論列表。
本人從未有過這樣的工作經驗,分析一下覺得需求也有些不好搞:

  1. 評論不是實時返回的,是客戶端輪詢接口。(大概兩秒一次的頻率)
  2. 評論是動態添加上去的,所以數據結構需要尾插入。
  3. 評論不能無限展示,達到一定數目需要頭部刪除,維持總量基本不變。

乍一看頭刪除尾插入的模式,鏈表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

GitHub代碼

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;
}
}

根據需求,大概做出了這樣的方案:

  1. 確定粒度後,每個粒度為一單位,使用ArrayList存儲,保證當前粒度下,是能隨機訪問的。
  2. 然後用總容量除以粒度得到aimSize,維護一個長度為aimSize + 1的鏈表作為最終的數據結構,元素就是每一粒度的ArrayList

最終的數據結構,選擇鏈表或者ArrayList其實都行。
因為實際需求是容量200,粒度100,所以只有3個元素,使用鏈表相比ArrayList在訪問時幾乎沒有性能差距。鏈表只是為了方便頭刪除。

至於為啥會有forceAdd()不論容量是否超標都插入而不刪除頭部的方法,是因為當用戶滑動評論,停留在某一條時,不能因為刷出新評論而把用戶當前正在看的給刪了。

此時,數據結構的容量不能維持在targetCapacity + granularity以內,可能會無限膨脹,這也是我為啥沒有選擇頭尾循環隊列來實現此需求。

存在的問題

  1. 用戶在評論頁面停留時,數據結構的容量可能會無限膨脹,那麼aimSize有可能很大,性能又會下降。
  2. 如果外層不使用LinkedList,而是ArrayList,那麼在容量膨脹時,讀取性能不會下降,但是下次刪除時,沒法一次性刪掉頭部多處的很多數據,多次頭刪除一條數據,ArrayList性能差。
  3. 沒有考慮線程安全的問題。

關於1.2問題,能想到的解決方案是,完全使用數組來實現兩層結構,自己實現ArrayList沒有的頭部多個元素刪除的功能。


工作經驗太少,所以,想問題可能太簡單或者太複雜了。
不知有啥好些的方案。期望有人討論一下。

相關文章

面向開發的測試技術(二):性能測試

面向開發的測試技術(一):Mock

Java學習筆記

[持續更新]開發筆記