scenario

This was a problem I had in mind while writing a special React business component (virtual tree list), when I implemented a class that inherits arrays internally. You can also use this internally to access the array itself and the methods) and implement an internal filter and reset filter.

The first thing THAT came to my mind was to tag each data on initialization, take it out on filtering, put it back on reset and reorder it by tag.

class DataArr extends Array {
    constructor(data, key){
        super(a)this.dataMap = {}
        this.dataKey = key
        this.dataWhichBeFiltered = []
    }
    initData () {
        this.forEach((item, index) = > {
            this.initItem(item, {
                index
            })
        })
    }
    initItem (item, opt) {
        this.dataMap[item[this.dataKey]] = item
        item._index = opt.index
    }
    filter () {}
    resetFilter () {}
}

// usage
const data = new DataArr(arr)

data.filter(item= > item.a === 1)
data.resetFilter()

Copy the code

And then there’s the problem. In this case we can’t just use array.prototype. filter because this method just returns the new Array, We can’t write code like this = this.filter(item => item.a === 1).

process

To write an array filter by itself, I started with the idea of traversing the array in reverse order and then using splice to extract the values one by one, like this

filter (fn) {
    for (let i = this.length - 1; i >= 0; i--) {const item = this[i]
        if(!!!!! fn(item)) {const delItem = this.splice(i, 1) [0]
            this.dataWhichBeFiltered.push(delItem)
        }
    }
}
Copy the code

The result of this implementation is indeed feasible, but it has considerable hidden dangers. So far, many people believe that SPLice is a very common O(1) operation, just like pop and push methods. In fact, splice performance is very poor. I asked some of my front-end colleagues, and they didn’t see much of a problem either, and I’ve sometimes seen comments like “Splice is really cool” while walking around the Nuggets.

In addition to the above approach, I came up with a solution that looks slow, but is actually nearly 100 times faster than loop splice, which loops to mark the items that need to be filtered, and then sorts the items to the end and cuts them off.

filter (fn) {
    let index = 0
    for (let i = this.length - 1; i >= 0; i--) {const item = this[i]
        if(!!!!! fn(item)) { item.willBeFiltered =1
            index ++
        }
        else item.willBeFiltered = 0
    }
    this.sort((a, b) = > b.willBeFiltered - a.willBeFiltered)
    this.dataWhichBeFiltered = this.splice(i)
}
Copy the code

The resulting graph from the test in the browser Console

Directly traverse splice in reverse order

After sorting, splice, data volume of 1W is not much, but occupying more than 1s already has a serious sense of lag.

originally

Splice is slow because it inserts and removes arrays, unlike linked lists, which simply remove the nodes to be removed and join the prev and next nodes.

The elements of an array are stored in a contiguous block of memory and can only be accessed by indexes.

That is to say, the storage of array is a sequence, using an array subscript visit each array element, when we are “simple” to remove or insert in the middle of the array of one or more array elements, so need to change the corresponding elements to all elements after a subscript, such behavior brings a lot of wear and tear.

Original array [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Arr. Splice (4,1) [1, 2, 3, 4, 6, 7, 8, 9, 10]

The change of the array (removed before - removed) = > 1 0 0 = > 1 1 = 1 = > > 2 2 2 2 = > 3 3 = = > 3 > 4 3 = 4 = > > 4 5 4 = = > > 6 5 = > = = > > 5 6 7 = > = > = > 7 8 7 => 8 7 => 9 8 => 9 8 => 10 9 => 10 9 => 10Copy the code

The impact of this change is related to the length of the array and the number of subscripts that need to be adjusted. In addition to splice, another method with the same performance loss is the unshift method with the same insertion capability.

tips

In addition to the above issues, I also found a casual change brought about by an ES6. Datafilter, which comes through the filtered window, is a filter that comes through the filtered window, which comes through the filtered window, which comes through the filtered window.

    this.dataWhichBeFiltered.forEach(data => this.push(data))
    this.sort((a, b) => a._index - b._index)
Copy the code

At the same time, I can’t write this = this.concat(this. dataatus), just loop one by one and push it back to the original array.

But I randomly tried the push method, it turns out that push can pass multiple parameters!

arr.push(element1, … , elementN)

In the old ES5 environment it was rare to pass multiple arguments to create multiple array items (because you can’t dynamically pass arguments to a push method), but now thanks to the new extension operator in ES6, we can just say this.push(… Enclosing beFilteredData). The result was very satisfying in every way. In the previous code, there was const result = arr1.concat(arr2).

conclusion

To summarize, never use splice or unshift in an array loop in a front-end browser environment, because it can be a performance drain when the amount of data exceeds a certain amount. Because the elements of an array are stored in a contiguous block of memory that can only be accessed through indexes, a series of cascading changes can occur when an array is deleted or inserted, resulting in poor performance.

I’m thinking of a famous guy who wrote a quick row where a loop called splice changed the “fast” row to “slow” row. It’s been a long time since I was ridiculed by the gods. Now they’re all winners, and I’m still working late at the office.

This is Roxz, please feel free to like my article. I will silently thank you in spirit for your encouragement.