Recently, THERE was a demand to create a product details page similar to that of jd.com or Taobao, and one of the functions was the query of product SKU selection

As shown in the figure above, network type, body color, package type, and storage capacity are all SKU attributes. After all SKU attributes are selected, they will be combined into a complete SKU, corresponding to a specific product. Then, information such as inventory and price of the product corresponding to this SKU can be given

In addition, when some SKU properties are selected, the SKU combination whose inventory is 0 under the current condition will be calculated automatically according to the SKU properties that have been selected, and the interaction that the button is disabled will be given

The start when receiving the demand, the demand of the backend and the front end of the group cooperation friends all think this is a difficult point, need a good research, and I was evil spirit’s smile, don’t think it is a combination, algorithm can write write, can’t write a big deal for a loop through violence, little scene

However, when I started working on it, I realized that, unlike usual, the code couldn’t be written with my eyes closed

Implementation approach

When I found that this function was a little difficult, I started to search the relevant articles on the Internet, and then found that the relevant articles seemed to be relatively good. “You don’t know to what an array of ten kinds of usage of the prototype chain man-of-the-match analysis what my functional programming can’t be so lovely,” what the three years’ experience with a front companies interview all don’t, look incredibly need with the brain, and related articles is less, remove those copy to copy, and I didn’t search, A few really useful ones:

  • Realization of SKU combinatorial query algorithm on e-commerce platform
  • Sku multidimensional attribute state judgment algorithm
  • Taobao SKU combination query algorithm implementation

After I read it, I was lost in thought

Since plastic dinosaurs are made of plastic, and plastic comes from oil, which is turned into ancient dinosaur corpses. So, plastic dinosaurs are real dinosaurs?

These articles describe the feeling is not very clear, the main is not complete running code, see the cloud in the fog, according to what they say to do, it is better than I write a new, but still some reference

  • First, give me some groupsSKUProperties of, then according to the combination of these propertiesskuCertainly can be listed all, and considering the real business use, the attributes are not too many, do not need to care about extreme cases, so even exhaustive, there is no big loss of performance;
  • Then, since poor point to the set of all possible, you can calculate the combination of each corresponding price and inventory information, so that nature can form a dictionary, no matter choose what combination, can quickly from the dictionary query to the corresponding information such as price and inventory, i.e., according to the space in time, As long as this dictionary is initialized at the beginning and contains all possible data dictionaries, thenskuAttribute switching is nothing more than a dictionarykeyThe change of the

Of course, that’s the idea, but when you’re actually writing code, you have to think about a lot of points, and you have to think about, no matter what point is missing, the data is going to be wrong

Data preparation

It is assumed that for the category of mobile phone, its SKU attributes include finalization, color, configuration and version. The finalization is new and unpacked only, the color is deep space gray, silver and gold, the configuration is 64G and 256G, and the version is National, Hong Kong and Macao, Japan and Korea, and other versions

For example, for a color, it must have its own ID, called paramId. There is at least one small attribute under the color, such as deep Space Gray, silver, and gold. Each color also has its own ID, called valueId.

interface ISkuParamItem {
  paramId: string
  paramValue: string
  valueList: ArrayThe < {valueId: string
    valueValue: string
  }>
}
Copy the code

When requesting SKU data, the back end will return all SKU attributes corresponding to the current product ID(called spuId), which is called SKU attribute data set. The data format is as follows:

[{
    "paramId": "6977"."paramValue": "Colour"."valueList": [{
        "valueId": "1081969"."valueValue": "New"
    }, {
        "valueId": "1080699"."valueValue": "Unpack only."}]}, {"paramId": "6975"."paramValue": "Color"."valueList": [{
        "valueId": "730003"."valueValue": "Deep Space Gray"
    }, {
        "valueId": "730004"."valueValue": "Silver"
    }, {
        "valueId": "730005"."valueValue": "Golden"}]}, {"paramId": "7335"."paramValue": "Configuration"."valueList": [{
        "valueId": "710004"."valueValue": "64G"
    }, {
        "valueId": "710006"."valueValue": "256G"}]}, {"paramId": "72"."paramValue": "Version"."valueList": [{
        "valueId": "1080627"."valueValue": "Legal channels"
    }, {
        "valueId": "1080628"."valueValue": "Hong Kong and Macau Edition"
    }, {
        "valueId": "1080697"."valueValue": "Japan and South Korea"
    }, {
        "valueId": "1080629"."valueValue": "Other versions"}}]]Copy the code

