用於將散列合併爲稀疏矩陣的高效算法

我有不規則間隔的時間數據，我需要將其轉換爲稀疏矩陣以便與圖形庫一起使用。用於將散列合併爲稀疏矩陣的高效算法

的數據目前是採用以下格式：

{ 
    :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], 
    ... 
}

這裏每一行代表一個我有條目的時間點。每列表示一個系列（線圖上的一條線）。這就是爲什麼用零表示缺失值非常重要。

我有一些非常慢的實現，但這似乎是一個問題，之前已經解決，所以我希望有一個更有效的方法來做到這一點。

來源

2012-02-20 Greg Guida

輸出中的時間戳是否需要按順序排列？ – 2012-02-20 12:02:23

@NickBarnes是的，我最終需要它們，但我可以在合併後對它們進行排序。 – 2012-02-20 18:01:23

任何種類的東西都會打擊你的O（n）要求。但是，假設這不是問題，我很難想象如何創建比O（n）更慢的未排序版本......您能否提供一些關於您目前的解決方案的信息，所以我們知道我們打算打敗？ – 2012-02-20 20:19:30

我對你的要求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）。

來源

2012-02-20 11:56:56 DarkOtter

怎麼是這樣的：

num = series.count 
timestamps = {} 
series.each_with_index do |(k, entries), i| 
    entries.each do |entry| 
    timestamps[entry.timestamp] ||= Array.new(num) 
    timestamps[entry.timestamp][i] = entry.value 
    end 
end

不知道雖然你一系列的初始排序，我猜你的真實情況比較複雜一點比問題提出的。

來源

2012-02-20 12:00:01

用於將散列合併爲稀疏矩陣的高效算法

回答

相關問題