剁手党必看——转转红包使用规则与最优组合计算全解析

2024-05-08 20:44

本文主要是介绍剁手党必看——转转红包使用规则与最优组合计算全解析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  • 1、省钱攻略基础之“了解平台红包使用规则”

  • 2、举个栗子

  • 3、最优红包组合计算方法进化过程

    • 3.1、初代“笛卡尔乘积”版

    • 3.2、二代“边算边比较Map聚合”版

    • 3.3、三代“边算边比较数组索引定位”版

  • 4、总结

1、省钱攻略基础之“了解平台红包使用规则”

规则一:红包大类别分为“商品红包”、“叠加券”、“邮费红包”三种。

规则二:每个SKU(同一个商品ID),商品红包、叠加券、邮费红包最多每种使用一张。

规则三:商品红包和叠加券都有可能设定使用门槛金额,门槛金额是商品促销优惠后金额(如果有促销),邮费红包使用门槛基于商品红包和叠加券优惠后金额计算。

规则四:门槛金额高的红包优惠不一定高于门槛低的(虽然大概率如此)。

规则五:绝大多数红包都有使用限制条件,与商品相关的:分类、归属的业务、卖家、包含的服务、特定的商品范围、商品发布时间;与场景相关:终端类型、卖场;与买卖家相关:是否是“新客户”、买卖家是否被风控等等。

规则六:商品红包和叠加券小类分为:满额减和满额折,其中满额折红包又有最大优惠金额如满10元8.8折最多优惠1000元,此时如果商品10000元最多也只能减1000元;邮费红包分为定额红包和免邮红包。

2、举个栗子

在开始计算最大优惠前,我们先举个例子具象化实际场景,此处忽略“规则五”计算过程,直接给出符合红包使用限制的商品与红包关系;由于邮费红包门槛金额基于商品红包和叠加券后金额较为复杂,且不影响最优红包解题思路,此处忽略邮费红包,仅以商品红包为例。

场景如下:

5个商品分别为:P1=10元、P2=20元、P3=30元、P4=40元、P5=50元。

5个商品红包:R1=满10元减5元、R2=满20元减12元、R3=满30元减10元、R4=满90元减60元、R5=满100元减80元。商品与红包的关系如下表格:

3、最优红包组合计算方法进化过程

3.1、初代“笛卡尔乘积”版

首先,将每个红包的可用商品聚合:

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

将每个红包的可用商品进行排列组合得到下表(黄色为该组合不符合红包门槛):

将上表改写成矩阵:

计算纵列笛卡尔积:

计算各组合红包的优惠情况,按红包优惠金额倒序,取红包最大优惠组合情况, 得到:P5商品使用R2;P1P2P3P4使用R5,得到最大优惠金额80+12=92元。

该版本核心思想:计算出所有商品使用红包的组合情况,并行计算各组合的优惠金额,按优惠金额倒序取最大优惠。存在的问题:商品和红包数量增加时组合数呈指数级增长,计算笛卡尔积时很容易OOM。

3.2、二代“边算边比较Map聚合”版

一代算法最大的问题是将所有组合全部排列好后再进行价格计算和比较,导致内存占用过大;二代算法核心思想是“边排列组合边计算边比较”保留最优解,计算耗时到达规定阈值时停止,取已算组合中的最优。这一代算法中,用到了HashMap作为记录商品使用红包的标记指针,数据结构如下:

//用于记录每个商品上,各大类可用红包的列表
private Map<ERedMetaBigType, List<RedBaseInfoInput>> prodRed = Maps.newHashMap();//用于记录该商品在各大类红包列表List<RedBaseInfoInput>上使用红包的列表index位置private Map<ERedMetaBigType, Integer> pointer = Maps.newHashMap();

指针移动抽象示例(黄色为此轮组合指针位置):

移动一次指针就形成一个新的组合,根据根据标记将使用相同红包的商品“聚合” 如组合2:R5<P1,P2,P3,P4> R3

//使用Map结构记录
Map<ERedMetaBigType, Map<Long, List<EngineInput>>> oneType2RedId2Prods = Maps.newEnumMap(ERedMetaBigType.class);

优点:不需要将所有组合都排列出后再计算比较,超过规定时间可以中断降级处理。缺点:每次移动指针后,都需要使用Map结构将红包商品重新“聚合”后才能计算红包门槛和优惠,频繁生产销毁Map和List对象,GC压力大。

3.3、三代“边算边比较数组索引定位”版

三代主要通过数据结构与虚拟逻辑关系,减少上一代算法大量生成中间临时Map导致GC压力大问题。使用数组Long[] infoArray存储商品列表,此时infoArray数组下标就含有了商品ID的含义,同理,Long[] redArray存储红包列表,redArray数组下标就含有了红包ID的含义。使用byte[][] infoRedRel二维数组用于存储商品红包关系,数组值0表示此轮计算未使用,1表示此轮计算使用,-1表示该商品不可使用此红包。关系数组如下:

拥有这个二维数组后,就可以通过修改这个位数数组的值(不包含-1不可用的),实现红包使用组合的变更。

此时聚合商品不再需要使用Map生成新的结构存储,只需要遍历红包列表数组,根据数组下标去infoRedRel维数组中获取数组值,然后去infoArray取商品即可。

4、总结

本文简述了最优红包组合的整体演进,下表是二代和三代在不同红包总量、商品数量、商品可用红包数量时,200ms完成计算组合数的情况对比(30次均值)如下图:

通过二代三代的对比,我们不难发现,在面对大量计算时除了要注意JVM内存使用情况外(一代FullGC或溢出),还需要关注对象生成销毁的数量与频率,因为在面临大量计算时对象生成和GC也将成为性能瓶颈,三代相较二代,完成计算的组合数在5倍以上,这其间的差距都是因为二代Map对象的生成和销毁。


关于作者

马宝山,  转转交易中台Java开发工程师

这篇关于剁手党必看——转转红包使用规则与最优组合计算全解析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/971393

相关文章

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库,完全使用 Python 语言编写,它对 XPath表达式提供了良好的支 持,因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块,该模块专门用来解析 HTML/XML 文档,下面来介绍一下 lxml 库

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

使用SecondaryNameNode恢复NameNode的数据

1)需求: NameNode进程挂了并且存储的数据也丢失了,如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2)故障模拟 (1)kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 (2)删除NameNode存储的数据(/opt/module/hadoop-3.1.4/data/tmp/dfs/na

Hadoop数据压缩使用介绍

一、压缩原则 (1)运算密集型的Job,少用压缩 (2)IO密集型的Job,多用压缩 二、压缩算法比较 三、压缩位置选择 四、压缩参数配置 1)为了支持多种压缩/解压缩算法,Hadoop引入了编码/解码器 2)要在Hadoop中启用压缩,可以配置如下参数

Makefile简明使用教程

文章目录 规则makefile文件的基本语法:加在命令前的特殊符号:.PHONY伪目标: Makefilev1 直观写法v2 加上中间过程v3 伪目标v4 变量 make 选项-f-n-C Make 是一种流行的构建工具,常用于将源代码转换成可执行文件或者其他形式的输出文件(如库文件、文档等)。Make 可以自动化地执行编译、链接等一系列操作。 规则 makefile文件

使用opencv优化图片(画面变清晰)

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化,使其看起来更清晰,同时保持尺寸不变,通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多,主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器:相机传

hdu4869(逆元+求组合数)

//输入n,m,n表示翻牌的次数,m表示牌的数目,求经过n次操作后共有几种状态#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#includ

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据,将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]