All SKU data corresponding to the current product ID(called spuId) is returned, which is called the product full SKU data set. The data format is provisionally as follows:

[{count: 98.paramIdJoin: "72 _1080697__6975_730004__6977_1081969__7335_710006".priceRange: [7000.8978].spuDId: "98002993445"}]Copy the code

Among them, paramIdJoin is the combination of SKU attributes and can be divided into four units 72_1080697, 6975_730004, 6977_1081969 and 7335_710006. Each unit is connected by paramId and valueId. Therefore, 72_1080697__6975_730004__6977_1081969__7335_710006 means the SKU combination with Japanese and Korean version, silver color, new color and 256G configuration, and the corresponding total inventory count is 98. The price range is 7000 to 8978. The lowest price is 7000, and the highest price is 8978. (If there is only one price, the item in the array is the price spuDId.

Note that the value of paramIdJoin, such as 72_1080697__6975_730004__6977_1081969__7335_710006, must be paramId in ascending (or descending) order. 72 < 6975 < 6977 < 7335, so there is 72_1080697__6975_730004__6977_1081969__7335_710006

This has a significant effect on the subsequent optimization of the algorithm, not in order can also be, but in the case of a large amount of data, the calculation time will be relatively long, it is likely to appear page lag

Backend might return data structures and is not the same as above, but has little to do, regardless of the back-end data structure is what kind of return, return certainly need to include the above information, because these are the necessary data, if not the same, you only need to advance processing, processing into and the same data structure for the above, this is certainly can do it With the above data, You can start writing the core processing code

Analysis methods

In fact, there are only two functions here, that is, when any SKU attribute is selected or cancelled:

  • Calculate the price and inventory corresponding to the skU attribute combination. For example, if the color: silver, memory: 64G, and carrier: mobile are selected, the price and inventory of the goods corresponding to these SKU attributes are calculated

  • Under the skU attribute combination at this time, calculate which SKU combination should be gray. For example, the current selected color: silver, memory: 64G, the combination inventory of the remaining SKU attributes combined with the two selected SKU is 0, indicating that these SKU attributes should be dimpered, that is, the user is not allowed to select. For example, if the inventory of silver + 64G is 0, then silver is selected. You need to gray out the 64G SKU attribute

As for the first point, it is relatively simple. It only needs to get the currently selected SKU attribute combination and then search for the data containing the selected SKU attribute in all SKU data, which is a traversal filtering operation. The second point is difficult

Regardless of which SKU attributes are currently selected, the data containing any of the selected SKU attributes must be found from the entire SKU data, and then the data whose inventory is 0 must be found from this data, and the SKU attributes that should be grashed

For example, if silver -64G- bank of China this SKU inventory is 0, then when you select silver -64G, should put the bank of China in gray, silver – bank of China, should put 64G in gray, elected bank of China -64G, should put silver in gray

This is just the simplest case

To make it more complicated, if the stock of the silvery -64G SKU is 0, then when you choose silver, you should ash 64G, when you choose 64G, you should ash silver, when you choose Deep Space Grey-64G, you should ash silver… , etc.

If there are multiple SKU property items, such as color, memory, carrier, standard, color, package type, and insurance, then there are even more items that can be combined

Just think about it, I feel my head is so big, it seems to be a lot of things to calculate

But there is evidence to be found

When n SKU attributes are selected, the SKU attribute that should be dimmed is actually the skU attribute that should be dimmed when any of the n skU attributes are selected, plus the SKU attribute that should be dimmed when any of the n SKU attributes are selected, plus the SKU attribute that should be dimmed when any of the n SKU attributes are selected, plus… The skU attribute header, which should be gray if any of the n SKU attributes are selected, seems to get bigger

For example above,

When the four SKU attributes of new, gold, 64G and National are selected, calculate the SKU attributes that need to be gray in this state:

First of all, look at the four SKU attributes. When no SKU attribute is selected, which SKU inventory is 0. If it is found that there is no brand new attribute in all the goods, it means that the brand new inventory is 0, and record it.

Then, look at the four SKU attributes, and the SKU attribute that should be gray when selecting each single SKU attribute. For example, when selecting the new SKU attribute alone, it is found that the inventory of the new – silver gray combination is 0, so the silver gray is gray and this attribute is recorded. When the SKU attribute of Bank of China is selected separately, it is found that the inventory of the combination of Bank of China – only unsealing is 0, then it will only unsealing and ash, and record this attribute. When gold or 64G is selected separately, no skU properties will be recorded if any other SKU properties combined with it are in stock.

Then, among the four SKU attributes, the two SKU attributes that should be grayed are selected. For example, when the gold and 64G SKU attributes are selected at the same time, it is found that the inventory of the combination of gold -64G- Port bank is 0, then the port bank is grayed and this attribute is recorded. When new – gold or new -64G or new – National bank or gold – National bank or 64G- National Bank is selected at the same time, and any other SKU combined with these is found to be in stock, no SKU attributes are recorded;

Then, among the four SKU attributes, the three SKU attributes that should be grayed should be selected. For example, when the gold and 64G SKU attributes are selected at the same time, it is found that the inventory of the combination of gold -64G- Port bank is 0, then the port bank is grayed and this attribute is recorded. When new – gold or new -64G or new – National bank or gold – National bank or 64G- National Bank is selected at the same time, and any other SKU combined with these is found to be in stock, no SKU attributes are recorded;

Should be dimmed means that for the current SKU combination, if an additional SKU attribute is added and the inventory for this new SKU combination is 0, the last skU attribute added should be dimmed

So here we need a set of skU properties that should be gray when any number of SKU properties are selected

Want to get this collection, the computation will be very big, and the vast majority are useless calculations (calculate a lot of results, in fact, the user need only a few), so simplify, you just need to get a collection, the collection contains all may choose sku combination, also can be a bit more orderly, will be set into the Map, In js, this is an object. This object has properties whose key values are the numbers 1, 2, 3… N-1, n, represents the selection of 1 to N arbitrary SKU attributes, and its value is an object. The key of this small object is the possible combination of 1 to N arbitrary SKU attributes, and its value contains the price range and inventory information of these combinations

The code level data structure is as follows (in part) :

The above indicates that there are 11 SKU selection methods in the case that 1(subscripts 0) SKU attributes are selected, and each method has corresponding price range and total inventory information. For example, 72_1080627 indicates that when the SKU attribute whose version is National Bank is selected, Its price range array priceArr and total inventory totalCount; For the case that 2(submarked as 1) SKU attributes are selected, there are 44 SKU selection methods, and each method has corresponding price range and total inventory information. For example, 72_1080627__6975_730003 indicates that when the SKU attribute 72_1080627__6975_730003 is selected, the version is National Bank and the color is deep space gray, Its price range array priceArr and total inventory totalCount… , etc.

And with that information, it’s easy to do the rest

First of all, if you select any SKU attribute, I can find the corresponding total inventory and price range from this set without filtering the original data many times, which realizes the first function point. For the second function, when any SKU attribute is selected (set to n), I only need to select the data whose key is from 0 to N in this object and find the data whose skU total inventory is 0 corresponding to these data. If skU attribute is included in these data, it needs to be gray, which achieves the second function point

So, the most important is the Map object, as long as the calculation of the Map object, the rest of the easy to do, of course, it is simple, real code implementation or a lot of attention to the place

Data calculation

Calculation sheetskuThe collection of subscripts to which the attribute belongs

That is, from the data source returned by the interface containing all SKU attribute combinations and their corresponding data (i.e., the whole SKU data set of goods mentioned above), the subscript set of the data item containing each SKU attribute is calculated

For example, for the SKU property color: black, all the colors in the product skU data set are: The set of subscripts of skU attribute data in black is the set of subscripts to which it belongs. Taking paramId and valueId of SKU attribute as key and subscript set as value, a set can be obtained. The data structure is as follows:

{
    "6977 _1081969": [0.4.5.6.7.11.14.15.17.19.20.23.25.31.32.34.35.36.38.39.40.42.44.47]."6977 _1080699": [1.2.3.8.9.10.12.13.16.18.21.22.24.26.27.28.29.30.33.37.41.43.45.46]."6975 _730003": [4.14.17.18.22.23.28.29.32.33.37.39.43.44.45.47]."6975 _730004": [0.2.5.7.8.10.12.16.19.20.24.31.34.40.41.46]."6975 _730005": [1.3.6.9.11.13.15.21.25.26.27.30.35.36.38.42]."7335 _710004": [1.3.4.5.8.9.10.11.19.24.28.30.31.32.33.34.35.36.37.39.42.43.44.46]."7335 _710006": [0.2.6.7.12.13.14.15.16.17.18.20.21.22.23.25.26.27.29.38.40.41.45.47]."72 _1080627": [7.12.13.18.19.23.30.33.38.42.44.46]."72 _1080628": [3.5.6.10.16.21.36.39.40.43.45.47]."72 _1080697": [0.8.9.11.14.22.25.26.31.32.37.41]."72 _1080629": [1.2.4.15.17.20.24.27.28.29.34.35]}Copy the code

For example, for the first piece of data “6977_1081969”: [0, 4, 5, 6, 7, 11, 14, 15, 17, 19, 20, 23, 25, 31, 32, 34, 35, 36, 38, 39, 40, 42, 44, 47] It indicates that all the skU attributes in the commodity full SKU data set contain paramId 6977 and valueId 1081969, namely, finalization: The new set of data subscripts is [0, 4, 5, 6, 7, 11, 14, 15, 17, 19, 20, 23, 25, 31, 32, 34, 35, 36, 38, 39, 40, 42, 44, 47]

There is nothing to say about the computation of this collection, other than to iterate through the whole skU data set of the goods and create an array of data. For the sake of the description, this collection is called keyRankMap. Right

To calculateMapobject

With the keyRankMap above, we have the prerequisite to calculate the desired Map object (called indexKeyInfoMap),

The composition of the indexKeyInfoMap set, as described above, is similar to a cache of data, listing all the information for any combination of SKUs, so there is an algorithm involved:

I have m arrays, all of which are not empty, so how many ways can I take n(n <= m) from these arrays? Specifies that each array can be fetched at most once, at most one item at a time

This algorithm is actually a more enhanced version of the common algorithm, that is, from m number of n number, how many kinds of method, the m number here may be regarded as an array, which is from the data of a length of m n number, but now is not from an array, but from the m in the array

There are, of course, many ways to write this algorithm, as long as it works and is not too efficient:

/** * Give an array of mArr lengths, select n items from the array, take at most one item from each array, find all possible sets, where each item of mArr represents the length of the array * for example, composeMArrN(([1, 2, 3], 2)), indicate that 3 arrays are given, Example: composeMArrN(([1, 2, 3], 2)); return: composeMArrN(([1, 2, 3], 2)) * [[0, 0, 1], [0, 1, 1], [0, 1, 0], [0, 1, 1], [0, 1, 2], [0, 1], [1, 1], [1,0,2], [1, 0], [1,1,1], [1,1,2]] * the returned array length is 11, For example, for the first subarray [0, 0, -1] of the result above, the first way to fetch is to take the number with index 0 in the first array and index 0 in the second array. @param arr = @param arr = @param arr = @param arr = @param arr = @param arr * @param hasSeletedArr recursion */ @param rootArr recursion */
function composeMArrN (mArr: Array<number>, n: number, arr = [], hasSeletedArr = [], rootArr = []) :Array<Array<number>> {
  if(! n || n <1 || mArr.length < n) {
    return arr
  }
  for (let i = 0; i < mArr.length; i++) {
    // The current level already has a selection
    if (hasSeletedArr.includes(i)) continue
    hasSeletedArr = hasSeletedArr.slice()
    hasSeletedArr.push(i)
    for (let j = 0; j < mArr[i]; j++) {
      let arr1 = completeArr(arr, i - arr.length, - 1)
      arr1.push(j)
      if (n === 1) {
        arr1 = completeArr(arr1, mArr.length - arr1.length, - 1)
        rootArr.push(arr1)
      } else {
        composeMArrN(mArr, n - 1, arr1, hasSeletedArr, rootArr)
      }
    }
  }
  return rootArr
}
Copy the code

CompleteArr ([1, 2], 3, -1); completeArr([1, 2], 3, -1); completeArr([1, 2], 3, -1); Return [1, 2, -1, -1, -1]

By analogy, when arbitrary N SKU attributes are taken, the data of price, inventory and other information corresponding to the skU combination can be obtained, namely indexKeyInfoMap

According to indexKeyInfoMap, the information corresponding to skU combination and gray information in any state are calculated

IndexKeyInfoMap is just a cache of data. The function of indexKeyInfoMap is to select any SKU data, the corresponding information such as price and inventory, and the SKU information should be dimmed

For example, when you win the all-new – Silver combination

  • Calculate the corresponding price and inventory information

New – silver is a combination of two SKU attributes, then directly look for the attribute in indexKeyInfoMap with key 1, and look for the array value that matches the new – silver, that is, the data item with sub-key 6975_730004__6977_1081969:

Where priceArr is the set of price ranges for all SKU data that contain the new – silver SKU combination, spuDIdArr is the set of spuDId, and totalCount is the total inventory

  • Calculate the need to ashskuattribute

That’s the key

First, calculate the attribute whose inventory is 0 when no attribute is selected. Second, calculate the inventory of 0 when the new and Silver properties are selected separately and combined with these two properties respectively. Third, calculate the inventory of 0 when new – silver is selected at the same time and combined with new – silver;

The union of the three properties that should be grayed in all cases is the one that should be grayed when selected as new – silver

The basis of the calculation is indexKeyInfoMap. For example, for the second, calculate the property that the inventory is 0 when new is selected separately and when silver is selected separately; , its calculation process:

First, any combination of a SKU attribute and new or silver is a pair of SKU attribute links of length 2, so select the data with key 1 from indexKeyInfoMap[1], From this data, find the data items containing new and silver, that is, the key contains 6977_1081969 or 6975_730004, and the inventory is 0:

Then, the 7 pieces of filtered data are sorted out to get the set of SKU attributes that need to be gray, that is, the key string of these data. Remove the currently selected SKU attributes, that is, the set of the remaining values after 6977_1081969 and 6975_730004

For example, for 72_1080628__6975_730004, 72_1080628 is left after the processing, that is, the button corresponding to skU attribute whose paramId is 72 and valueId is 1080628 should be disabled, and the rest is similar

This results in an array (which needs to be deduplexed) in which each item is the SKU property button that needs to be dimmable when the all-silver is selected at the same time

In fact, it is also an algorithm. As mentioned above, n(n <= m) numbers are taken from m data, all possible fetching methods, and then each fetching method is processed to calculate the skU attributes whose inventory is 0 when combined with the SKU combination of each fetching method

@param arr @param arr @param arr @param arr @param arr @param arr @param arr @param arr @param arr */ Function composeMN (m: number, n: number) composeMN (m: number, n: number) number, arr: number[] = [], hasSeletedArr: number[] = [], rootArr: number[][] = []): number[][] { for (let i = 0; i < m; i++) { if (hasSeletedArr.includes(i)) continue hasSeletedArr = hasSeletedArr.slice() hasSeletedArr.push(i) let arr1 = arr.slice() arr1.push(i) if (n ! == 1) { composeMN(m, n - 1, arr1, hasSeletedArr, rootArr) } else { rootArr.push(arr1) } } return rootArr }Copy the code

