c# - 在集合中查找具有相同值的 block 并操作周围的值

Question

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

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

像这样:

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

现在，我们假设在此集合中，有一些 block 的标志设置为 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
...

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

Answer 1

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

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

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

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