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＃中查询速度最快的数据结构？

回答

相关问题