algorithm - 算法问题 : iterating over multiple time series "as of"

Question

这个问题不是特定于语言的。

假设我有 N 个名为 S_1、S_2、... S_N 的时间序列。我所说的时间序列是指(示意性地)

struct timeseries{T}
    values::Vector{T}
    timestamps::Vector{Timestamp}
end

其中两个向量对于每个时间序列具有相同的长度。

您不能假设时间序列具有相同数量的元素。对于一天的数据，一些时间序列可能有数百万个元素，而其他时间序列可能有几个元素，但您可以假设它们都同时适合内存。您可以假设所有时间序列都按时间戳排序。

我想获得另一个时间序列:

• 具有与 N 个时间序列的时间戳的并集一样多的时间戳
• 对于每个时间戳 t，它的值是 N 个时间序列的值的元组，时间小于或等于 t，当它们存在且 NaN 否则

例如，假设我们有两个时间序列，我将其表示为元组列表 (timestamp,values):

S_1 = [(1,43),(4,20),(5,21),(10,10)]
S_2 = [(2,31),(4,-5),(6,-1),(11,100)]

结果是:

[(1,43,NaN),(2,43,31),(4,20,-5),(5,21,-5),(6,21,-1),(10,10,-1),(11,10,100)]

Answer 1

如果您有一种有用的数据结构，这很容易。

该数据结构是一个优先级队列。您将事物放入优先级队列中，然后它们按优先级顺序出现。所以我们可以将我们的n时间序列变成n元组(timestamp, queue, position, timeseries)。它们将首先按 timestamp 排序，然后按 queue 排序。没有其他联系。

对于使用堆数据结构实现的优先级队列，插入是O(log(n))，移除头部是O(log(n))，仅仅读取头部是 O(1)。

现在我们有一个算法如下:

# Initialize
Take our n timeseries, make n tuples (timestamp, queue, 0, timeseries)
Put the tuples into a priority queue
set last_timestamp = the timestamp of the first element in the queue.
set answer = [[last_timestamp, NaN, NaN, ..., NaN]]
set current_vector = answer[0]

# Work
while priority queue is not empty:
    (timestamp, queue, position, timeseries) = pop off of queue
    if timestamp = last_timestamp:
        current_vector = copy of current_vector
        current_vector[0] = timestamp
        answer.append(current_vector)
        last_timestamp = timestamp

    # Update for this record
    current_vector[queue] = timeseries[position][1]
    position = position + 1
    if position < len(timeseries):
        append to queue (timeseries[position][0], queue, position, timeseries)

如果您有 n 个时间序列、m 个时间戳和 k 个条目，则此算法将花费 O(n*m + k*log(n))。 (第一项是为答案创建新条目，第二项是处理每个时间序列条目。)