Of course, you can use the algorithm that you think is better, but it solves the problem and it’s efficient

At this point, the process is finished and the function is complete

Algorithm to optimize

According to the above process, the functions can be realized and the efficiency is not low. It is perfectly fine for normal business scenarios, but there is still some room for optimization

Single SKU data cache with inventory of 0

For a normal product, especially a platform directly operated product, in most cases, every SKU should be in stock. In this case, no matter which SKU properties you select under any circumstances, there should be no gray SKU properties, because all SKUs are in stock. If I can confirm that all SKUs have inventory of a certain item, then I don’t need to worry about button ash, and the part with the largest calculation can be completely saved, which reduces the calculation amount by more than half at a time

If not all SKU inventories are zero, there is room for optimization to be accurate to a single SKU attribute, as follows: Iterate through all skU data sets of all goods, find out all SKU combinations with inventory of 0, separate single SKU attributes from each combination, put all these single SKU attributes into a set (called emptySkuIncludeList), then when the user selects any SKU combination, It is found that none of the SKU properties selected by the user are in the emptySkuIncludeList set, and it is determined that no skU property will need to be deactivated no matter which SKU property is selected or cancelled by the next user

This is very understandable, for example, the skU combination with inventory of 0 now only has this item 72_1080697__6975_730004__6977_1081969__7335_710006, namely version: Japan and Korea, color: silver, color: New, configuration: EmptySkuIncludeList = [’72_1080697′, ‘6975_730004’, ‘6977_1081969’, ‘7335_710006’], When the user selects the SKU property, version: Guoxing and color: are selected. Gold, corresponding to the ID combination 72_1080627 and 6975_730005, both properties are found not in emptySkuIncludeList, then there is no need to predict the user’s next step, because no matter which SKU attribute the user selects or cancelates next, There are certainly no SKU attributes that need to be dimmed

