计算连续时间内发生次数的算法

Question

我有一组数据告诉我组件的 on/off 状态随时间的变化。数据如下所示：

第一列以秒为单位显示时间，第二列显示状态（1 为开启，0 为关闭）。

我需要知道其中最多 1 的 600 秒是多少秒。例如，0-600 有 3*120 秒，因此组件打开时为 360 秒。但是 120-720 有 4 等等...这意味着这不仅是 0-600、600-1200，它可以是任何 600 秒。困难的是这是一个循环，这意味着最坏的时间可能是从 1920 到 480（请注意，这个循环有 2040 秒，这意味着时间 2040 也是时间 0）。时间步长并不总是相等的。在这种情况下，它是一个恒定的 120 秒，但也可以是 120 秒和 150 秒的混合。

我唯一能想到的就是从0-600扫描文件，检查时间是否开启，120-720，240-840等...但是非常耗时。特别是因为我可以拥有非常大的文件。

该程序是用 Perl 编写的，但我只需要算法（如果存在）。你们中有人知道什么是最好的方法吗？

谢谢

Answer 1

问题可以通过以下方式解决。定义一个整数n；继续将 1 添加到 n 直到出现零。也就是说，如果出现零，则将 n 设置为零。在过程中记录最大n次出现和当时的秒数。为此，定义另一个变量 m 并让 m 为最大值。现在，如果 n 变得大于 m，则 m=n。通过这种方式，您可以接近包含最大数量 1 的 600 秒间隔。祝你好运。希望成功了。

Answer 2

假设点是按时间排序的，你可以保持连续点的缓冲区，使得第一个点和最后一个点之间的时间差不超过600。这是C#中的代码：

// Class for data point
class Point {
    public int Time { get; private set; }
    public bool On { get; private set; }

    public Point(int time, bool on) {
        Time = time;
        On = on;
    }
}

Point[] points = {
    new Point(0, true),
    new Point(120, true),
    new Point(240, false),
    new Point(360, false),
    new Point(480, true),
    new Point(600, true),
    new Point(720, true),
    new Point(840, false),
    new Point(960, false),
    new Point(1080, false),
    new Point(1200, true),
    new Point(1320, true),
    new Point(1440, false),
    new Point(1560, false),
    new Point(1680, true),
    new Point(1800, false),
    new Point(1920, true),
};

int GetMaxIntervalCount(IEnumerable<Point> points) {
    LinkedList<Point> buff = new LinkedList<Point>();
    int buffCount = 0, res = -1;
    foreach (Point point in points) {
        buff.AddFirst(point);
        while (buff.Count > 0) {
            Point last = buff.Last.Value;
            if (Math.Abs(last.Time - point.Time) > 600) {
                buff.RemoveLast();
                if (last.On) {
                    --buffCount;
                }
            } else {
                break;
            }
        }
        if (point.On) {
            ++buffCount;
        }
        res = Math.Max(res, buffCount);
    }
    return res;
}

目前它 returns 只是最大计数，但可以很容易地调整它以保持实际缓冲区。方法的时间复杂度为 O(N)（每个点将 "touched" 最多 2 次 - 在缓冲区中添加和删除）。

Answer 3

不太清楚您要计算的值是多少，但您的核心问题似乎是找到一种算法来在每个滑动 600 秒中获取样本 window。滑动window可以用数组来实现。将新样本添加到最后并清除旧样本以保持总大小 <= 600s。唯一棘手的部分是计算时间值以 2040 为模。

use strict;
use warnings;
use Data::Dump qw(pp);

my @window;
while (my $line = <DATA>) {
    chomp $line;
    my ($t, $on) = split / +/, $line;

    # add sample to sliding window
    push @window, { t => $t, on => $on};

    # limit window size to 600s
    while (1) {
        last if @window <= 1;

        my $start = $window[0]{t};
        my $stop  = $window[-1]{t};

        # account for time values being mod 2040
        if ($stop < $start) {
            $stop += 2040;
        }

        if ($stop - $start > 600) {
            # purge old sample from window
            shift @window;
        }
        else {
            last;
        }
    }

    # do something with @window
    pp \@window;
}

__DATA__
0    1
120  1
240  0
360  0
480  1
600  1
720  1
840  0
960  0
1080  0
1200  1
1320  1
1440  0
1560  0
1680  1
1800  0
1920  1
0    1
120  1
240  0
360  0

@window 中的值如下所示：

# no wrapping
[
  { on => 1, t => 0 },
  { on => 1, t => 120 },
  { on => 0, t => 240 },
  { on => 0, t => 360 },
  { on => 1, t => 480 },
  { on => 1, t => 600 },
]

# with wrapping
[
  { on => 0, t => 1560 },
  { on => 1, t => 1680 },
  { on => 0, t => 1800 },
  { on => 1, t => 1920 },
  { on => 1, t => 0 },
  { on => 1, t => 120 },
]

计算连续时间内发生次数的算法

Algorithm to count occurance in a consecutive amount of time

arrays

algorithm

perl

sorting

count