This period of time to write a pile of source code analysis, this article would like to change the taste, with you to share a case I met in the work. After all, as a worker, in addition to looking at the source code to go to work, brick or to move. This article will share a story of using the right data structure for performance optimization to dramatically improve response times by hundreds of times.
The thing is, I am working for a foreign company. We have an offline APP for foreigners to sell goods, such as clothes, shoes, cola and so on. One day, the product manager came to me with a requirement to support three layers of product options. When I heard this requirement, my first reaction was that I didn’t seem to have seen three layers of product options. After all, I am also an experienced hand cutter for more than ten years. The general product options seem to have two layers at most.
This shoe is two product options, one is color, the other is size, there are 11 colors and 11 sizes in total. To test my intuition, I opened all the shopping apps on my phone, including Taobao, JINGdong, Pinduoduo and Suning. Of the products I’ve seen, I haven’t found a single product that has three options, two at most.
A working example of this article has been uploaded to GitHub for fun:Github.com/dennis-jian…
Why doesn’t anyone do the three-tier option?
If one or two families don’t do it, it may be because each family has different needs, but everyone doesn’t do it and feels something is wrong. After careful analysis, I think there may be two reasons for not doing the three-tier option:
1. This may be a bogus requirement
The shoes above come in 11 colors and 11 sizes, meaning these options are followed by 11 by 11, a total of 121 items. If I had a third option, if I had 11 options for the third option, then the total number of items would be 11 * 11 * 11, or 1,331 items, and a lot of stores might not have 1,331 items. That is to say, the third layer of options may be a fake demand, users do not have so many options on the third layer, or for the shoes above, in addition to color, size, must add another layer, that is, men’s shoes and women’s shoes. For men’s shoes and women’s shoes, the size and size are very different. Generally, they are not put under one product. It is more common to divide them into two products, each with its own color and size.
2. Performance problems occur
It’s not that hard to add a third layer of options, just a few more clickable buttons, and the clickable logic is not that different from the two layers. But on further reflection, I saw that he had potential performance issues. In the case of the shoes above, the data I got from the back-end API looks like this:
const merchandise = {
// Variations contain all the options
variations: [{name: The 'color'.values: [{name: 'Limited Edition 574 Navy Blue' },
{ name: 'Limited Edition 574 White Powder' },
// There are 9 more] {},name: 'size'.values: [{name: '38' },
{ name: 'and' },
// There are 9 more]},],// The products array holds all the products
products: [{id: 1.price: 208.// The variations with the above variations are in the variationMappings for each commodity
variationMappings: [{name: The 'color'.value: 'Limited Edition 574 White Powder' },
{ name: 'size'.value: '38'}},],// There are more than 100 products below]}Copy the code“Merchandise. Variations are an array with several levels of options, and there are several objects in this array. The name of each object is the name of the current level, and values are the options contained in the current level. So merchandise. Variations can be directly displayed on the UI, rendering them hierarchically as buttons.
In the picture above, the user selects the limited edition 574 white powder on the first layer, and the non-existent goods such as 40 and 41 on the second layer are automatically gray out. To do this, use the above data structure. When the user selects a limited edition 574 chalk, we will walk through the merchandise.products array. One of the items in this array will be an item. For my current project, if the item can be sold, it will be in the array merchandise. Products. If it cannot be sold, it will not be in the array at all. For example, limited edition 574 chalk, a 40-yard combination will not appear in merchandise. Products. If you do not find this combination, it will turn gray.
So for the limited edition 574 chalk, 40 shoe, to know if it needs to be grayed, I need to traverse the entire array of merchandise. Products. According to the 11 colors and 11 sizes mentioned above, there will be a maximum of 121 products, that is, a maximum of 121 searches. Similarly, to know whether the limited edition 574 white powder, 41 can be sold or not, and to traverse the entire commodity array, 11 sizes need to traverse the entire commodity array 11 times. For the two-tier options, 11 * 11 is a lot, and a hundred operations per size probably won’t cause serious performance problems. But if you add another layer of options, if you add another layer of options if you have 11 options, then all of a sudden you go from O(n2)O(n^2)O(n2) to O(N3)O(n^3)O(n3)! Now our total number of goods is 11 * 11 * 11, namely 1331 goods. If the third layer is gender, now IN order to know whether the limited edition of 574 white powder, 40 and male can be sold, I need to traverse 1331 goods. If it takes 20ms to traverse 121 goods, it is relatively smooth. It takes 220ms to go through 1331 items, which is a noticeable stutter, and on some devices with poor hardware, this stutter is even worse and becomes unacceptable. In addition, our APP uses React Native technology, which has poor performance compared to the original one. In this case, users may get angry and uninstall it!
I approached the product manager with the above questions about requirements and concerns about performance and had the following conversation:
Me: Dude, I found that there seems to be no APP in the market that supports three-tier options. Is there a problem with this requirement? Besides, the complexity of three-tier options is exponentially increasing compared to two-tier options, and there may be performance problems, so users will get stuck when using them.
Product manager: Brother, what you are looking at are domestic apps, but this one is for foreigners. Foreigners are used to it. If we want to sell, we have to meet their needs. This is to add a few buttons on the UI, the design is the same as before, give you two days enough
I: ah! ? Er… Oh…
I also don’t know a few foreigners, I dare not ask again, all said is the user demand, I must meet the product to sell out, the product sold out I can eat, think of a way to solve it!
The solution
This is not complicated because the three-tier option can continue to iterate through the array as the two-tier option does, but the complexity increases exponentially from O(n2)O(n^2)O(N3)O(n^3)O(n3) to O(n^3)O(n3). Now, I need to think about other options to improve performance. After thinking about it, I realized that this exponential increase in complexity was due to our traversal of the entire array. If I could find a way not to traverse the array, I could immediately find out if the limited edition item 574 white powder, 40 male existed.
The specific problem translates to finding an item in an array that matches a specific filter. Well, search, that sounds familiar, and now I need to go through the array, because there’s no direct correspondence between the search criteria and the item, and if I can establish a direct correspondence, I can find it immediately, right? It came to me: find a tree. If I reorganize these hierarchies and organize them into a tree with each item corresponding to a leaf node in the tree, I can reduce the search complexity of the three-tier options from O(n3)O(n^3)O(n3) to O(1)O(1)O(1) O(1).
Two-level search tree
To illustrate the algorithm, let me simplify the problem by assuming that we now have two layers of options, color and size, with two options for each layer:
- Color: white, red
- Size: 39,40
We now have 4 items:
- Product # 1: productId is 1, white, size 39
- Product 2: productId is 2, white, 40 yards
- Product Number 3: productId is 3, red, size 39
- Item 4: productId is 4, red, 40 yards
If we take the simplest approach, in order to find out whether the red size 39 shoes exist, we need to traverse all the four items, the time complexity of this time is O(n2)O(n^2)O(n2). But if we build a tree like this, we can reduce the time complexity to O(1)O(1)O(1) :
The tree above, we ignore the root node, which is useless in this case, just the entrance to a tree. The first layer of the tree is our first color, and the second layer is our second color, but each color node corresponds to all sizes. In this way, the last leaf node of the second layer actually corresponds to a specific commodity. Now we need to find the red size 39 shoes, just look at the red arrow points to the node has goods on the line.
How do you represent this data structure in JS? It’s very simple, just one object, like this:
const tree = {
"Color: white": {
Size: 39: { productId: 1 },
"Size: 40": { productId: 2}},"Color: red": {
Size: 39: { productId: 3 },
"Size: 40": { productId: 4}}}Copy the codeSo with this data structure above, we’re going to look forredthe39The values directlyTree [" color: red "][" size: 39"]That’s it. The complexity is instantaneous
.
Three-level search tree
Once you understand the above two-level search tree, it’s easy to extend it to three levels, just add one more. If we now have a third layer of options for gender and two options for male and female, our search tree would look something like this:
The corresponding JS object:
const tree = {
"Color: white": {
Size: 39: {
"Gender: Male": { productId: 1 },
"Gender: Female": { productId: 2}},"Size: 40": {
"Gender: Male": { productId: 3 },
"Gender: Female": { productId: 4}}},"Color: red": {
Size: 39: {
"Gender: Male": { productId: 5 },
"Gender: Female": { productId: 6}},"Size: 40": {
"Gender: Male": { productId: 7 },
"Gender: Female": { productId: 8}}}},Copy the codeSimilarly, let’s say we’re looking for onewhiteThe,39.maleShoes, directTree [" color: white "][" size: 39"][" gender: male "]That’s it, and so is the time
.
Write the code
All of the above algorithms are understood, the rest is to write code, the main code we need to write is to use the data returned by the API to build a tree on the top of this structure, one traversal can do. For example, the API returns a structure like this:
const merchandise = {
variations: [{name: The 'color'.values: [{name: 'white' },
{ name: 'red']}, {},name: 'size'.values: [{name: 'and' },
{ name: '40']}, {},name: 'gender'.values: [{name: 'male' },
{ name: 'woman'}},]],products: [{id: 1.variationMappings: [{name: The 'color'.value: 'white' },
{ name: 'size'.value: 'and' },
{ name: 'gender'.value: 'male'}}]// There are 7 items left, which I won't repeat]}Copy the codeTo convert the data returned by the API into our tree structure, we write a method:
function buildTree(apiData) {
const tree = {};
const { variations, products } = apiData;
// First use variations to build tree structures. The default value of leaf nodes is NULL
addNode(tree, 0);
function addNode(root, deep) {
const variationName = variations[deep].name;
const variationValues = variations[deep].values;
for (let i = 0; i < variationValues.length; i++) {
const nodeName = `${variationName}:${variationValues[i].name}`;
if (deep === 2) {
root[nodeName] = null
} else {
root[nodeName] = {};
addNode(root[nodeName], deep + 1); }}}// Then iterate over products to fill the leaves of the tree with values
for (let i = 0; i < products.length; i++) {
const product = products[i];
const { variationMappings } = product;
const level1Name = `${variationMappings[0].name}:${variationMappings[0].value}`;
const level2Name = `${variationMappings[1].name}:${variationMappings[1].value}`;
const level3Name = `${variationMappings[2].name}:${variationMappings[2].value}`;
tree[level1Name][level2Name][level3Name] = product;
}
// Finally return the constructed tree
return tree;
}
Copy the codeThen use the above API to test the data run to see the effect, and find that the built tree fully meets our expectations:
Is that all?
So now we have a search tree, and when the user selects red, 40 yards, in order to figure out if the guy can click, we don’t have to go through all the items, we can just value from this structure. But is that it? No! Take a closer look at the data structure we constructed. The hierarchy is fixed. The first layer is color, the second layer is size, the third layer is gender, and the corresponding goods are placed on the third layer of gender. What that means is that with this structure, the user has to follow the exact rules, first the color, then the size, and then we’ll see which one of these is grayed out. If he doesn’t follow this order, for example, he chooses male first, then size 40, then we should calculate the last level of color which should be grayed out. But we cannot calculate this using the above structure, because we do not have the object tree[” gender: male “][” size: 40″].
How can I do that? We don’t have a sex-size-color tree, so let’s build one! That’s a method, of course, but the user could have other order of operations, and how many trees would we need to cover all the possible order of operations? This is actually a full permutation of sex, size, and color, so A33A_3^3A33, six trees. Lazy people like me ask me to build six trees and I’m too lazy to do it. If you don’t build so many trees, you can’t cover the demand, what do you do? Is there a lazy way? Can I get around this problem if I can do something about the requirements? With this in mind, I came up with two ideas:
1. Give a default value.
By default, the first item available for sale is selected when the user opens the product details page. This gives the user a default order by selecting a value in color-size-gender order from the start.
2. Does not provide the cancel function, can only switch options
If the cancel function is provided, he will cancel the default option of color – size – gender provided by us, and can choose gender – size – color again. There is no cancel function, can only be toggled by selecting other options, can only be changed from red to white, can not cancel red, other same. So we can always ensure that the color-size-gender order, the user just selects different values for each level, the hierarchy doesn’t change, and our search tree is always valid. I also found that some shopping sites can’t cancel their options, so I wonder if they have similar problems.
These two changes to the requirements did not have much impact on the user experience and after consulting with the product manager, she agreed. So I killed the other 5 trees on demand, lazy success!
Here’s what three layers of options look like in action:
One more thing
In the previous scenario, we solved the lookup performance problem, but introduced a new problem, that is, the need to create this lookup tree. Creating the search tree still requires a walk through the list of items, which is inevitable, and for a smoother user experience, we should try to hide the creation process from the user’s perception. So what I’m doing here is I’m integrating it into the load state of the product detail page, so the user clicks into the product detail page, and we’re going to go to the API to get the data, and inevitably there’s going to be a load state, and there’s going to be a spin. I’ve done this loop as well, and the loop ends when the API data is returned and the lookup tree is created. This theoretically lengthens the loop time, but local traversal is slower than a network request, so it’s not noticeable to the user. When the rotation is over, all the data is ready, and the user operations are O(1)O(1)O(1) complexity, making it really smooth
Why not let the back end create this tree?
If you want to create a tree on the front end, you can use it to create a tree on the back end. If you want to create a tree on the front end, you can use it to create a tree on the back end. Just kidding, the truth is that the product API is a microservice maintained by another team, and the data they provide is not only used by my terminal APP, but also used by other products of the company, so it is too big to change the return structure.
Encapsulates the code
In fact, the implementation of our scheme itself is relatively independent, if other people use it, it doesn’t care whether you are a tree or a grass, as long as you pass in the selection condition, can return the correct goods, so we can encapsulate it as a class.
class VariationSearchMap {
constructor(apiData) {
this.tree = this.buildTree(apiData);
}
// This is how the tree was constructed
buildTree(apiData) {
const tree = {};
const { variations, products } = apiData;
// First use variations to build tree structures. The default value of leaf nodes is NULL
addNode(tree, 0);
function addNode(root, deep) {
const variationName = variations[deep].name;
const variationValues = variations[deep].values;
for (let i = 0; i < variationValues.length; i++) {
const nodeName = `${variationName}:${variationValues[i].name}`;
if (deep === variations.length - 1) {
root[nodeName] = null;
} else {
root[nodeName] = {};
addNode(root[nodeName], deep + 1); }}}// Then iterate over products to fill the leaves of the tree with values
for (let i = 0; i < products.length; i++) {
const product = products[i];
const { variationMappings } = product;
const level1Name = `${variationMappings[0].name}:${variationMappings[0].value}`;
const level2Name = `${variationMappings[1].name}:${variationMappings[1].value}`;
const level3Name = `${variationMappings[2].name}:${variationMappings[2].value}`;
tree[level1Name][level2Name][level3Name] = product;
}
// Finally return the constructed tree
return tree;
}
// Add a method to search for items with the same parameter structure as API data variationMappings
findProductByVariationMappings(variationMappings) {
const level1Name = `${variationMappings[0].name}:${variationMappings[0].value}`;
const level2Name = `${variationMappings[1].name}:${variationMappings[1].value}`;
const level3Name = `${variationMappings[2].name}:${variationMappings[2].value}`;
const product = this.tree[level1Name][level2Name][level3Name];
returnproduct; }}Copy the codeAnd then when you use it, just new it:
const variationSearchMap = new VariationSearchMap(apiData); // Create an instance
// Then you can use this instance to search
const searchCriteria = [
{ name: The 'color'.value: 'red' },
{ name: 'size'.value: '40' },
{ name: 'gender'.value: 'woman'}];const matchedProduct = variationSearchMap.findProductByVariationMappings(searchCriteria);
console.log('matchedProduct', matchedProduct); // { productId: 8 }
Copy the codeconclusion
This paper describes a demand I actually met in my work, and shares my implementation and optimization ideas for your reference. My solution may not be perfect, but if you have a better solution, please feel free to discuss it in the comments section
A working example of this article has been uploaded to GitHub for fun:Github.com/dennis-jian…
To recap the main points of this article:
- The requirement to be implemented in this article is a three-tier option for a commodity.
- When the user selects two layers, the third layer should automatically calculate which can and cannot be sold.
- Since there is no direct correspondence between back-end API return options and items, we need to traverse all items to find out whether they can or can’t be sold.
- When the total number of items is small, traversal of all items may not cause significant performance problems.
- But as the selection increases to three levels, the number of items increases exponentially, and performance issues become apparent.
- For performance problems such as O(n3)O(n^3)O(N3) that were foreseen when we wrote the code, we didn’t wait for bugs to be reported. We solved them at development time.
- This example is solving a lookup problem, so I thought of building a tree and reducing O(n3)O(n^3)O(n3) down to O(1)O(1)O(1).
- However, one tree does not cover all user actions; it takes six trees to cover all user actions.
- In order to be lazy, I discussed with the product manager, adjusted the requirements and interactions and cut down 5 trees. The real reason is that too many trees take up more memory and are difficult to maintain. Performance optimization can sometimes be achieved by adjusting requirements and interactions appropriately, and performance optimization can think about interaction and technology together.
- The search module of the tree can be wrapped separately into a class that external consumers can call the interface lookup without knowing the details.
- Front-end point-to-point data structures are still useful and necessary in scenarios like this one.
At the end of this article, thank you for your precious time to read this article. If this article gives you a little help or inspiration, please do not spare your thumbs up and GitHub stars. Your support is the motivation of the author’s continuous creation.
Welcome to follow my public numberThe big front end of the attackThe first time to obtain high quality original ~
“Front-end Advanced Knowledge” series:Juejin. Cn/post / 684490…
“Front-end advanced knowledge” series article source code GitHub address:Github.com/dennis-jian…