In other words, in this case, there is no need to calculate the graying SKU attribute, which also reduces the calculation amount by more than half

Find array intersection

When calculating indexKeyInfoMap, for example, the set of subindices of all skU data set corresponding to the SKU combination 72_1080627__6975_730003__6977_1080699, It is to find the subscripts containing 72_1080627, 6975_730003 and 6977_1080699 from the whole SKU data set of commodities, and then find the intersection of the three sets. Is the set of subscripts containing the SKU combination 72_1080627__6975_730003__6977_1080699

At first I asked array intersection, is, in turn, two more directly, through which an array, and then find another did an array containing the current traversal of the array, if you have, that is that intersection

const resultArr = []
arr1.forEach(item= > {
    if (arr2.includes(item)) {
        // indicates the intersection term
        resultArr.push(item)
    }
})
Copy the code

The complexity of this algorithm is about O(m * n). If the amount of data is large, it still affects the efficiency. Therefore, I thought that since the data in ARR1 and ARR2 are all arranged in ascending order, the complexity of the algorithm can be reduced to O(m), so I have the following algorithm

function intersectionSortArr (. params: Array
       
        >
       ) :Array<number> {
  if(! params || params.length ===0) return []
  if (params.length === 1) {
    return params[0]}let arr1 = params[0]
  let arr2 = params[1]
  if (params.length > 2) {
    returnintersectionSortArr(arr1, intersectionSortArr(arr2, ... params.slice(2)))}let arr = []
  if(! arr1.length || ! arr2.length || arr1[0] > arr2.slice(- 1) [0] || arr2[0] > arr1.slice(- 1) [0]) {
    return arr
  }
  let j = 0
  let k = 0
  let arr1Len = arr1.length
  let arr2Len = arr2.length
  while (j < arr1Len && k < arr2Len) {
    if (arr1[j] < arr2[k]) {
      j++
    } else if (arr1[j] > arr2[k]) {
      k++
    } else {
      arr.push(arr1[j])
      j++
      k++
    }
  }
  return arr
}
Copy the code

