In the last video, we implemented a fixed-size virtual list. In this video, we increased the difficulty of implementing a fictitious list of a variable size.

demand

Implement a virtual list of variable sizes. Use as follows:

const rowHeights = new Array(1000)
  .fill(true)
  .map(() => 25 + Math.round(Math.random() * 50));
 
const getItemSize = index => rowHeights[index];
 
const Row = ({ index, style }) => (
  <div style={style}>Row {index}</div>
);
 
const Example = () => (
  <List
    height={150}
    itemCount={1000}
    itemSize={getItemSize}
    width={300}
  >
    {Row}
  </List>
);

Analysis of the

What are the similarities and differences between the unfixed size and the fixed size in the last video? Think about it, we find that the whole process logic is the same, except when calculating the positioning of each element, because the size is different, the calculation method is different. Size inconsistencies require us to traverse the cumulative calculation of the actual size and position of each element. Simply said is in the fixed size of the basic implementation, update the auxiliary calculation function.

Realize the principle of

  1. Since the size is not fixed, we need to calculate the offset and size of each piece of data starting from index 0. In this way, we can divide the calculated data into the uncalculated data and the calculated data.
  2. The ones that have already been computed are cached in an object, and the ones that will be used in future use are retrieved directly from the cache.
  3. In the onScroll scroll event, we need to find the offset of the corresponding startIndex according to the offset. There are two cases here, which have been cached, then we can search from the cache interval. We can use binary search method to improve the search efficiency. If not cached, then you can use exponential search to narrow the search range, and then use binary search

implementation

As discussed in the previous section, we need to implement the following helper functions:

GetEstimatedTotalSize () {// getEstimatedTotalSize() {// getEstimatedTotalSize() {// StartIndex getStartIndexForOffset(offset) {// startIndex startIndex startIndex startIndex endIndex endIndex endIndex getStopIndexForStartIndex() {}

First mount some properties on the instance to cache the measured data:

InstanceProps = {ItemMetaDataMap: {}, // EstimatatEditemSize: EstimatEditemSize, // The default size given for each item is LastMeasureDindex: -1, // The index of the element that has been measured};

Then we add a helper method to retrieve the information corresponding to each item. If it is cached or not, it will be computed and saved, as follows:

getItemMetadata(props, index, instanceProps) { const { itemSize } = props; const { itemMetadataMap, lastMeasuredIndex } = instanceProps; If (index > LastMeasureDindex) {let offset = 0; if (itemMetadatamap) {let offset = 0; // By default, the first element is offset 0. If (LastMeasureDindex >= 0) {const ItemMetadata = LastMeasureDindex [LastMeasureDindex]; offset = itemMetadata.offset + itemMetadata.size; } for (let i = lastMeasuredIndex + 1; i <= index; i++) { let size = itemSize(i); itemMetadataMap[i] = { offset, size, }; offset += size; } instanceProps.lastMeasuredIndex = index; } return itemMetadataMap[index]; }

Then implement the above auxiliary functions one by one

getItemOffset && getItemSize

GetItemOffset = getItemOffset = getItemOffset (index) => getItemMetadata(props, index, instanceProps). Offset (index) => instanceProps.itemMetadataMap[index].size

getEstimatedTotalSize

Const getEstimatedTotalSize = ({ItemCount}, {ItemMetaMap, EstimatedEditemSize, {ItemCount}, {ItemMetaMap, EstimatedEditemSize, {ItemCount}, {ItemMetaMap, EstimatedEditemSize, lastMeasuredIndex } ) => { let totalSizeOfMeasuredItems = 0; if (lastMeasuredIndex >= 0) { const itemMetadata = itemMetadataMap[lastMeasuredIndex]; totalSizeOfMeasuredItems = itemMetadata.offset + itemMetadata.size; } const numUnmeasuredItems = itemCount - lastMeasuredIndex - 1; const totalSizeOfUnmeasuredItems = numUnmeasuredItems * estimatedItemSize; return totalSizeOfMeasuredItems + totalSizeOfUnmeasuredItems; };

getStartIndexForOffset

getStartIndexForOffset: (props, offset, instanceProps) =>
    findNearestItem(props, instanceProps, offset)

Here it needs to be emphasized that the search algorithm:

const findNearestItem = (props, instanceProps, offset) => { const { itemMetadataMap, lastMeasuredIndex } = instanceProps; // Get the offset offset of the last element that has been measured const lastMeasureUredItemOffset = lastMeasureDindex > 0? itemMetadataMap[lastMeasuredIndex].offset : 0; If (LastMeasuredItemOffset >= Offset) {// The query object is in the measured range, Directly using the binary search algorithm is used to return findNearestItemBinarySearch (props, instanceProps lastMeasuredIndex, 0, offset); } else {// Query target in unmeasured region, Use index lookup embedded binary search / / find the main search calculation is to avoid the whole data interval return findNearestItemExponentialSearch (props, instanceProps, Math. Max (0, lastMeasuredIndex), offset ); }}; // The implementation of binary search algorithm, there is nothing to talk about. const findNearestItemBinarySearch = ( props, instanceProps, high, low, offset ) => { while (low <= high) { const middle = low + Math.floor((high - low) / 2); const currentOffset = getItemMetadata(props, middle, instanceProps).offset; if (currentOffset === offset) { return middle; } else if (currentOffset < offset) { low = middle + 1; } else if (currentOffset > offset) { high = middle - 1; } } if (low > 0) { return low - 1; } else { return 0; }}; // the exponential search algorithm, there is nothing to say. const findNearestItemExponentialSearch = ( props, instanceProps, index, offset ) => { const { itemCount } = props; let interval = 1; while ( index < itemCount && getItemMetadata(props, index, instanceProps).offset < offset ) { index += interval; interval *= 2; } return findNearestItemBinarySearch( props, instanceProps, Math.min(index, itemCount - 1), Math.floor(index / 2), offset ); };