F＃中查詢速度最快的數據結構？

我想編寫一個小的F＃線性代數庫（對於具有小矩陣的應用程序，因此內存不是問題），並且我想知道哪個數據結構在元素查找時間方面具有最佳性能特徵，因爲我需要那個來定義矩陣操作？F＃中查詢速度最快的數據結構？

2010-09-03 Alexander

如果「小」是2-或3-維然後結構。對於稍大的「小」，請使用帶有明確組件的引用類型。如果元素的數量超過大約30個，則使用單個陣列並自己執行i + n*j。避免使用.NET的2D數組，因爲它們比必要的慢幾倍。真的避免F＃的Matrix類型的元素明智的操作，因爲它做一些瘋狂的動態調度（一個數量級慢）。數組的數組是很好的，但索引自己可以進行更多的JIT索引優化。

來源

2010-09-03 16:30:30

簡而言之。不錯，但我會回來參考:) – Alexander 2010-09-03 17:31:35

最有效的表示形式可能是一個可變數組（二維應該工作得很好）。索引查找是O（1），因此它的效率可以達到。即使數組是可變的，你仍然可以用它來開發一個不可變的（功能性）矩陣類型 - 你需要做的就是避免改變數組。編譯器不會檢查這一點，但數據結構對用戶來說可能是純粹的功能。

像這樣的東西可能是一個很好的起點：

// Constructor takes the data of the matrix 
type Matrix(data:float[,]) = 
    // Expose data only for private purposes (cannot be mutated by the user!) 
    member private x.Data = data 
    // All operations create new array as the result 
    static member (+) (a:Matrix, b:Matrix) = 
    // TODO: Check that arrays have the same size 
    let res = Array2D.init (a.Data.GetLength(0)) (a.Data.GetLength(1)) 
     (fun i j -> a.Data.[i, j] + a.Data.[i, j]) 
    new Matrix<_>(res)

來源

2010-09-03 15:45:03

據我所知，在.NET中，多維數組明顯比一維數組慢，這是需要記住的。 – kvb 2010-09-03 16:10:56

@kvb：有趣。我不知道 - 你有什麼參考？這是否適用於矩形二維數組和「陣列」？ – 2010-09-03 16:20:03

我認爲參差不齊的數組（即數組數組）是合理的高性能。但是，真正的多維數組並沒有得到很好的優化。我手邊沒有很好的參考資料，但請參閱http://stackoverflow.com/questions/468832/why-are-multi-dimensional-arrays-in-net-slower-than-normal-arrays。 – kvb 2010-09-03 17:18:36

我有點不清楚對方的問題。

陣列當然是O（1），所以我期望他們是正確的答案。（經驗Brian的規則：如果你想要的東西要快，那麼答案是每一種語言一樣 - 使用結構數組）。

如果你需要的東西稀疏，還有的.NET Dictionary和HashSet類（它使用散列）以及F＃Map和Set類型（使用樹/比較）。 Dictionary可能是下一個最好的嘗試。當然我期望這要麼取決於具體細節（密度，位置/訪問模式，......）或者根本不重要（其他因素壓倒它）。

在一天結束時，像每個表現問題：措施。

來源

2010-09-03 15:47:12 Brian

由於*布萊恩的經驗法則*我投了贊成票。當我達到最後的時候，我想提高**度量**。優秀的答案。 – 2010-09-03 16:06:22

我同意;高效代碼的三個基本要素是：基準，基準，基準。 – TechNeilogy 2010-09-03 17:28:31

F＃中查詢速度最快的數據結構？

回答

相關問題