Following up on the long list of front-end development, I introduced the list of “visual area renders” and wrote a simplified example to show how to do it. Such lists are commonly called Virtual lists and are referred to as “Virtual lists” in this article. In this article, the author will strengthen the simplified example in the previous article step by step into a relatively general, excellent performance of virtual list components, in order to explain the realization of virtual list ideas. You don’t need to read the previous article to read this article, but the code is implemented using vue.js, so you need experience with vue.js. In addition, provides the various steps of JSFiddle, if you do not understand the place, recommended by modifying JSFiddle online debugging.
Implementation approach
Before we get into what follows, let’s make a brief definition of virtual lists.
Because the time cost of creating and rendering DOM elements is high, the time required for a complete rendering list is unacceptable in the case of big data. One solution is to render only the “visible area” in any case to achieve extremely high first rendering performance.
A virtual list is a list of “viewable areas rendered”. Two basic concepts are important:
- Scrollable area: Suppose there are 1000 items of data, and each list item is 30 in height, then the height of the scrollable area is 1000 * 30. When the user changes the current scroll value of the list’s scroll bar, the contents of the visible area change.
- Visible area: For example, if the height of the list is 300 and there is a vertical scroll bar to scroll to the right, the visually visible area is the visible area.
To realize the virtual list is to deal with the change of the visible area after the scroll bar is rolled. The specific steps are as follows:
- StartIndex to calculate the start data of the current visible region
- Computes the endIndex of the current visible region end data
- Calculates the data for the current visible area and renders it to the page
- Calculate the startIndex data offset startOffset in the entire list and set it to the list
Please refer to the following figure to understand the above steps:
The simplest example
This section explains how to translate the above steps into code to make the logic actually work in the browser.
To keep this example simple, I made a configuration that each list item should be 30px high. Under this convention, the core JavaScript code is no more than 10 lines, but the visible area can be fully rendered and updated.
The first thing we need to think about is how to implement the HTML and CSS of the virtual list. We added several styles:
- List elements (.list-view) use relative positioning
- Use an invisible element (.list-view-phantom) to prop up the list and make the scroll bar appear
- The visible elements of the list (.list-view-content) use absolute positioning, with left, right, and top set to 0
The CSS code is as follows:
.list-view {
height: 400px;
overflow: auto;
position: relative;
border: 1px solid #aaa;
}
.list-view-phantom {
position: absolute;
left: 0;
top: 0;
right: 0;
z-index: -1;
}
.list-view-content {
left: 0;
right: 0;
top: 0;
position: absolute;
}
.list-view-item {
padding: 5px;
color: #666;
line-height: 30px;
box-sizing: border-box;
}
Copy the codeThe HTML code looks like this (ignoring the event and variable bindings) :
<template>
<div
class="list-view"
@scroll="handleScroll">
<div
class="list-view-phantom"
:style="{
height: contentHeight
}">
</div>
<div
ref="content"
class="list-view-content">
<div
class="list-view-item"
:style="{
height: itemHeight + 'px'
}"
v-for="item in visibleData">
{{ item.value }}
</div>
</div>
</div>
</template>
Copy the codeThe JavaScript code is as follows:
export default { name: 'ListView', props: { data: { type: Array, required: true }, itemHeight: { type: Number, default: 30 } }, computed: { contentHeight() { return this.data.length * this.itemHeight + 'px'; } }, mounted() { this.updateVisibleData(); }, data() { return { visibleData: [] }; }, methods: { updateVisibleData(scrollTop) { scrollTop = scrollTop || 0; const visibleCount = Math.ceil(this.$el.clientHeight / this.itemHeight); const start = Math.floor(scrollTop / this.itemHeight); const end = start + visibleCount; this.visibleData = this.data.slice(start, end); this.$refs.content.style.webkitTransform = `translate3d(0, ${ start * this.itemHeight }px, 0)`; }, handleScroll() { const scrollTop = this.$el.scrollTop; this.updateVisibleData(scrollTop); }}}Copy the code- Rendering the visibleData is done with vue.js, using elements from the visibleData array
- The virtual list update logic is the updateVisibleData method, the author added some comments to this method:
updateVisibleData(scrollTop) { scrollTop = scrollTop || 0; const visibleCount = Math.ceil(this.$el.clientHeight / this.itemHeight); Const start = math.floor (scrollTop/this.itemheight); Const end = start + visibleCount; This.visibledata = this.data.slice(start, end); // Calculate the data corresponding to the visible area, Let the Vue. Update this js. $refs. Content. style.css. WebkitTransform = ` translate3d (0, ${start. * this itemHeight} px, 0) `; // Set the top of the visible area to the position of the starting element in the entire list (transform is used for better performance)}Copy the code- In order for the virtual list to have scroll bars properly present, the calculated property contentHeight of vue.js is used to calculate the true height of the scroll area
This simplest implementation can be run online from here. It is recommended that you make some changes to the code and then run it to deepen your understanding of the above.
Remove height restrictions
How does the code implement this if you break the limitation that every element is the same height in the simplest implementation?
In the example, the itemHeight attribute is used to determine the height of a list item. There are two options to implement the dynamic height of a list item:
- Add a prop of array type. The height of each list item is indexed
- Add a method to get the height of a list item, pass item and index to the method, and return the height of the corresponding list item
The second option is obviously a little more flexible, so we add an itemSizeGetter property to get the height of each list item.
- Add the itemSizeGetter property as follows:
itemSizeGetter: {
type: Function
}
Copy the code- Because each row is different in height, the contentHeight algorithm needs to be updated with the following code:
contentHeight() {
const { data, itemSizeGetter } = this;
let total = 0;
for (let i = 0, j = data.length; i < j; i++) {
total += itemSizeGetter.call(null, data[i], i);
}
return total;
}
Copy the code- In the previous example, calculating the start index and end index of a range required a simple calculation using itemHeight. FindNearestItemIndex = findNearestItemIndex = findNearestItemIndex = findNearestItemIndex = findNearestItemIndex
findNearestItemIndex(scrollTop) {
const { data, itemSizeGetter } = this;
let total = 0;
for (let i = 0, j = data.length; i < j; i++) {
const size = itemSizeGetter.call(null, data[i], i);
total += size;
if (total >= scrollTop || i === j -1) {
return i;
}
}
return 0;
}
Copy the code- Similarly, a list item in the top of the list can also be calculated simply by index, now need to add a method to calculate, the implementation code is as follows:
getItemSizeAndOffset(index) {
const { data, itemSizeGetter } = this;
let total = 0;
for (let i = 0, j = Math.min(index, data.length - 1); i <= j; i++) {
const size = itemSizeGetter.call(null, data[i], i);
if (i === j) {
return {
offset: total,
size
};
}
total += size;
}
return {
offset: 0,
size: 0
};
}
Copy the code- The updateVisibleData method makes a simple update based on the above changes, as follows:
updateVisibleData(scrollTop) {
scrollTop = scrollTop || 0;
const start = this.findNearestItemIndex(scrollTop);
const end = this.findNearestItemIndex(scrollTop + this.$el.clientHeight);
this.visibleData = this.data.slice(start, Math.min(end + 1, this.data.length));
this.$refs.content.style.webkitTransform = `translate3d(0, ${ this.getItemSizeAndOffset(start).offset }px, 0)`;
}
Copy the codeThe added implementation of itemSizeGetter can be run online from here, and you can modify the return value of itemSizeGetter to see if it responds properly.
Caching results
Although the previous example implemented the dynamic height of list items, the size and offset calculations of each list item are not cached, and the itemSizeGetter is called repeatedly during initial rendering and scrolling updates, which is not ideal. To optimize this performance, you need to cache the size and offset information and get the results directly from the cache the next time.
In the normal case, the user’s scrolling starts at the top and is continuous. A very simple caching strategy can be adopted to record the last calculated size, offset index.
- Call this variable lastMeasuredIndex, and the default value is -1; The variable that stores the cached result is called sizeAndOffsetCahce and is of type object.
data() {
return {
lastMeasuredIndex: -1,
startIndex: 0,
sizeAndOffsetCahce: {},
...
};
}
Copy the code- The height of the cached list item is calculated by modifying the getItemSizeAndOffset method.
getItemSizeAndOffset(index) {
const { lastMeasuredIndex, sizeAndOffsetCahce, data, itemSizeGetter } = this;
if (lastMeasuredIndex >= index) {
return sizeAndOffsetCahce[index];
}
let offset = 0;
if (lastMeasuredIndex >= 0) {
const lastMeasured = sizeAndOffsetCahce[lastMeasuredIndex];
if (lastMeasured) {
offset = lastMeasured.offset + lastMeasured.size;
}
}
for (let i = lastMeasuredIndex + 1; i <= index; i++) {
const item = data[i];
const size = itemSizeGetter.call(null, item, i);
sizeAndOffsetCahce[i] = {
size,
offset
};
offset += size;
}
if (index > lastMeasuredIndex) {
this.lastMeasuredIndex = index;
}
return sizeAndOffsetCahce[index];
}
Copy the code- The findNearestItemIndex method also uses itemSizeGetter to get the size of the element. We can change this to getItemSizeAndOffset to get the size of the element.
findNearestItemIndex(scrollTop) {
const { data, itemSizeGetter } = this;
let total = 0;
for (let i = 0, j = data.length; i < j; i++) {
const size = this.getItemSizeAndOffset(i).size;
// ...
}
return 0;
}
Copy the codeAfter using the cache, you can click here to run the code online. If you don’t see a significant improvement in performance, you can try changing the array size to 20000 or 50000.
Optimized calculations for contentHeight
If you add a console.log line to itemSizeGetter, you will find that contentHeight executes all the itemSizeGetter for the first time during initial rendering.
To solve this problem, we need to introduce another attribute, estimatedItemSize. The meaning of this attribute is that an estimate is made for elements whose height has not been calculated, so contentHeight is equal to the height of cached list items plus the number of uncached list items * estimatedItemSize.
- The first thing you need to do is add this property to the component, which defaults to 30, as follows:
estimatedItemSize: {
type: Number,
default: 30
}
Copy the code- Because of the need to know the height of the calculated height of the list items, and need to increase the methods getLastMeasuredSizeAndOffset, code is as follows:
getLastMeasuredSizeAndOffset() {
return this.lastMeasuredIndex >= 0 ? this.sizeAndOffsetCahce[this.lastMeasuredIndex] : { offset: 0, size: 0 };
}
Copy the code- The code modified according to the above algorithm is as follows:
contentHeight() { const { data, lastMeasuredIndex, estimatedItemSize } = this; let itemCount = data.length; if (lastMeasuredIndex >= 0) { const lastMeasuredSizeAndOffset = this.getLastMeasuredSizeAndOffset(); return lastMeasuredSizeAndOffset.offset + lastMeasuredSizeAndOffset.size + (itemCount - 1 - lastMeasuredIndex) * estimatedItemSize; } else { return itemCount * estimatedItemSize; }}Copy the codeContentHeight optimized implementations can be run online from here, and you can add console.log to the itemSizeGetter property to see how the itemSizeGetter works.
Optimize search performance for cached results
There is actually room for optimization in cached virtual lists, such as findNearestItemIndex, which is searched sequentially and in O(N) time. In fact, the computed result of list items is naturally an ordered array, and binary lookup can be used to optimize the search performance of cached results, reducing the time complexity to O(lgN).
- Add the binarySearch method to the component as follows:
binarySearch(low, high, offset) {
let index;
while (low <= high) {
const middle = Math.floor((low + high) / 2);
const middleOffset = this.getItemSizeAndOffset(middle).offset;
if (middleOffset === offset) {
index = middle;
break;
} else if (middleOffset > offset) {
high = middle - 1;
} else {
low = middle + 1;
}
}
if (low > 0) {
index = low - 1;
}
if (typeof index === 'undefined') {
index = 0;
}
return index;
}
Copy the codeThis binary search is a little bit different than a normal binary search, except that it doesn’t return -1 in any case, so you can think about why the logic works that way.
- Modify the findNearestItemIndex method to use binary lookup for cached results as follows:
findNearestItemIndex(scrollTop) {
const { data, itemSizeGetter } = this;
const lastMeasuredOffset = this.getLastMeasuredSizeAndOffset().offset;
if (lastMeasuredOffset > scrollTop) {
return this.binarySearch(0, this.lastMeasuredIndex, scrollTop);
} else {
// ...
}
return 0;
}
Copy the codeAn implementation that uses binary lookup can be run online from here and is no different in effect from the previous example.
Optimize search performance for uncached results
The search for uncached results is still sequential. There are two ideas for search optimization of uncached results:
- Find the number of entries at a time (a reasonable number is contentHeight/estimatedSize), find indexes that exceed your search results, and then use binary search
- Search by number of exponents, such as 1, 2, 4, 8, 16, 32… To find the range, and then use binary search
The author chooses the second method, which is named Exponential Search. The Search process of this algorithm can be seen in the following figure:
- Add exponentialSearch as follows:
exponentialSearch(scrollTop) {
let bound = 1;
const data = this.data;
const start = this.lastMeasuredIndex >= 0 ? this.lastMeasuredIndex : 0;
while (start + bound < data.length && this.getItemSizeAndOffset(start + bound).offset < scrollTop) {
bound = bound * 2;
}
return this.binarySearch(start + Math.floor(bound / 2), Math.min(start + bound, data.length), scrollTop);
}
Copy the codeThis algorithm is also slightly different from the standard Exponential Search, the main difference being that the Search will not start from scratch, but will start at the position of the lastMeasuredIndex.
- Modify the findNearestItemIndex method as follows:
findNearestItemIndex(scrollTop) { const { data, itemSizeGetter } = this; const lastMeasuredOffset = this.getLastMeasuredSizeAndOffset().offset; if (lastMeasuredOffset > scrollTop) { return this.binarySearch(0, this.lastMeasuredIndex, scrollTop); } else { return this.exponentialSearch(scrollTop); }}Copy the codeThe optimized implementation can be run online from here, and you can add console.log to the code to observe the execution of the search.
The resources
In the process of writing this article, THE author referred to a lot of open source projects, and also referred to a lot of articles, which are of great help to me:
- React Tiny Virtual List
- React Virtualized
- EstimatedRowHeight adaptive Cell
Write in the last
If you’re interested in learning how to implement a virtual list, hopefully this article will help.
The optimizations that can be made for a virtual list of static data are basically covered in this article. If you’re still interested in this topic, try adding two features to virtual lists:
- Dynamically update the height of list items based on the render results
- Invalidate the cache after the data is updated and keep the range of invalidated caches as small as possible
Thank you for your patience in reading this article. If there are any mistakes in this article, or if you have any questions, please leave them in the comments section directly.