Avoid regular expressions with high ambiguity

When the user selects some SKU attributes, the SKU attributes that need to be gray in the current state need to be calculated. For example, when the user selects 72_1080627 and 6975_730005 skU attributes, according to the above, You need to go to indexKeyInfoMap[2] to find the SKU combination data that contains both skU attributes

That is to look in these data:

How do you find the string 72_1080627 and 6975_73000699 in the format of 72_1080627__6975_730003__6977_1080699? In general, you might think of matching with a regular expression, like I started with this regular expression to match

reg = / [0-9 _] * 72 _1080627 _ - [0-9] * 6975 _730005 _ - [0-9] * /
Copy the code

Why did you write it that way? Because I only know that 72_1080627 is ranked in front of 6975_730005 according to paramId, but I don’t know which place 72_1080627 and 6975_730005 should be in, and whether there are other attributes connected before and after them, so I write a very broad regular. A regular fix, simple and easy

After writing it, I thought it was ok and there was no problem. Later, when I tested the extreme cases on the back end, I sent thousands of SKUs for each product, and found that the front end would be stuck for more than ten seconds before moving. I quickly checked and found that this regex took too long, because the regex was too vague

There are also many optimization methods. For example, when the user chooses paramId for location determination, you can clearly know that 72_1080627 is definitely in the first place, 6975_730005 is definitely in the second place, and there must be a third. In this way, the regularization can be precisely as

