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

大佬们,假设下面这个是已经排序过的关于时间的数组,现在需要添加到不同距离当前年份时间的数组,能用二分查找去实现吗?

  •  
  •   unregister · 2022-08-18 22:37:32 +08:00 · 1269 次点击
    这是一个创建于 588 天前的主题,其中的信息可能已经有所发展或是发生改变。

    public void test(){ String time2 = "2022-08-31"; for(int i = 0; i<times.size();i++){ String time = times.get(i); if(betweenMonth(time,time2) < 12){ oneYearTimes.add(time); } else if(betweenMonth(time,time2) >= 12 && betweenMonth(time,time2) < 24 ){ one2twoYearTimes.add(time); } else if(betweenMonth(time,time2) >= 24 && betweenMonth(time,time2) < 36 ){ two2threeYearTimes.add(time); } else if(betweenMonth(time,time2) >= 36 && betweenMonth(time,time2) < 48 ){ three2fourYearTimes.add(time); } else if(betweenMonth(time,time2) >= 48 && betweenMonth(time,time2) < 48 ){ four2fiveYearTimes.add(time); } else if(betweenMonth(time,time2) >= 60 ){ moreThanFiveYearTimes.add(time); } } }

    static Long betweenMonth(String time1, String time2){
        return ChronoUnit.MONTHS.between(parse(time1), parse(time2));
    }
    
    static LocalDate parse(String str){
        DateTimeFormatter df = DateTimeFormatter.ofPattern("yyyy-MM-dd");
        return LocalDate.parse(str, df);
    }
    
    第 1 条附言  ·  2022-08-18 23:36:55 +08:00
    能不能利用分治的思想。。先给时间排序,然后取中间值,递归下去这样。除了临界点算一下年份之外,其他的 item 都不计算直接存放到数组里面。
    28 条回复    2022-08-20 20:40:52 +08:00
    JasonLaw
        1
    JasonLaw  
       2022-08-18 22:50:24 +08:00
    建议你补全并格式化一下代码,描述清楚你的问题。
    unregister
        2
    unregister  
    OP
       2022-08-18 22:51:12 +08:00
    就是根据两个日期的之间相隔的月份,存放到距离 2022-08-31 这个时间点 相差不同年份的数组中。
    unregister
        3
    unregister  
    OP
       2022-08-18 22:56:24 +08:00
    @JasonLaw 好滴,现在就是需要从一个包含很多时间的集合 times ,根据当前的时间判断距离现在多少年,比如< 12 个月就是一年内,12 - 24 个月存放到 1-2 年的数组中,大于 60 个月的统统都算 5 年以上,这个编辑操作不太会,下面是重新整理过的代码 https://pastebin.com/Vjev1xac
    JasonLaw
        4
    JasonLaw  
       2022-08-18 23:02:01 +08:00
    @unregister #3 如果我没理解错的话,你就是想要减少 if, else if 的次数,对吧?
    JasonLaw
        5
    JasonLaw  
       2022-08-18 23:04:51 +08:00   ❤️ 1
    @JasonLaw #4 如果是的话,你完全可以使用数组来存储,然后计算`month_diff/12`来决定是存储在那个 index 。
    wxf666
        6
    wxf666  
       2022-08-18 23:10:47 +08:00   ❤️ 1
    伪代码:

    时间段数组 = [一年时间表,一至两年时间表,二至三,三至四,四至五,五以上];

    for 待分类时间 in 待分类时间表
     时间段数组[max(betweenMonth(待分类时间, "2022-08-31") / 12, 时间段数组.size() - 1)].add(待分类时间);


    这样?
    wxf666
        7
    wxf666  
       2022-08-18 23:11:40 +08:00
    写错了,max 改为 min
    unregister
        8
    unregister  
    OP
       2022-08-18 23:14:00 +08:00
    @JasonLaw 也不完全是啦,就是 if else 里面 不是需要计算相差的月份吗?如果这种写法的话 100 万数据的话,需要比较将近 200 万次。这样性能就很差,就想看看有没有能够减少比较次数的方法。
    unregister
        9
    unregister  
    OP
       2022-08-18 23:18:21 +08:00
    @wxf666 这个方法挺好的,感觉比较优雅。
    JasonLaw
        10
    JasonLaw  
       2022-08-18 23:22:14 +08:00 via iPhone
    @unregister #8 你可以理解计算相差月份是需要常量时间的。我不太理解你所说的“ 100 万数据的话,需要比较将近 200 万次”。
    unregister
        11
    unregister  
    OP
       2022-08-18 23:29:14 +08:00
    @JasonLaw 就是 betweenMonth 这个方法中,两个日期需要做一次减法操作,else if 里面 需要计算两次日期差 ,那就是接近 200 万次的计算量了。
    zmal
        12
    zmal  
       2022-08-18 23:30:08 +08:00
    写个返回 time 距今几个 12 月的函数,stream 流用该函数分组,再用 treemap 搜集。
    unregister
        13
    unregister  
    OP
       2022-08-18 23:36:15 +08:00
    @zmal 能不能利用分治的思想。。先给时间排序,然后取中间值,递归下去这样。除了临界点算一下年份之外,其他的 item 都不计算直接存放到数组里面。
    JasonLaw
        14
    JasonLaw  
       2022-08-18 23:37:53 +08:00 via iPhone
    @unregister #11 其实你说的这些在时间复杂度上面没有多大区别,都是θ(len(times)),因为每次循环最后运算 6 次,我说的方法就是把 6 次变为 1 次。
    zmal
        15
    zmal  
       2022-08-18 23:39:14 +08:00
    一次遍历的时间复杂度是 N 。
    排序的时间复杂度是 N*logN ,排序再二分还得*logN ,你咋想的大兄弟。
    JasonLaw
        16
    JasonLaw  
       2022-08-18 23:42:55 +08:00 via iPhone
    @unregister #13 将 times 进行排序就需要θ(nlgn)了🤕。我很想知道你是怎么做到“ 除了临界点算一下年份之外,其他的 item 都不计算直接存放到数组里面”的,写一下代码或伪代码让我看一下,我真的很想知道。
    zmal
        17
    zmal  
       2022-08-18 23:52:06 +08:00   ❤️ 1
    我明白你的意思了,你是觉得你的一坨 if else 代码需要比较 6 次有多余耗时?其实优化成 除 12 再分组就可以了。
    而且计算时间复杂度时常数的部分可以忽略。而且大于小于这种计算在这个场景里的时间消耗可以忽略不计。
    unregister
        18
    unregister  
    OP
       2022-08-18 23:53:17 +08:00
    @zmal 哈哈哈哈,看来我之前没整明白。
    @JasonLaw 😅,看来我之前没整的很清楚,代码实现的有问题,有点"急“了,希望大佬包涵一下。
    unregister
        19
    unregister  
    OP
       2022-08-18 23:56:58 +08:00
    @zmal 嗯嗯好的,我在去测试一下。
    JasonLaw
        20
    JasonLaw  
       2022-08-19 08:17:15 +08:00 via iPhone
    @zmal #12 不太懂为什么要用 tree map ,OP 的源代码应该没这样的需求,更重要的是,涉及到排序的话,时间复杂度就是 O(nlgn)了,而且 hash table 会用到更多的 memory ,计算 index 也会更加耗时。如果我说错的话,欢迎指出。
    JasonLaw
        21
    JasonLaw  
       2022-08-19 08:22:16 +08:00 via iPhone
    @unregister #18 我不是大佬,我还是在一直学习。如果你想要更加理解代码的话,真的建议你学习一下算法和数据结构,https://neetcode.io/是个好地方,我也在使用这个网站,大家一起进步。
    aguesuka
        22
    aguesuka  
       2022-08-19 09:30:33 +08:00
    首先你的代码应该是这样, 也就是先把重复的代码抽离成方法.

    public void test() {
    String time2 = "2022-08-31";
    for (int i = 0; i < times.size(); i++) {
    String time = times.get(i);
    var monthsBetween = betweenMonth(time, time2);
    findTimeList(monthsBetween).add(time);
    }
    }

    List<String> findTimeList(long monthsBetween){
    // TODO
    }
    zmal
        23
    zmal  
       2022-08-19 11:34:53 +08:00
    @JasonLaw
    private int 返回入参时间距今几年(String time);
    Map<Integer, List<String>> yearMap = list.stream().collect(Collectors.groupingBy(this::返回入参时间距今几年, TreeMap::new, Collectors.toList()));

    treeMap 只是用来把年份做个排序,遍历的时候方便。不用也可以。
    msg7086
        24
    msg7086  
       2022-08-19 11:50:14 +08:00
    你想把扫全表变成二分搜来做 grouping 是吗?

    确实可以做的。

    比如说 Ruby 里有 bsearch_index 可以通过条件在数组里做二分搜,返回第一个满足条件的项的下标。
    假设 times 是时间数组,降序,time2 是比较日期
    year2_date = time2 - 1.year
    year2_idx = times.bsearch_index {|time| time < year2_date} #找到第一个 1 年以前的日期
    year3_date = time2 - 2.year
    year3_idx = times.bsearch_index {|time| time < year3_date} #找到第一个 2 年以前的日期
    然后把 0-year2_idx 的和 year2_idx-year3_idx 等等的 slice 切出来放进不同数组就行了。
    JasonLaw
        25
    JasonLaw  
       2022-08-19 11:51:59 +08:00 via iPhone
    @zmal #23 有一个疑问,使用 tree map 的话,时间复杂度是 O(nlgn),对吗?
    zmal
        26
    zmal  
       2022-08-19 11:55:10 +08:00
    @JasonLaw
    ??? treeMap 的 key 是 int 值的年份,总共才 5 个数,和时间集合的长度无关。
    JasonLaw
        27
    JasonLaw  
       2022-08-19 12:06:56 +08:00 via iPhone
    @zmal #26 对,如果不包含所有年份差的话,就是只有 6 个 key 。
    unregister
        28
    unregister  
    OP
       2022-08-20 20:40:52 +08:00
    @JasonLaw Thank you,已经收藏啦
    @aguesuka 学习了。
    @msg7086 谢谢大佬的思路。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2017 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 16:18 · PVG 00:18 · LAX 09:18 · JFK 12:18
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.