The data structure with the fastest element lookup in F#?

Question

I'm trying to code a small F# linear algebra library (for applications with small matrices, so memory isn't an issue), and I was wondering which data structure had the best performance characteristics, in terms of element lookup times, since I'll need that to define matrix operations?

Answer 1

The most efficient representation is probably going to be a mutable array (two-dimensional should work pretty well). The lookup by index is O(1), so that's as efficient as it can get. Even though the array is mutable, you can still use it to develop a immutable (functional) matrix type - all you need to do is to avoid mutating the array. The compiler will not check this, but the data structure can be purely functional for the user.

Something like this could be a good starting point:

// 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)

Answer 2

I'm a little unclear what's being asked.

Arrays are of course O(1), and so I expect they're the right answer. (Brian's rule of thumb: if you want something to be fast, then the answer is the same in every language - use an array of structs.)

If you need something sparser, there's the .NET Dictionary and HashSet classes (which uses hashes), and the F# Map and Set types (which use trees/comparison). Dictionary is probably a next best try.

But of course I expect either this depends a whole lot on the specifics (density, locality/access pattern, ...) or it does not matter at all (other factors overwhelm it).

At the end of day, like for every performance question: measure.

Answer 3

If "small" is 2- or 3-dimensional then structs. For slightly larger "small", use a reference type with explicit components. If the number of elements is more than about 30 then use a single array and do i + n*j yourself. Avoid .NET's 2D arrays because they are several times slower than necessary. Really avoid F#'s Matrix type for element-wise operations because it does something insane like dynamic dispatch (an order of magnitude slower). Arrays of arrays are good but indexing yourself permits more JIT optimizations of the indexing.