reg = / 72 _1080627__6975_730005 ^ 0-9 _ + /
Copy the code

This is obviously a lot more accurate than the first fuzzy match, and there are fewer regular branches, but there are still positions to be determined, and there will still be fuzzy matches, so it’s better not to use regular matches

Since the selected skU properties are not repeated, and the data is in order, it is a string lookup, such as indexOf or includes, but there are still some invalid searches. It’s on the order of order m by n

Since the skU attributes selected by the user are sorted by paramId in ascending order, an array is formed in order, such as [“72_1080627”, “6975_730005”], and then each string attribute of indexKeyInfoMap[2] is taken. Also separate the skU properties into arrays, such as [“72_1080627”, “6975_730003”, “6977_1080699”], and then iterate over them:

const skuJoinArr = ["72 _1080627"."6975 _730003"."6977 _1080699"]
const currentSkuArr = ["72 _1080627"."6975 _730005"]
let i = 0
skuJoinArr.forEach(item= > {
    if (item === currentSkuArr[i]) i++
})
if (i === skuJoinArr.length) {
    // Specify a match
}
Copy the code

No matter which SKU attributes are selected by the user, the length of the attribute string of indexKeyInfoMap[index] THAT I need to look up is only 1 more than that selected by the user, and both of them are sorted in ascending order according to paramId, so as long as two arrays step at the same time according to the conditions, The last shorter currentSkuArr can be stepped to the end, indicating that skuJoinArr contains currentSkuArr

