大佬们，假设下面这个是已经排序过的关于时间的数组，现在需要添加到不同距离当前年份时间的数组，能用二分查找去实现吗？
unregister · 2022-08-18 22:37:32 +08:00 · 1368 次点击这是一个创建于 827 天前的主题，其中的信息可能已经有所发展或是发生改变。
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 都不计算直接存放到数组里面。
 |
1
JasonLaw 2022-08-18 22:50:24 +08:00
建议你补全并格式化一下代码，描述清楚你的问题。
|
 |
2
unregister OP 就是根据两个日期的之间相隔的月份，存放到距离 2022-08-31 这个时间点 相差不同年份的数组中。
|
|
3
unregister OP @JasonLaw 好滴，现在就是需要从一个包含很多时间的集合 times ，根据当前的时间判断距离现在多少年，比如< 12 个月就是一年内，12 - 24 个月存放到 1-2 年的数组中，大于 60 个月的统统都算 5 年以上，这个编辑操作不太会，下面是重新整理过的代码 https://pastebin.com/Vjev1xac 。
|
|
4
JasonLaw 2022-08-18 23:02:01 +08:00
@unregister #3 如果我没理解错的话，你就是想要减少 if, else if 的次数，对吧？
|
|
5
JasonLaw 2022-08-18 23:04:51 +08:00  1
@JasonLaw #4 如果是的话，你完全可以使用数组来存储，然后计算`month_diff/12`来决定是存储在那个 index 。
|
 |
6
wxf666 2022-08-18 23:10:47 +08:00 1
伪代码：
时间段数组 = [一年时间表，一至两年时间表，二至三，三至四，四至五，五以上]; for 待分类时间 in 待分类时间表 时间段数组[max(betweenMonth(待分类时间, "2022-08-31") / 12, 时间段数组.size() - 1)].add(待分类时间); 这样？ |
|
7
wxf666 2022-08-18 23:11:40 +08:00
写错了，max 改为 min
|
|
8
unregister OP @JasonLaw 也不完全是啦，就是 if else 里面 不是需要计算相差的月份吗？如果这种写法的话 100 万数据的话，需要比较将近 200 万次。这样性能就很差，就想看看有没有能够减少比较次数的方法。
|
|
9
unregister OP @wxf666 这个方法挺好的，感觉比较优雅。
|
|
10
JasonLaw 2022-08-18 23:22:14 +08:00 via iPhone
@unregister #8 你可以理解计算相差月份是需要常量时间的。我不太理解你所说的“ 100 万数据的话，需要比较将近 200 万次”。
|
|
11
unregister OP @JasonLaw 就是 betweenMonth 这个方法中，两个日期需要做一次减法操作，else if 里面 需要计算两次日期差 ，那就是接近 200 万次的计算量了。
|
 |
12
zmal 2022-08-18 23:30:08 +08:00
写个返回 time 距今几个 12 月的函数，stream 流用该函数分组，再用 treemap 搜集。
|
|
13
unregister OP @zmal 能不能利用分治的思想。。先给时间排序，然后取中间值，递归下去这样。除了临界点算一下年份之外，其他的 item 都不计算直接存放到数组里面。
|
|
14
JasonLaw 2022-08-18 23:37:53 +08:00 via iPhone
@unregister #11 其实你说的这些在时间复杂度上面没有多大区别，都是θ(len(times))，因为每次循环最后运算 6 次，我说的方法就是把 6 次变为 1 次。
|
|
15
zmal 2022-08-18 23:39:14 +08:00
一次遍历的时间复杂度是 N 。
排序的时间复杂度是 N*logN ，排序再二分还得*logN ，你咋想的大兄弟。 |
|
16
JasonLaw 2022-08-18 23:42:55 +08:00 via iPhone
@unregister #13 将 times 进行排序就需要θ(nlgn)了🤕。我很想知道你是怎么做到“ 除了临界点算一下年份之外，其他的 item 都不计算直接存放到数组里面”的，写一下代码或伪代码让我看一下，我真的很想知道。
|
|
17
zmal 2022-08-18 23:52:06 +08:00 1
我明白你的意思了，你是觉得你的一坨 if else 代码需要比较 6 次有多余耗时？其实优化成 除 12 再分组就可以了。
而且计算时间复杂度时常数的部分可以忽略。而且大于小于这种计算在这个场景里的时间消耗可以忽略不计。 |
|
18
unregister OP |
|
19
unregister OP @zmal 嗯嗯好的，我在去测试一下。
|
|
20
JasonLaw 2022-08-19 08:17:15 +08:00 via iPhone
@zmal #12 不太懂为什么要用 tree map ，OP 的源代码应该没这样的需求，更重要的是，涉及到排序的话，时间复杂度就是 O(nlgn)了，而且 hash table 会用到更多的 memory ，计算 index 也会更加耗时。如果我说错的话，欢迎指出。
|
|
21
JasonLaw 2022-08-19 08:22:16 +08:00 via iPhone
@unregister #18 我不是大佬，我还是在一直学习。如果你想要更加理解代码的话，真的建议你学习一下算法和数据结构，https://neetcode.io/是个好地方，我也在使用这个网站，大家一起进步。
|
 |
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 } |
|
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 只是用来把年份做个排序，遍历的时候方便。不用也可以。 |
 |
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 切出来放进不同数组就行了。 |
|
28
unregister OP |
Select Language