V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
bingdong700
V2EX  ›  程序员

有个三维度的搜索,求高手指教一下算法!

  •  
  •   bingdong700 ·
    bingdong700 · 2016-08-18 22:38:05 +08:00 · 1984 次点击
    这是一个创建于 3017 天前的主题,其中的信息可能已经有所发展或是发生改变。
    公司在做终端投放广告的业务,你可以理解成公共场所的显示器吧。现有一百个显示器,每个显示器上有八个广告位。之所以说三维,就是不同机器的不同广告位的不同空闲时间段。因为每个广告位对应的广告订单的起始时间不一样,这样就存在空档期。现在有人下单投放广告需要搜索出来在指定的时间段内的空档广告位,要怎么做才能减少广告位的空闲浪费呢???

    下订单的时候要根据一个指定时间段来搜索空闲广告位。我目前的想法,把这一百个显示器的八个广告位理解成八百个独立广告位,每个广告位会对应若干条不同时间段的订单,分别记录不同的起始时间。用户在搜索的时候,就需要遍历这八百个广告位,然后将新订单时间来对比历史订单,若没有重叠时间则为可用广告位。

    以上想法在目前可能应付得过来,可是后期,我们会有 1000 台设备,甚至更多。而且,若屏幕允许左右滑动,一个显示器就有可能有 16 或者 24 个广告位。就算不滑动,广告多了会考虑将每个广告位做成轮播图片,控制轮播循环图片不超过五张。这样一个广告位对比历史订单,同时间段内重叠不超过五次。这样计算起来真是太麻烦了。求指教,应该会有更好的方法。
    9 条回复    2016-08-27 01:04:11 +08:00
    yangxin0
        1
    yangxin0  
       2016-08-18 22:44:03 +08:00 via iPhone
    工作内容的咨询是要按小时收费的
    htfy96
        2
    htfy96  
       2016-08-18 23:11:22 +08:00 via Android
    检查一个广告位在一段时间内可能被多少个之前的广告占用,只要查找出没有在这段时间内占用位置的广告数量。

    没有占用位置的用 count(end_time <= current_start_time) + count(start_time >= current_end_time)得出。我猜建了索引的话应该挺快的?
    binux
        3
    binux  
       2016-08-18 23:19:56 +08:00
    「把这一百个显示器的八个广告位理解成八百个独立广告位」
    并不合理,客户是买一个显示器上的八个广告位,还是八个显示器上的一个广告位。

    你确定产品需求要确定到具体某台显示器的某个广告位某个时间点第几个滑出吗?
    显示器不能分区吗?八个广告位随机位置不可以吗?
    bingdong700
        4
    bingdong700  
    OP
       2016-08-19 00:11:51 +08:00
    @binux 显示器布置在不同的地点,所以是买不同显示的某个级别广告位。八个广告位大小不全相同,级别也不全相同,同样级别的可能大小也不一样,这里只用考虑同一个广告位级别,不用考虑不同显示器。
    bingdong700
        5
    bingdong700  
    OP
       2016-08-19 00:52:01 +08:00
    重新整理一遍:

    假定现有 100 台布置在不同地点显示器,每个显示器上有 8 个不全相同的广告位(不同级别,不同大小。同级别也有可能大小不一样,暂时只考虑级别),不同广告位有不同空闲时间段可投放广告。一个订单在同一时间段对应多个广告位,每个广告位对应多个不同时间段的订单,因为起始结束时间不一样,这样就存在空档期。现在有客户下单投放广告,需要搜索出来在指定的时间段内的有空档广告位,要怎么做才能减少广告位的空闲浪费呢?

    我目前的想法,把这 100 台显示器的 8 个广告位理解成 800 个独立广告位,每个广告位会对应若干条不同时间段的订单,分别记录不同的起始结束时间。用户在搜索的时候,后台就需要遍历这 800 个广告位,然后将客户指定的时间段来对比历史订单(后面待执行)的时间段,若没有重叠时间则为可用广告位。

    以上想法在目前可能应付得过来,可是后期,会有 1000 甚至更多台显示器,而且,若屏幕允许左右滑动,一个显示器就有可能有 16 或者 24 个广告位。广告多了还会考虑将每个广告位做成轮播图片形式,也就是多个订单可选这个广告位。但为了保证广告展示时间会限制轮播循环图片不超过五张。这样计算出一个有效广告位,还需要对比历史订单,同时间段内重叠不超过五次。至于根据重叠时间长短来取舍是后话了。 1000 台显示器、 24 个广告位、重叠不超过 5 次,应该还有更好的算法,求指教。
    lecher
        6
    lecher  
       2016-08-19 01:12:43 +08:00
    搜索可用资源这个事情,把资源维度从多维展开,降到一维就好了。
    这个资源计算并不是 800 个广告位的颗粒度,还要算上时间颗粒度。比如按 10 秒为时间颗粒度的话,一个广告是 20 秒就要占用两个时间单位,这样拆下来,一天大概是 800×8640 个单位。这样可以把广告轮播的维度展开。
    提前将这些单位预先创建好。如果是在数据库的话,就相当于每条记录一个单位,按每天的数据提前创建 800×8640 条记录,哪怕提前创建一年的数据也可以的,这种已经展开的数据,没有复杂的汇总计算。建个索引速度快得很。

    一旦用户决定购买一个时间段的某个广告位,直接把这个广告需要占用的单位标识为使用。
    这样下一个用户决定订购的时候,可以直接搜没使用的单位汇总成可选时间段。

    至于要扩展广告轮播之类的,也就是增加展示单位的事情。搜索可用单位还是同样的逻辑。

    以上是获取可用资源显示成时间段给用户的事情。
    至于要把客户订单按逻辑展开,怎么标注要占用的展示单位,间隔之类的。都拿到所有可用的展示单位了,怎么安排就简单很多。
    winglight2016
        7
    winglight2016  
       2016-08-19 13:53:40 +08:00
    你把(显示屏+位置)生成一个编号,这不就变成了一个工单排号系统了?或者当成一个美甲预约系统?
    bingdong700
        8
    bingdong700  
    OP
       2016-08-27 01:01:03 +08:00
    @yangxin0 你得有两把刷子才行啊
    bingdong700
        9
    bingdong700  
    OP
       2016-08-27 01:04:11 +08:00
    @htfy96 谢谢,我之前是这么想的。

    @binux 谢谢,现在不用考虑那么复杂了。

    @lecher 谢谢指教,学习了。

    @winglight2016 谢谢
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3385 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 05:02 · PVG 13:02 · LAX 21:02 · JFK 00:02
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.