ruby - 将哈希合并为稀疏矩阵的高效算法

Question

我有不规则间隔的时间数据，我需要将其转换为稀疏矩阵以便与图形库一起使用。

数据目前采用以下格式:

{
  :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 表示缺失值非常重要。

我有一些非常慢的实现，但这似乎是一个以前已经解决的问题，所以我希望有一种更有效的方法来做到这一点。

Answer 1

我对你要求的 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)。