插楼算法

作者: 编程的蚂蚁 | 来源:发表于2018-08-08 20:07 被阅读32次

情景描述：

在一个视频Feed列表里面，根据一个确定的策略插入广告。

策略字段：

策略字段	含义
firstPos	广告首楼的位置
interval	广告的间隔
preInterval	提前几楼请求广告

举例：

首楼广告在第4楼，广告的间隔是10个楼层，需要提前2楼请求广告。那么Feed列表到达第二楼的时候就要进行广告数据的请求，然后插入到第4楼，如果成功插入后，那么第二条广告应该举例第一条广告10楼的间隔，也就是说第二个广告应该在第15楼，那么用户达到第13楼的时候，就要预取第二条广告，然后插入到15楼。
广告的位置满足：4 + 11N

算法：

1.如何判断当前楼层是否要发起预取？

当前广告的相对楼层（oppositeFloor）= 传过来的绝对楼层 - 基楼层 + 1 （楼层从1开始）
$oppositeFloor = floor - baseFloor + 1$
（相对楼层（oppositeFloor） + 提前预取楼层（preInterval）- 首楼位置 - 当前楼层前面的广告数目（preAdCount））对广告的间隔取余，余数为remainder，如果remainder等于0，则要进行广告请求，否则不进行。
$remainder = (oppositeFloor + preInterval - firstPos - preAdCount) \mod interval$
如果进行广告请求，先从广告的请求缓存列表中查询当前广告的索引是否请求过，如果请求过则返回NO，不再进行请求；如果缓存列表中没有，则把当前广告的索引添加到已请求缓存列表中（requestedADArray），再返回YES，进行广告的请求。这样有效避免了来回滑动时重复的请求。
广告的索引：当remainder等于0的时候再进行计算广告索引；（当前楼层（currentFloor） + 提前预取楼层（preInterval）- 首楼位置 - 当前楼层前面的广告数目（preAdCount））对广告的间隔取整。
$adIndex = {{currentFloor + preInterval - firstPos - preAdCount} \over interval}$
由于广告的请求是异步的操作，所以请求广告成功之后不是立即进行插楼操作，先把广告索引和广告一起存入待处理广告列表（handleADArray）。

//根据当前楼层判断是否要发送广告请求
- (BOOL)isRequesteADWithFloor:(NSInteger)floor
{
    if (![self checkInterval]) {
        return NO;
    }
    NSInteger oppositeFloor = floor - self.baseFloor + 1; //相对楼层 = 实际楼层 - 基楼层 + 1 （从1开始）
    //如果相对的楼层小于提前预取的楼层数，就请求广告数据（配合首次进入视频页面立即调用）
    if (oppositeFloor <= self.preInterval) {
        for (NSDictionary *dic in self.requestedADArray) {
            NSInteger index = [[dic objectForKey:kOriginalFloor] integerValue];
            if(index == 0){
                return NO;
            }
        }
        [self.requestedADArray addObject:@{kOriginalFloor:@(0)}];  //保存广告的次序（第0个）
        return YES;
    }
    //如果相对楼层大于提前预取的楼层
    NSInteger insertCount = [self previousInsertedAdCountWithFloor:oppositeFloor];
    if ((oppositeFloor - insertCount + self.preInterval - self.firstPos) % self.interval == 0) {
        NSInteger realIndex = (oppositeFloor - insertCount + self.preInterval - self.firstPos) / self.interval;
        for(NSDictionary *dic in self.requestedADArray){
            NSInteger index = [[dic objectForKey:kOriginalFloor] integerValue];
            if(index == realIndex){
                return NO;
            }
        }
        [self.requestedADArray addObject:@{kOriginalFloor:@(realIndex)}];  //保存原始楼层(N)
        return YES;
    }
    return NO;
}

2.什么时候获取广告，如何获取插入位置？

广告的加载时机是按照客户端的操作来确定，iOS是滑动停止时获取要插入的广告。
插入位置的计算：根据传过来的绝对楼层（floor）（ps:要换算一下，因为刚进入的时候可能不是第一楼），转化为相对楼层（oppositeFloor），根据这个相对楼层获取当前楼层之前插入的广告数量。然后当前楼层之前插入的广告条数（preAdCount），加上首楼位置（firstPos），加上当前楼层对应的广告索引和楼间隔的乘积（adIndex * interval ），最后加上基楼层（baseFloor），就是广告出现的楼层（adFloor）。

相对楼层 = 绝对楼层 - 基楼层 + 1 （这里楼层从1开始）
$oppositeFloor = {floor - baseFloor} + 1$

$adFloor = adIndex * interval + preAdCount + firstPos + baseFloor$

如果adFloor和大于传过来的绝对楼层且小于当前屏幕feed列表的总数量，就是一个合法的待插入广告。如果当前的绝对楼层大于等于adFloor（滑过去了），则该广告废弃，并且从待处理广告列表移除。
广告要插入的位置 = 广告的楼层 - 1
$adInsertIndex = adFloor - 1$

