在集合中查找相同值的块并操作周围的值

Question

我真的不知道如何总结标题中的问题，抱歉。:)

假设我有一个包含数千个对象的集合(即ObservableCollection)。这些对象由升序时间戳和FALSE布尔值(非常简化)组成。

:

[0] 0.01, FALSE
[1] 0.02, FALSE
[2] 0.03, FALSE
[3] 0.04, FALSE
...

现在，让我们假设在这个集合中，有一些块的标志设置为TRUE。

:

[2345] 23.46, FALSE
[2346] 23.47, FALSE
[2347] 23.48, FALSE
[2348] 23.49, TRUE
[2349] 23.50, TRUE
[2350] 23.51, TRUE
[2351] 23.52, TRUE
[2352] 23.53, TRUE
[2353] 23.54, FALSE
[2354] 23.55, FALSE
...

我需要找到块并在块之前和之后的1.5秒内将所有标志设置为TRUE。如何在保持合理性能的同时实现这一点?

Answer 1

Matthias G解是正确的，尽管相当慢-似乎有n平方的复杂度。

第一个算法扫描输入values，通过IsActive过滤它们，检索时间戳并放入一个新列表—这至少是O(n)。然后它扫描构造的列表，在最坏的情况下可能是整个输入- O(n)，并且对于检索到的每个时间戳，它扫描输入values以修改其中的适当值- O(n^2)。然后，它建立一个额外的列表，只是扫描一次，销毁。

我会提出一个类似于合并排序的解决方案。首先扫描输入值，并为每个Active项将适当的时间间隔推入队列。您可以延迟推，看看下一个间隔是否与当前的重叠-然后延长间隔，而不是推。当输入列表完成后，最后推送最后一个延迟间隔。这样，您的队列将包含您想要修改的(几乎)最小数量的时间间隔。

然后再次扫描values数据并将时间戳与队列中的第一个间隔进行比较。如果项目的时间戳落在当前间隔内，则将项目标记为Active。如果超过了间隔，则从队列中删除该间隔，并将该时间戳与下一个时间戳进行比较——以此类推，直到项目在该间隔内或之前。您输入的数据是按时间顺序排列的，因此间隔也将按相同的顺序排列。这允许在单个并行遍历两个列表中完成任务。

Answer 2

假设您有一个这样的数据结构:

Edit: Changed TimeStamp to double

public class Value
{
    public double TimeStamp { get; set; }
    public bool IsActive { get; set; }
}

这个对象的列表叫做values。然后，您可以搜索活动数据集，并将它们周围范围内的值标记为活动:

double range = 1.5;
var activeTimeStamps = values.Where(value => value.IsActive)
                             .Select(value => value.TimeStamp)
                             .ToList();
foreach (var timeStamp in activeTimeStamps)
{
    var valuesToMakeActive =
        values.Where
            (
                value =>
                    value.TimeStamp >= timeStamp - range &&
                    value.TimeStamp <= timeStamp + range
            );
    foreach (var value in valuesToMakeActive)
    {
        value.IsActive = true;
    }
}

无论如何，我想一定会有更好的解决方案的。