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

用什么算法,最快算出两个时间段的重叠部分呢

  •  
  •   meteor2013 · 2015-07-19 23:38:45 +08:00 · 8706 次点击
    这是一个创建于 3417 天前的主题,其中的信息可能已经有所发展或是发生改变。
    任意两个时间序列:

    比如
    A: 3,4,5, 7,8,910, 18,19
    B: 4,5, 16,17,18,19,20,

    输出
    4,5 18,19
    41 条回复    2015-08-03 17:57:52 +08:00
    zhengnanlee
        1
    zhengnanlee  
       2015-07-19 23:48:15 +08:00 via Android
    最长公共子序列?
    lixia625
        2
    lixia625  
       2015-07-19 23:49:49 +08:00
    print [i for i in B if i in A]
    wy315700
        3
    wy315700  
       2015-07-19 23:52:03 +08:00
    线段树吧
    aheadlead
        4
    aheadlead  
       2015-07-20 00:13:11 +08:00
    随便找个查找树吧…
    ariestiger
        5
    ariestiger  
       2015-07-20 00:15:36 +08:00
    你这是有间断的两个时间序列,问题就不应该是你这样的。
    本质上就是 Range 之间的交,差运算了。
    之前做交易系统时,在订单发生退货退款时,要计算订单从下单到现在“真正”用了多少时间(也就是要把发生退货退款处理的时间段排队掉,而一个订单生命周期中可能发生多次退货退款,因为有的退货退款可能会被拒绝,用户后面可以继续申请退货退款),从而决定是不是要执行相应的定时任务。
    因为 Java 里没有像 Ruby, Python 里的 Range 类,只能自己写个类来做一下了。
    这个计算主要就是一个主线时间段,从订单最后更新时间到现在,另一个是若干退货退款的时间段(发生时间到结束时间),写个方法,循环,对每个退货退款时间段,看它和主线时间段的关系(其实主线时间段肯定是包含退货退款时间段的,不然就异常了),然后进行相减就行了。
    你这里的话,主线时间段可以就用[min(A), max(A)],需要排队的支线时间段,从 A 和 B 中去提取,自己去考虑间隔点的问题了,然后做 Range 之间的运算就好了。
    meteor2013
        6
    meteor2013  
    OP
       2015-07-20 00:16:00 +08:00 via iPhone
    @zhengnanlee 不是最长公共子序列,是所有公共子序列
    clink8001
        7
    clink8001  
       2015-07-20 00:28:41 +08:00
    用python 可以这么做:

    a = [3,4,5, 7,8,910, 18,19 ]
    b = [ 4,5, 16,17,18,19,20]
    h = filter(lambda f: f in a, b)
    print h
    messyidea
        8
    messyidea  
       2015-07-20 00:31:20 +08:00 via Android
    线段树蛮方便的
    iloahz
        9
    iloahz  
       2015-07-20 00:35:29 +08:00
    时间序列是不是可以认为可以有序啊,排好序两个指针跑一遍?
    SoloCompany
        10
    SoloCompany  
       2015-07-20 00:57:06 +08:00
    题目没说清楚,那么久成了遍准求交集问题
    set(A).retainAll(set(B)) 完事 ((
    tushiner
        11
    tushiner  
       2015-07-20 01:01:47 +08:00
    看了九章算法的广告,只看标题以为楼主和他们是一路的
    sciooga
        12
    sciooga  
       2015-07-20 01:12:56 +08:00 via Android
    有序的?
    睡前随便想了一下 Python 应该是这样写比较快吧?

    A = [3, 4, 5, 7, 8, 9, 10, 18, 19]
    B = [4, 5, 16, 17, 18, 19, 20]
    b_index = 0
    b_end_index = len(B)
    for i in A:
    ....while(b_index<b_end_index):
    ........if B[b_index] > i:
    ............break
    ........elif B[b_index] == i:
    ............print i
    ............break
    ........b_index += 1
    meteor2013
        13
    meteor2013  
    OP
       2015-07-20 01:20:56 +08:00 via iPhone
    @iloahz 对,是有序的
    meteor2013
        14
    meteor2013  
    OP
       2015-07-20 01:23:38 +08:00 via iPhone
    @messyidea
    @wy315700

    怎么个线段树?
    msg7086
        15
    msg7086  
       2015-07-20 01:47:58 +08:00
    时间序列是什么?
    时间点?
    时间段?
    题目好乱根本读不明白……
    linxy
        16
    linxy  
       2015-07-20 01:48:50 +08:00 via Android
    区间查找一般都是线段树。
    meteor2013
        17
    meteor2013  
    OP
       2015-07-20 03:20:04 +08:00
    @msg7086

    A: 3,4,5, 7,8,9,10, 18,19 => A序列的子序列有3-5, 7-10和18-19
    B: 4,5, 16,17,18,19,20,=> B有4-5,和 16-20两个子序列

    => A和B相同的重叠部分就是:4-5和 18-19两段。
    msg7086
        18
    msg7086  
       2015-07-20 03:29:00 +08:00
    @meteor2013 性能好点的用线段树,性能差点的用归并比较。
    我不懂前者。
    mangocool
        19
    mangocool  
       2015-07-20 08:58:25 +08:00
    算法,咱不懂,学习!
    messyidea
        20
    messyidea  
       2015-07-20 09:04:14 +08:00
    我感觉如果输入有序,且每个点都输入而不只输入时间段的起始和结束的话只需要扫一遍就可以了,复杂度O(2n), 如果是n个时间序列,要求覆盖m遍及以上的时间段,可以用线段树来处理。 说实话只有两个时间段用线段树小题大做了。
    iker01
        21
    iker01  
       2015-07-20 09:30:45 +08:00
    一般用线段树解决区间问题。
    meteor2013
        22
    meteor2013  
    OP
       2015-07-20 09:45:41 +08:00 via iPhone
    @iker01 能举个例子具体说说吗?
    meteor2013
        23
    meteor2013  
    OP
       2015-07-20 09:51:19 +08:00 via iPhone
    @iker01 还有就是线段树一般处理无序序列,这个是有序的,能减少复杂度吗?
    likuku
        24
    likuku  
       2015-07-20 10:01:18 +08:00
    python

    使用 set (集合) 类型一步搞定:

    # & 交集
    >>> print ( set([4, 5, 16, 17, 18, 19, 20]) & set([3, 4, 5, 7, 8, 9, 10, 18, 19]))
    set([18, 19, 4, 5])
    RisingV
        25
    RisingV  
       2015-07-20 10:05:23 +08:00
    就是求两个小整数数组交集,bitmap 足够快,O(m+n)
    meteor2013
        26
    meteor2013  
    OP
       2015-07-20 10:09:24 +08:00 via iPhone
    @likuku

    集合好像感觉是找相同点的交集。
    但是题目是要输出子序列。概念上略有不同。

    @msg7086

    A: 3,4,5, 7,8,9,10, 18,19
    => A序列的子序列有三个:3-5, 7-10和18-19

    B: 4,5, 16,17,18,19,20,
    => B有4-5,和 16-20两个子序列

    输出:

    => A和B相同的重叠部分就是两个子序列:4-5和 18-19两段。
    omph
        27
    omph  
       2015-07-20 10:16:40 +08:00
    楼主表达能力堪忧,早该按 17 楼表达清楚
    C++ 可以把 A 存到 map,key 是开始时间,val 是结束时间
    使用 lower_bound,upper_bound 把 B 的开始和结束到 map 中定位(二分查找),两个定位的中间部分就是重叠部分
    因 AB 有序,所以后续定位不用从头开始
    kzzhr
        28
    kzzhr  
       2015-07-20 10:21:04 +08:00
    区间树干这个是不是太重了。。
    这好像是当年学hash的经典题型,题意不是很清楚。。
    meteor2013
        29
    meteor2013  
    OP
       2015-07-20 10:34:46 +08:00 via iPhone
    @omph
    @kzzhr

    二分查找听起来不错, 但如果A和B序列“非常非常大”,二分查找效率会不会不理想?
    这时候用线段树有帮助吗?
    ant_sz
        30
    ant_sz  
       2015-07-20 11:14:13 +08:00
    先把两个序列都处理成 [start, end] 这样range 的序列,然后用两个指针指向两个range序列的头,依次后移两个指针来计算range的交。这应该是一个 O(M+N)的算法,我觉得应该比 O(M log N) 的 要好。

    1. 如果 a 指向的 range 的结束时间 大于 b 指向的range 的开始时间,把 a 往后移动,反之亦然。
    2. 如果 a 指向的 range 和 b 指向的 range 有交集,求交集并加入结果,然后将 a 和 b 结束时间较早的那个往后移动。

    @meteor2013 另外,二分查找的性能其实是非常好的。A 和 B 序列非常大,最大能有多大呢?2^32 = 4G 个元素算不算大?然而用二分查找只需要 32 次迭代。二分查找的问题在于如果序列非常大,可能难以全部load到内存里,而且二分查找的时候有可能访问的内存位置跳跃比较大,因此可能需要频繁的置换虚拟内存。

    线段树的查询也是需要 O(log N) 的时间的,而且你总要遍历其中一个序列所以时间复杂度综合来看也差不多 O(M log N) ,而且线段树的实现比较复杂,需要的内存空间大约是 O(2N) ,而且不一定有二分查找快,建树本身需要 O(N) 的时间复杂度。所以我觉得并不是一个好的方法。
    ffffwh
        31
    ffffwh  
       2015-07-20 11:22:09 +08:00
    从左到右linear scan,碰到开闭区间标记一下
    stackpop
        32
    stackpop  
       2015-07-20 12:19:01 +08:00
    准确描述问题先吧。

    根据你的描述,求的是离散的点的交集啊,数据是有序的,因而就是最长公共子序列啊。

    如果说是很多个时间区间的集合,然后求哪些时间段有交叉,需要使用线段树。
    yuankui
        33
    yuankui  
       2015-07-20 12:36:25 +08:00
    1. 两个序列排序
    2. 两个指针指向两个序列
    3. 谁小谁后移
    4. 相等的话,就加入result_list,并且同时后移
    5. 直到有一个指针到末尾

    如果时间序列没有排序的话,这是个O(2*logN + N) = O(logN)的算法
    如果有序的话,这是个O(N)的算法
    messyidea
        34
    messyidea  
       2015-07-20 13:27:24 +08:00
    AB序列非常大的话可以进行一次预处理,先离散化数据。
    XadillaX
        35
    XadillaX  
       2015-07-20 14:53:19 +08:00
    线段树正解。
    KotiyaSanae
        37
    KotiyaSanae  
       2015-07-20 15:18:04 +08:00
    ……按错键发出去了。这篇paper前半部分讨论了几种(三种?)方法,找交集。里面有一个双堆法,个人感觉挺有意思。
    qwsqwa
        38
    qwsqwa  
       2015-07-20 15:36:59 +08:00
    @yuankui 是正解。
    楼主给的数据不是时间段,是时间点,只是几个时间点连起来就是时间段了。
    如果给的是若干时间段,比如原问题中
    A: 3,4,5, 7,8,910, 18,19
    B: 4,5, 16,17,18,19,20
    写成
    A:3,5,7,10,18,19
    B:4,5,16,20
    的话才会用到线段树。
    qw7692336
        39
    qw7692336  
       2015-07-20 20:47:57 +08:00
    经过排序到数据?
    linxy
        40
    linxy  
       2015-07-20 21:02:40 +08:00
    @yuankui 这个好…
    kzzhr
        41
    kzzhr  
       2015-08-03 17:57:52 +08:00
    @meteor2013 所以我说hash嘛。区间数烧内存是小事,关键是需求没那么复杂,就比如现在让你找(1,n)的最大值,你也可以先排个序,问题是没有必要。奥对了,#33也给出了logn的解法,跟线段树时间一样,但是编码复杂度小很多。不过个人觉得还是hash优先。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1309 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 17:51 · PVG 01:51 · LAX 09:51 · JFK 12:51
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.