//获取要插入的广告数组(一次只能获取一个来进行处理,因为实际位置严格依赖当前的状态),需要遍历使用
- (NSArray *)getInsertADArrayWithFloor:(NSInteger)floor dataSourceCount:(NSInteger)dataSourceCount
{
    if (![self checkInterval]) {
        return nil;
    }
    NSInteger oppositeFloor = floor - self.baseFloor + 1; //相对楼层 = 实际楼层 - 基楼层 + 1 （从1开始）
    NSMutableArray *insertADarray = [NSMutableArray array];
    for (NSDictionary *handleDic in self.handleADArray) {
        //取出来待处理的数据位置，反射成广告的位置
        NSInteger originalFloor = [[handleDic objectForKey:kOriginalFloor] integerValue];
        //获取前面插入广告的个数
        NSInteger insertCount = [self previousInsertedAdCountWithFloor:oppositeFloor];
        //广告的插入的楼层(当前相对楼层前面插入广告的个数 + 原始楼层 * 间隔 + 首楼位置 + 基楼层)
        NSInteger indexReal = insertCount + originalFloor * self.interval + self.firstPos + self.baseFloor;
        //如果要插入的广告的位置大于当前的楼层，并且小于数据源的个数，就认为是一个合法的广告数据
        if (indexReal > floor && indexReal < dataSourceCount) {
            //插入的广告：位置 = 楼层 - 1
            id adValue = [handleDic objectForKey:kAdValue];
            if (adValue) {
                [insertADarray addObject:@{kIndexReal:@(indexReal - 1),kAdValue:adValue,kOriginalFloor:@(originalFloor)}];//originIndex 原始的位置(N)
            }
            return insertADarray;
        }else if (floor >= indexReal) {
            //如果当前的楼层大于广告的实际要插入的位置，就抛弃（从待处理数组中清理掉）
            [self.handleADArray removeObject:handleDic];
        }
    }
    return insertADarray;
}

3.如何缓存已经插入的广告？

第二步，每次都会返回一个广告给feed列表进行插入，每次插入之后都要把插入的广告同步缓存到已插入广告列表（insertedAdArray）。
并且把该广告从待处理广告列表（handleADArray）中移除。这样每次的插入都会更新已插入广告列表和待处理广告列表。

//保存请求的数据到待处理区
- (void)insertAD:(id)ad floor:(NSInteger)floor
{
    if (![self checkInterval]) {
        return;
    }
    NSInteger oppositeFloor = floor - self.baseFloor + 1; //相对楼层 = 实际楼层 - 基楼层 + 1 （从1开始）
    //如果相对的楼层小于提前预取的楼层数，就存入广告
    if (oppositeFloor < self.preInterval) {
        [self.handleADArray addObject:@{kOriginalFloor:@(0),kAdValue:ad}];
        return;
    }
    NSInteger insertCount = [self previousInsertedAdCountWithFloor:oppositeFloor];
    if ((oppositeFloor - insertCount + self.preInterval - self.firstPos) % self.interval == 0) {
        NSInteger originalFloor = (oppositeFloor - insertCount + self.preInterval - self.firstPos) / self.interval;
        [self.handleADArray addObject:@{kOriginalFloor:@(originalFloor),kAdValue:ad}];
    }
}

4.如何获取一个楼层之前插入广告的数量？

当前楼层为相对楼层，根据公式，计算出该相对楼层之前有多少个广告位(adCount)，然后遍历已插入广告列表（insertedAdArray），当插入广告的索引小于广告位数的时候，表示该广告已经插入，preAdCount加1。
最后，将preAdCount返回即可。
$oppositeFloor = {floor - baseFloor} + 1$
$adCount = {{oppositeFloor - firstPos} \over interval}$
此时如果 ${(oppositeFloor - firstPos) \mod interval}$ 不为0，则adCount + 1；

//查询一个楼层前面插入广告的条数
- (NSInteger)previousInsertedAdCountWithFloor:(NSInteger)floor
{
    NSInteger count = 0;
    if (floor - self.firstPos > 0){
        NSInteger realIndex = (floor - self.firstPos) / self.interval;
        if ((floor - self.firstPos) % self.interval != 0) {
            realIndex = realIndex + 1;
        }
        for (NSDictionary *dic in self.insertedAdArray) {
            NSNumber *index = [dic objectForKey:kOriginalFloor];
            if ([index integerValue] < realIndex) {
                count++;
            }
        }
    }
    return count;
}

//处理插入的广告数据记录
- (void)dealInsertedADWithADArray:(NSArray *)adArray
{
    for (NSDictionary *adDic in adArray) {
        [self.insertedAdArray addObject:adDic];  //记录插入的数据
        [self dealHandleADArrayWith:adDic];      //待处理数据清理已经处理的数据
    }
}

//处理插入之后待处理的数据记录
- (void)dealHandleADArrayWith:(NSDictionary *)adDic
{
    NSInteger adDicFloor = [[adDic objectForKey:kOriginalFloor] integerValue];
    for (NSDictionary *dic in self.handleADArray) {
        NSInteger dicFloor = [[dic objectForKey:kOriginalFloor] integerValue];
        if (dicFloor == adDicFloor) {
            [self.handleADArray removeObject:dic];
        }
    }
}

注意点：
1.feed列表的广告是一次插入一条，因为每次广告的位置依赖于广告的插入之后的结果。
2.每次Feed插入广告之后，已经要将插入广告的信息（广告和索引值）传给该管理者，以便于管理者更新待处理广告列表和已插入广告列表的数据。
3.参与计算的广告楼层都是使用的相对楼层，且都是从1开始的，注意要做相应的转换操作。

插楼算法

情景描述：

策略字段：

举例：

算法：

1.如何判断当前楼层是否要发起预取？

2.什么时候获取广告，如何获取插入位置？

3.如何缓存已经插入的广告？

4.如何获取一个楼层之前插入广告的数量？

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读