1. The basic basis of the money-saving strategy is "understanding the rules for using red envelopes on the platform"
Rule 1: There are three types of red envelopes: "commodity red envelopes", "superimposed coupons", and "postage red envelopes".
Rule 2: Each SKU (the same product ID), product red envelopes, stacked coupons, and postage red envelopes can be used at most one each.
Rule 3: The threshold amount is the amount after the product promotion (if there is a promotion), and the postage red envelope is calculated based on the amount after the product red envelope and the superimposed coupon discount.
Rule 4: The red envelope offer with a high threshold amount is not necessarily higher than the one with a low threshold (although it is likely to be so).
Rule 5: The vast majority of red envelopes have restrictions on the use of goods: classification, business to which they belong, sellers, services included, specific product ranges, and product release time; Scenario-related: terminal type, store; Related to the buyer and seller: whether it is a "new customer", whether the buyer and seller are subject to risk control, etc.
Rule 6: Commodity red envelopes and superimposed coupons are divided into: full reduction and full discount, of which the full discount red envelope has the maximum discount amount, such as 10 yuan or 8.8 discount, the maximum discount is 1000 yuan, at this time, if the product is 10000 yuan, it can only be reduced by 1000 yuan at most;
2. Take a chestnut
Before starting to calculate the maximum discount, let's take an example to visualize the actual scenario, ignoring the "Rule 5" calculation process, and directly giving the relationship between the goods that meet the restrictions on the use of red envelopes and red envelopes; Since the threshold amount of postage red envelopes is more complex based on the amount after the commodity red envelope and the superimposed coupon, and does not affect the optimal red envelope solution idea, the postage red envelope is ignored here, and only the commodity red envelope is taken as an example.
The scenario is as follows:
The five commodities are: P1 = 10 yuan, P2 = 20 yuan, P3 = 30 yuan, P4 = 40 yuan, P5 = 50 yuan.
5 commodity red envelopes: R1 = 5 yuan for a full 10 yuan, R2 = 12 yuan for a full 20 yuan, R3 = 10 yuan for a full 30 yuan, R4 = 60 yuan for a full 90 yuan, and R5 = 80 yuan for a full 100 yuan. The relationship between the product and the red envelope is as follows:
3. The evolution process of the optimal red envelope combination calculation method
3.1. The original "Cartesian product" version
First, aggregate the available items for each red packet:
R1->P2、P3、P4、P5 R2->P1、P3、P4、P5 R3->P1、P2、P4、P5 R4->P1、P2、P3、P5 R5->P1、P2、P3、P4
The following table is obtained by permutating and combining the available products of each red envelope (yellow indicates that the combination does not meet the red envelope threshold):
Rewrite the above table as a matrix:
Calculate the tandem Cartesian product:
Calculate the preferential situation of each combination of red envelopes, and take the maximum preferential combination of red envelopes in reverse order of the preferential amount of red envelopes, and obtain: R2 is used for P5 products; P1P2P3P4 use R5, get the maximum discount amount of 80 + 12 = 92 yuan.
The core idea of this version: calculate the combination of red envelopes used by all products, calculate the discount amount of each combination in parallel, and take the largest discount in reverse order of the discount amount. Problem: The number of combinations increases exponentially when the number of goods and red envelopes increases, and it is easy to OOM when calculating the Cartesian product.
3.2. The second-generation "Compare Map Aggregation While Calculating" version
The biggest problem of the first-generation algorithm is that all the combinations are arranged and then the price is calculated and compared, which leads to excessive memory usage. The core idea of the second-generation algorithm is to "calculate while permutating and combining", retain the optimal solution, stop when the calculation time reaches the specified threshold, and take the best of the calculated combinations. In this generation of algorithms, HashMap is used as a marker to record the use of red envelopes for goods, and the data structure is as follows:
//用于记录每个商品上，各大类可用红包的列表
private Map<ERedMetaBigType, List<RedBaseInfoInput>> prodRed = Maps.newHashMap();
//用于记录该商品在各大类红包列表List<RedBaseInfoInput>上使用红包的列表index位置
private Map<ERedMetaBigType, Integer> pointer = Maps.newHashMap();
Abstract example of pointer movement (yellow for this round combines pointer position):
Move the pointer once to form a new combination, which will be "aggregated" according to the mark of the same red packet (e.g. combination 2: R5< P1, P2, P3, P4> R3
//使用Map结构记录
Map<ERedMetaBigType, Map<Long, List<EngineInput>>> oneType2RedId2Prods = Maps.newEnumMap(ERedMetaBigType.class);
Advantages: There is no need to arrange all combinations and then calculate and compare, and the downgrade process can be interrupted after the specified time. Disadvantages: Every time the pointer is moved, it is necessary to use the Map structure to re-"aggregate" the red envelope products before the red envelope threshold and discount can be calculated, and the Map and List objects are frequently produced and destroyed, and the GC pressure is high.
3.3. Three generations of "Compare Array Index Positioning While Calculating" version
The third generation mainly uses the data structure and virtual logical relationship to reduce the problem of GC pressure caused by a large number of intermediate temporary maps generated by the previous generation algorithms. Use the array Long[] infoArray to store the list of goods, at this time, the infoArray array subscript contains the meaning of the product ID, in the same way, Long[] redArray stores the red packet list, and the redArray array subscript contains the meaning of the red packet ID. The byte[][] infoRedRel two-dimensional array is used to store the red packet relationship of the product, and the array value of 0 indicates that the round of calculation is not used, 1 means that the round of calculation is used, and -1 means that the product cannot use this red packet. The array of relationships is as follows:
After having this two-dimensional array, you can change the combination of red packets by modifying the value of this bit array (excluding -1 is not available).
At this time, the aggregated product no longer needs to use Map to generate a new structure storage, but only needs to iterate through the red packet list array, go to the infoRedRel dimensional array according to the array subscript to get the array value, and then go to infoArray to get the product.
4. Summary
This article briefly describes the overall evolution of the optimal red packet combination, and the following table shows the comparison of the number of combinations completed in 200ms (30 times average) between the second and third generations when the total number of red packets, the number of products, and the number of red packets available for different red packets are as follows:
Through the comparison of the second and third generations, it is not difficult to find that in the face of a large number of calculations, in addition to paying attention to the JVM memory usage (the first generation of FullGC or overflow), we also need to pay attention to the number and frequency of object generation and destruction, because in the face of a large number of calculations, object generation and GC will also become a performance bottleneck, and the number of combinations that complete the calculation is more than 5 times that of the third generation compared with the second generation, and the gap between them is because of the generation and destruction of the second-generation Map objects.
About the author
Ma Baoshan, Java Development Engineer in the middle office of Zhuan Trading
Source-WeChat public account: Zhuan Zhuan Technology
Source: https://mp.weixin.qq.com/s/AU7Ou97SfhQrlBj3zXLYyg