这个问题不是特定于语言的。
假设我有 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)]
最佳答案
如果您有一种有用的数据结构,这很容易。
该数据结构是一个优先级队列。您将事物放入优先级队列中,然后它们按优先级顺序出现。所以我们可以将我们的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))
。 (第一项是为答案创建新条目,第二项是处理每个时间序列条目。)
关于algorithm - 算法问题 : iterating over multiple time series "as of",我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57280653/