这是一个在女装项目中碰到的实际问题,网站的权限管理与省份相关,权限管理涉及两种角色:网站运维人员,商家。网站的运维人员可以管理不同省份的商家,商家具有在不同省份进行销售的权限,即两种角色与省份均是1对多的关系。
举个例子,某运维账号A具有浙江,上海两处站点管理权限,商家账号B具有浙江销售权限,商家账号C具有上海销售权限,商家D具有江苏和浙江的权限。那么运维账号A只能管理BC,不能管理账号D,因为D具有A所不具有的江苏权限。
图1 权限对应关系图,A管理BC,无法管理D
那么问题来了,对于某个登录的运维账号,如何在大量商家账号中快速找出隶属于该运维账号的呢?
设运维账号具有的权限的省份集合是O,例如O={浙江,上海},可以管理的商家账号集合为M。设商家账号集合为B,其中每个元素是商家销售站点的集合。例如B={B1,B2,B3,B4},B1={浙江},B2={上海},B3={浙江,上海},B4={浙江,江苏},那么计算该运维账号能够管理的商家账号的集合,即Bi∈B,如果Bi ⊆O,则Bi∈M。
图2 判断一个集合是否为另一个集合的子集
从抽象模型来看,如果我们设计一张表存储商家和销售省份的对应关系,直观的想法是,对于给定的运维账号,遍历所有的商家账号(O(n)),然后对于每个商家账号计算其对应省份集合是否为运维账号省份集合的子集,判断集合A是否为集合B的子集的时间复杂度根据算法不同分别为:
因此整体的时间复杂度是O(n^2lgn)
普通的解决方案,时间复杂度很大,且设计一张关系表存储商家和省份的对应关系占用较多空间,因此在时间和空间上都可以进一步提升。 在减少存储空间上,我们容易联想上使用BitMap存储账号对应的省份关系,例如,假设一共有浙江,江苏,上海三个省份,则可以使用三位bit表示账号与省份对应权限,三位bit从高到低依次表示浙江,江苏,上海,那么:
001表示具有上海权限
011表示具有江苏和上海权限 110表示具有浙江和上海的权限
上面的例子中,O={浙江,上海},则bitVal(O)=110,B={B1,B2,B3,B4},则bitVal(B)={100,001,101,011}。依次类推可以采用34位bit存储账号具有的省份权限。
在提升时间复杂度方面,可以采用位的与操作提高算法效率,因为如果集合A是集合B的子集,则满足bitVal(A)&bitVal(B)=bitVal(B),bitVal表示对应的bitMap值。例如:
bitVal(O)&bitVal(B1)=110&100=100=bitVal(B1),则B1∈M bitVal(O)&bitVal(B4)=110&011=010!=BitVal(B4),则B4∉M
通过位与操作,可以通过一次操作判断出二者是否具有包含关系,时间复杂度为O(n),我们可以将权限的bitmap的值设为数据库的一个字段,则判断是否为子集的操作都可以在数据库端完成。杭研所使用的分布式DDB最新版本已经支持了位操作,因此这个针对某个运维账号选择它可以管理的商家账号完全可以通过一个sql语句完成。
在实践中另一个提交效率的方法是在二进制与省份转换的中,直观的想法是遍历二进制的每一位,取出其为1的所有位得到其所表达的省份的集合,这个算法与一个面试题类似:计算一个二进制数的1的个数,代码如下:
int count=0;
while (fmt != 0) {
long fmtleft = fmt & (fmt - 1);
count++;
fmt = fmtleft;
}
这个算法的一个改进之处是“略过”为所有为0的二进制数字。代码如下:
public static List<Long> getCodeListByProvinceFmt(long fmt) {
List<Long> retList = new ArrayList<>();
while (fmt != 0) {
//通过减法略去所有为0的位
long fmtleft = fmt & (fmt - 1);
//计算此时最高位为1的数值,并转换成对应省份code
long singleFmt = fmt - fmtleft;
Long code = provinceCodeReverseMap.get(singleFmt);
retList.add(code);
fmt = fmtleft;
}
return retList;
}
该算法的时间复杂度为bitMap中1的位数,最坏情况下为O(n),最好情况下为O(1),在一个账号对应较少省份情况下,效率可以很好。
使用BitMap结构存储账号对应省份数据字段,既可以减少存储空间,也提交了判断是否为子集的效率。
网易云大礼包:https://www.163yun.com/gift
本文来自网易实践者社区,经作者刘杰授权发布