我有不规则间隔的时间数据,我需要将其转换为稀疏矩阵以便与图形库一起使用。
数据目前采用以下格式:
{
:series1 => [entry, entry, entry, entry, ...],
:series2 => [entry, entry, entry, entry, ...]
}
其中 entry
是一个具有两个属性的对象,timestamp
(一个 unix 时间戳)和 value
(一个整数)
我需要在尽可能接近 O(n) 的时间内将其放入这种格式。
{
timestamp1 => [ value, value, nil ],
timestamp2 => [ value, nil, value ],
timestamp3 => [ value, value, value],
...
}
这里每一行代表一个时间点,我有一个条目。每列代表一个系列(折线图上的一条线)。这就是为什么用 nil 表示缺失值非常重要。
我有一些非常慢的实现,但这似乎是一个以前已经解决的问题,所以我希望有一种更有效的方法来做到这一点。
最佳答案
我对你要求的 O(n) 有点困惑,所以请随时纠正我,但据我所知,O(n) 很容易实现。
首先找到起始散列的长度(数据中的系列数)。这应该是 O(1),但不比 O(S) 差(其中 S 不是系列),并且 S <= O(n)(假设没有没有值的系列)所以仍然是 O(n)。
将此长度存储在某处,然后为稀疏矩阵设置哈希,以自动将任何行初始化为此大小的空数组。
matrix = Hash.new {|hsh,k| hsh[k] = Array.new(S)}
然后简单地按索引浏览每个系列。对于每个条目,将数组中适当的单元格设置为正确的值。
对于每个条目,在哈希中查找时间戳的时间复杂度为 O(1)(平均),然后在数组中设置单元格的时间复杂度为 O(1)。这发生了 n 次,给了你 O(n)。
还将为矩阵中的每一行创建一个数组。据我所知,这是一个数组的 O(1),所以总体来说是 O(T)(其中 T 是时间戳的数量)。由于我们不会在没有带有该时间戳的条目的地方创建空行,因此 T 必须 <= n,所以这也是 O(n)。
所以总的来说我们有 O(n) + O(n) + O(n) = O(n)。在 Ruby 中可能有一些方法可以加快速度,但据我所知,这不仅接近,而且实际上是 O(n)。
关于ruby - 将哈希合并为稀疏矩阵的高效算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9357860/