So the complexity of the algorithm is down to order m

, of course, there must be other places can be optimized, I now are clearly made the above a few, and optimization of this kind of thing, is not accurate to every line of every period of the whole project complete optimization is the best, no dead Angle for optimized code, often is not the same as written according to the normal thinking, business code a cost-effective, balanced development is the best

After the above optimization is added, the back-end limit test is conducted on Huawei P30. The initialization of more than 1000 SKUs takes only 200~300 ms, and the initialization of more than 600 SKUS takes only about 70-80ms, which is tens of times more than ten seconds at the beginning

In the actual application scenario, for a normal commodity, the number of SKUS is generally not more than 100. For example, the iPhone XR on JD.com now has less than 60 SKUs. The initial use time is about 20 ~ 30ms, so it is completely sufficient

Npm package

At the beginning, I did not want to make this into a third-party package, because it is not a generic tool or component, but a business-oriented scenario component, which is highly coupled with the actual business scenario, and it is not good to make customized modifications according to the actual business scenario

But everyone seems to like the flattening of the complex code third-party libraries, only need to import can be out of the box, do not need to care about what internal logic, has more than one friend suggested that I will be packaged into NPM package, convenient promotion, so I want to the next, with part of the business interaction must be impossible as a separate package, but the core computing part can ah, Receive external input data, after completing the internal calculation, will return the calculation results, as to how to use the calculation results that is the business side of the matter, is also a kind of withdrawal

So I made an NPM package according to this idea, and those who are interested can try it

Matters needing attention

As mentioned above, data sources need to be sorted by paramId. Generally, this field will be of numeric type (or numeric string). This is sorted by paramId size, but there may be a problem. The following reference is from mdN-number. MAX_SAFE_INTEGER

MAX_SAFE_INTEGER is a constant value of 9007199254740991, which is 2 to the power of 53. The reason for this Number is, Javascript uses the double-precision floating-point format numbers specified in IEEE 754, where the range of numbers that can be safely represented is [-(253-1), 253-1].

Safe here means being able to represent integers accurately and compare them correctly. For example number.max_safe_INTEGER + 1 === number. MAX_SAFE_INTEGER + 2 will return true, which is not mathematically correct. See number.issafeInteger () for more information.

In plain English, that is, if the js operation Numbers greater than 9007199254740991, the results may be inaccurate, we here back end interface paramsId mutual size to ordering data, if paramsId value is the size of more than 9007199254740991, Then the result of comparison between the two paramId may be wrong. If you have confirmed with the back end, the value will definitely not exceed 9007199254740991. It is better to do so without any treatment

conclusion

A began to think of ideas, for I will don’t know where laid a hand on him, because seems to be a lot of things to consider, consider to this have forgotten that, but really settled down to clear up the thoughts carefully, actually was more clear, thinking, thinking with the code can be implemented, this is relatively simple, as long as you don’t put yourself around the halo

As the saying goes “Talk is cheap, show me the code”, some expressions in the article may not be clear, or the code is the most direct, so I also made an online Demo (it is best to view on mobile terminal), the source code can also be put on Github, interested can try it yourself

Of course, if you really don’t understand, you can also leave it to the back end to do, you can call the interface pass parameters and wait for the data (manual dog-head)