时间范围内任何事件的最大发生次数 [英] Maximum occurrence of any event in time range

问题描述

我有收集时间戳记，例如 10：18：07.490,11：50：18.251 ，其中第一个是事件的开始时间，第二个是事件的结束时间。我需要找到一个范围，在此范围内仅24小时就会发生最多的事件。这些事件的发生以毫秒为单位。

I have collection time stamps, e.g 10:18:07.490,11:50:18.251 where first is the start time and second is end time for an event. I need to find a range where maximum events are happening just 24 hours of time. These events are happening in precision of milliseconds.

我正在做的是将24小时划分为毫秒级，并每毫秒附加一次事件，然后查找

What I am doing is to divide 24 hours on millisecond scale, and attach events at every millisecond, and then finding a range where maximum events are happening.

LocalTime start = LocalTime.parse("00:00");
LocalTime end = LocalTime.parse("23:59");

for (LocalTime x = start; x.isBefore(end); x = x.plus(Duration.ofMillis(1))) {
        for (int i = 0; i < startTime.size(); i++) {
        if (startTime.get(i).isAfter(x) && endTime.get(i).isBefore(x))
            // add them to list;
        }

    }

当然，这不是一个好方法，这会占用太多内存。我如何以适当的方式做到这一点？有建议吗？

Certainly this is not a good approach, it takes too much memory. How I can do it in a proper way? Any suggestion?

推荐答案

找到最大并发事件的第一期的解决方案：

如果您愿意使用第三方库，则可以使用jOOλ的窗口功能。这个想法与阿米特的答案中的解释相同：

A solution finding the first period of maximum concurrent events:

If you're willing to use a third party library, this can be implemented "relatively easy" in a SQL style with jOOλ's window functions. The idea is the same as explained in amit's answer:

System.out.println(
    Seq.of(tuple(LocalTime.parse("10:18:07.490"), LocalTime.parse("11:50:18.251")),
           tuple(LocalTime.parse("09:37:03.100"), LocalTime.parse("16:57:13.938")),
           tuple(LocalTime.parse("08:15:11.201"), LocalTime.parse("10:33:17.019")),
           tuple(LocalTime.parse("10:37:03.100"), LocalTime.parse("11:00:15.123")),
           tuple(LocalTime.parse("11:20:55.037"), LocalTime.parse("14:37:25.188")),
           tuple(LocalTime.parse("12:15:00.000"), LocalTime.parse("14:13:11.456")))
       .flatMap(t -> Seq.of(tuple(t.v1, 1), tuple(t.v2, -1)))
       .sorted(Comparator.comparing(t -> t.v1))
       .window(Long.MIN_VALUE, 0)
       .map(w -> tuple(
           w.value().v1,
           w.lead().map(t -> t.v1).orElse(null),
           w.sum(t -> t.v2).orElse(0)))
       .maxBy(t -> t.v3)
);

上面的照片：

Optional[(10:18:07.490, 10:33:17.019, 3)]

因此，在10:18 ...和10:33 ...之间的时间段内，发生了3个事件，这是一天中任何时间重叠的事件最多。

So, during the period between 10:18... and 10:33..., there had been 3 events, which is the most number of events that overlap at any time during the day.

请注意，在多个时段中，​​样本数据中有3个并发事件。 maxBy（）仅返回第一个此类期间。为了返回所有这些期间，请使用 maxAllBy（）（添加到jOOλ0.9.11中）：

Note that there are several periods when there are 3 concurrent events in the sample data. maxBy() returns only the first such period. In order to return all such periods, use maxAllBy() instead (added to jOOλ 0.9.11):

   .maxAllBy(t -> t.v3)
   .toList()

然后屈服：

[(10:18:07.490, 10:33:17.019, 3), 
 (10:37:03.100, 11:00:15.123, 3), 
 (11:20:55.037, 11:50:18.251, 3), 
 (12:15       , 14:13:11.456, 3)]

或者图形表示形式

Or, a graphical representation

3                  /-----\       /-----\       /-----\       /-----\
2           /-----/       \-----/       \-----/       \-----/       \-----\
1     -----/                                                               \-----\
0                                                                                 \--
   08:15  09:37  10:18  10:33  10:37  11:00  11:20  11:50  12:15  14:13  14:37  16:57

说明：

这里是原始原始解决方案再次加上注释：

Explanations:

Here's the original solution again with comments:

// This is your input data    
Seq.of(tuple(LocalTime.parse("10:18:07.490"), LocalTime.parse("11:50:18.251")),
       tuple(LocalTime.parse("09:37:03.100"), LocalTime.parse("16:57:13.938")),
       tuple(LocalTime.parse("08:15:11.201"), LocalTime.parse("10:33:17.019")),
       tuple(LocalTime.parse("10:37:03.100"), LocalTime.parse("11:00:15.123")),
       tuple(LocalTime.parse("11:20:55.037"), LocalTime.parse("14:37:25.188")),
       tuple(LocalTime.parse("12:15:00.000"), LocalTime.parse("14:13:11.456")))

   // Flatten "start" and "end" times into a single sequence, with start times being
   // accompanied by a "+1" event, and end times by a "-1" event, which can then be summed
   .flatMap(t -> Seq.of(tuple(t.v1, 1), tuple(t.v2, -1)))

   // Sort the "start" and "end" times according to the time
   .sorted(Comparator.comparing(t -> t.v1))

   // Create a "window" between the first time and the current time in the sequence
   .window(Long.MIN_VALUE, 0)

   // Map each time value to a tuple containing
   // (1) the time value itself
   // (2) the subsequent time value (lead)
   // (3) the "running total" of the +1 / -1 values
   .map(w -> tuple(
       w.value().v1,
       w.lead().map(t -> t.v1).orElse(null),
       w.sum(t -> t.v2).orElse(0)))

   // Now, find the tuple that has the maximum "running total" value
   .maxBy(t -> t.v3)

我写了更多有关窗口功能以及如何实现

I have written up more about window functions and how to implement them in Java in this blog post.

（免责声明：我为jOOλ背后的公司工作）

(disclaimer: I work for the company behind jOOλ)

这篇关于时间范围内任何事件的最大发生次数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！