编写不易,转载请注明 (http://shihlei.iteye.com/blog/2358063)
一 概述
广告系统中,广告活动创建时,运营人员通常会根据广告的受众情况,设置广告的基本定向,如香奈儿推广 需要投放上海的女士用户。
因此,根据定象条件对广告活动进行索引和检索是投放引擎的必备功能。
通常实现可以使用ElasticSearch这样的索引引擎。本文尝试实现一个简单的基于BitMap的内存索引和检索引擎。
二 思路
索引:为每个定向条件构建一个BitSet,在该定向条件创建索引,相当于将BitSet 的 广告活动ID位 置1;
检索:提供定向集合,取出指定定向的BitSet,BitSet之间通过“与”运算,取交集获得最终的BitSet,获取最终BitSet中位为1 的下标即满足条件的bitmap。
优点:内存索引且内存空间很小。
缺点:
1)当BitSet位数很大时,进行&运算会比较慢,待进一步研究。
2)广告活动ID 必须为 整型。
3)定向条件很多的情况,感觉使用还是有些困难。
4)定向条件之间会有“或”运算的情况,这里没有考虑。
其他没有深想。
三 实现
public class AdvEngine { private static final int BITSET_SIZE = 100000000; //索引列表 private Map<TargetEnum, BitSet> indexes = new HashMap<>(); public static void main(String[] args) { AdvEngine advEngine = new AdvEngine(); //广告1000 投放:北京,女 advEngine.index(1000, Arrays.asList(TargetEnum.GENDER_FEMALE, TargetEnum.AREA_BEIJING)); //广告2000 投放:上海,女 advEngine.index(2000, Arrays.asList(TargetEnum.GENDER_FEMALE, TargetEnum.AREA_SHAGNHAI)); //广告3000 投放:女 advEngine.index(3000, Arrays.asList(TargetEnum.GENDER_FEMALE)); //广告4000 投放:上海 ,男 advEngine.index(4000, Arrays.asList(TargetEnum.GENDER_MALE, TargetEnum.AREA_SHAGNHAI)); System.out.println("上海,女 可投放广告:"); List<Integer> campaingIds = advEngine.search(Arrays.asList(TargetEnum.GENDER_FEMALE, TargetEnum.AREA_SHAGNHAI)); campaingIds.stream().forEach(System.out::println); System.out.println("女 可投放广告:"); campaingIds = advEngine.search(Arrays.asList(TargetEnum.GENDER_FEMALE)); campaingIds.stream().forEach(System.out::println); } /** * 创建索引 * * @param campaignId 广告id * @param targets 定向类型 */ public void index(int campaignId, List<TargetEnum> targets) { for (TargetEnum target : targets) { BitSet bitSet = indexes.get(target); if (bitSet == null) { bitSet = new BitSet(BITSET_SIZE); indexes.put(target, bitSet); } bitSet.set(campaignId, true); } } /** * 查找符合类型的广告活动 * * @param targets 定向类型 */ public List<Integer> search(List<TargetEnum> targets) { List<Integer> campaignIds = new LinkedList<>(); if (targets.isEmpty()) { return campaignIds; } BitSet finalSet = null; //取出满足所有定向条件的集合 long start = System.nanoTime(); for (TargetEnum target : targets) { BitSet campaingBitSet = indexes.get(target); if (campaingBitSet == null) { break; } if (finalSet == null) { finalSet = (BitSet) campaingBitSet.clone(); } else { finalSet.and(campaingBitSet); } } long end = System.nanoTime(); System.out.println("time1 : " + (end - start)); if (finalSet == null) { return campaignIds; } long start2 = System.nanoTime(); for (int i = 0; i < finalSet.length(); i++) { if (!finalSet.get(i)) { continue; } campaignIds.add(i); } long end2 = System.nanoTime(); System.out.println("time2 : " + (end2-start2)); return campaignIds; } /** * 删除索引 * * @param campaingId 广告ID */ public void dropIndex(int campaingId) { //取出满足所有定向条件的集合 for (BitSet campaingBitSet : indexes.values()) { campaingBitSet.clear(campaingId); } } /** * 定向类型枚举 */ public static enum TargetEnum { //性别定向 GENDER_MALE, GENDER_FEMALE, //地域定向 AREA_BEIJING, AREA_SHAGNHAI; } }
四 BitSet说明
(1)设置位
void set(int bitIndex)
(2)获取位
boolean get(int bitIndex)
(3)操作
void and(BitSet set) //与
void or(BitSet set) //或
void xor(BitSet set) //异或
(4)清除位
void clear(int bitIndex)
相关推荐
bitset - Go包实现 bitsets
bitset用法bitset用法bitset用法bitset用法bitset用法bitset用法
C语言头文件 BITSETC语言头文件 BITSETC语言头文件 BITSETC语言头文件 BITSETC语言头文件 BITSETC语言头文件 BITSETC语言头文件 BITSETC语言头文件 BITSETC语言头文件 BITSETC语言头文件 BITSETC语言头文件 BITSETC...
在C++的STL中实现由一个bitset类模板,其用法如下: std::bitset<64> bs; 也就是说,这个bs只能支持64位以内的位存储和操作;bs一旦定义就不能动态增长了。本资源附件中实现了一个动态Bitset,和标准bitset兼容。 /*...
自己实现的bitset数据结构,在vs2005下编译通过。有测试成素。
基于JDK1.8的BitSet 源码分析, 描述了实现的原理 个方法的含义 虽然没有写出实际的测试代码 但是只要是细度了我的这个分析 在使用的时候就不是问题了
acm相关资料vector、bitset、大数乘法等等
描述 该程序包包含固定大小的内存中位集的有效实现。 BitSet支持的操作是: ...索引范围检查和获取位置和掩码的函数调用是当前实现中最昂贵的部分。 $ go test -bench=. PASS BenchmarkGet 500000000 6.
使用C++编写的遗传算法,代码量200行左右,供大家学习研究,互相交流。
文档模仿STL库的BITSET写的一个bitset,但是和STL不同的是这个类是一个可以动态扩展的,使用方法和STL的类似,可以参考STL使用
轻型位集实现 安装 $ npm install --save speedr-bitset 用法 import BitSet from 'speedr-bitset' let bs1 = new BitSet ( 64 ) let bs2 = new BitSet ( 64 ) bs1 . set ( 3 , true ) bs1 . set ( 4 , true ) bs1...
C++ bitset——高端压位卡常题必备STL ———————————————————— 以下内容翻译自cplusplus.com,极大地锻炼了我的英语能力。 bitset存储二进制数位。 bitset就像一个bool类型的数组一样,但是有空间...
位集转到语言库以在非负整数和布尔值之间进行映射描述包位集实现位集,即非负整数和布尔值之间的映射。 它应该比map [uint] bool更有效。 它提供了设置,清除,翻转和测试单个整数的方法。 但它也提供集合相交,并集...
FastBitSet.js:速度优化的BitSet实现 当存储的值是相当小的整数时,BitSet(也称为Bitmap或位向量)是实现一组的理想数据结构。 它可能比通用集实现快几个数量级。 特别是,BitSet具有对设置操作(联合,差,交)...
C++的 bitset 在 bitset 头文件中,它是一种类似数组的结构,它的每一个元素只能是0或1,每个元素仅用1bit空间。 下面是具体用法 构造函数 bitset常用构造函数有四种,如下 bitset<4> bitset1; //无参构造,...
它可用于实现位图索引。 它所依赖的 EWAH 格式用于运行 GitHub 的 git 实现。 字对齐压缩的目标不是实现最佳压缩,而是提高查询处理时间。 因此,我们尝试节省 CPU 周期,可能以存储为代价。 然而,我们实现的 EWAH ...
下面小编就为大家带来一篇使用bitset实现毫秒级查询(实例讲解)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
C++下的bitset,强大而简单的位运算功能,象使用数组一样对位进行操作
bitset是一个软件包,可为Go提供高效的位集实现。 文献资料 [ ]( ) 您可以在线查看项目的完整go doc样式文档,而无需使用以下位置的GoDoc网站安装此软件包: ://godoc.org/github.com/jrick/bitset 使用godoc...