查找重叠值的时间总和

Question

几天来,我一直在努力解决这个问题.我有一台可能有错误的机器.在数据库中,我有错误出现时的开始和结束时间(在unix时间),以及错误类型(数字从5到12).我遇到的问题是多个错误可能同时发生(和重叠).

我的表看起来像这样:

   id| type | from       | to
    1| 6    | 1417179933 | 1417180006
    2| 6    | 1417180035 | 1417180065
    3| 9    | 1417180304 | 1417180409
    4| 6    | 1417180662 | 1417184364
    5| 8    | 1417180662 | 1417186832
    6| 9    | 1417180662 | 1417184364
    7| 12   | 1417180662 | 1417184364
    8| 6    | 1417184364 | 1417186832
    9| 9    | 1417184364 | 1417188054

我需要找到这台机器的总错误持续时间.我无法总结上表中的所有差异,因为在同一时间间隔内可能出现两个或更多错误.记录按升序排序.

我的猜测是将每个记录(开始和结束时间)与之前进行比较,然后找出以秒为单位的差异.但是,此表可能会随着时间的推移而增长,搜索它是一个问题.

有没有一种聪明的方法在PHP或MySQL中找到机器不工作的总时间,可能在几分钟内？

Answer 1

这是考虑潜在重叠的对间隔求和的通用方法，假设间隔按较低值排序。

2 间隔情况

当添加两个间隔[a,b]和[c,d]时，(d-c) + (b-a)您将计算它们的重叠两次。

• 如果重叠不为零，则其值为min(b,d) - max(a,c)。由于您在间隔开始时对项目进行了排序，因此您知道max(a,c) == c。

• 如果重叠为 0，a <= b <= c <= d则min(b,d) == b、max(a,c) == c、 和min(b,d) - max(a,c) == b - c <= 0。然而你却想删除0。

因此一个通用公式是d-c + b-a - max(0,min(b,d)-c)

推广到更多区间

要推广到两个以上的间隔，只需考虑当您将新间隔添加[c,d]到任意数量的先前间隔时，您会添加(d-c)并且计算两次的重叠位于[c,d]所有先前间隔的并集之间。

由于您根据间隔的起始值对间隔进行排序，因此您只需考虑该并集的最后一个连续间隔，即最后一个连续的停机时间段。

如果[a,b]是您之前的最后一个连续间隔并且您刚刚添加了[c,d]：

• 如果[a,b]和[c,d]重叠，则您的最后一个连续间隔变为，因为这是和[a, max(b,d)]的并集[a,b][c,d]
• 如果[a,b]和[c,d]不重叠，则您的最后一个连续间隔变为[c, d]（注意：我们有max(b,d) == b）

由于a < c间隔已排序，因此间隔重叠 iffc < b

在代码中

这可能比 mysql 更容易在 php 中实现。在伪代码中，假设每一行返回一个（开始，结束）错误间隔，并且[a,b]是您最后一个已知的连续间隔：

(a,b) = get_first_row();
downtime = b-a;
while( (c,d) = get_next_row() )
{
     downtime += d-c - max(0, min(d,b)-c);
     a = c < b ? a : c;
     b = max(b,d);
}

您可以在此处看到此代码成功运行： https: //3v4l.org/Q2phs