Select some indexes in a list of lists

Question

I have a record type which holds a list of table rows. Each row is also a list. The first row is assumed to be the header row. In addition the type optionally defines a filter - a list of columns (the actual string value of the column header).

Then the type have a member property FilteredRows. If no filter is defined, the property is the entire table. But if there is a filter, FilteredRows return the list of rows, but only with the columns defined by the filter.

I'm not interested in alternative ways to represent this. This is part of a bigger solution, it's working, and the design makes sense to me. What I believe I need however is some more eyes on the internals of FilteredRows. I'm looking for clever tricks on solving this problem in different ways, and other pointers on how I can improve the solution.

type Table = 
    {
        Rows : string list list
        OnlyColumns : string list option
    } 
    member internal x.FilteredRows =
        match x.OnlyColumns with
        | None -> x.Rows
        | Some xs -> 
            let indexesToInclude = seq {
                let headers = List.head x.Rows
                for c in xs do
                    yield List.findIndex ((=) c) headers }
            x.Rows
            |> List.map
                (fun row ->
                    indexesToInclude
                    |> Seq.map (List.nth row)
                    |> List.ofSeq )

As you can see, what I've done is first to fetch all the column indexes using List.findIndex. And then for each row I map over the column indices and re-create the row using List.nth.

Answer 1

The only real change that pops out at me without touching the record datatypes is to make indexesToInclude an array, you're evaluating it over and over again in that seq comprehension each time. Since it's an array and lookups are fast, and you know its size, you might as well pre-allocate it instead of using a comprehension which will be much faster. Then do a mapi over the rows, and just look up if you want that index in the array.

type Table = 
    {
        Rows : string list list
        OnlyColumns : string list option
    } 
    member internal x.FilteredRows =
        match x.OnlyColumns with
        | None -> x.Rows
        | Some xs -> 
            let headers = List.head x.Rows |> List.toArray
            let isIncluded = Array.init (headers.Length) (fun hi -> xs |> List.exists (fun lv -> lv = headers.[hi]))
            x.Rows
            |> List.map (fun row -> row |> List.mapi (fun i v ->  (isIncluded.[i], v))
                                        |> List.filter fst |> List.map snd)

The most important thing here is that we're no longer indexing into a list (almost always a bad idea in F#), which costs O(n) where n is the index you're indexing into. If you do this every time it gets very expensive!

Answer 2

type Table = 
{
    Rows : string list list
    OnlyColumns : string list option
} 
member internal this.FilteredRows =
    match this.OnlyColumns with 
    | None -> this.Rows
    | Some columns -> 
        let indexOfColumn name = this.Rows |> List.head |> List.findIndex(fun x -> x = name)
        let selectors = columns |> List.map (fun column -> let ci = indexOfColumn column in (fun (row : string list) -> row.[ci]))
        let projectRow row = selectors |> List.map (fun f -> (f row))
        this.Rows |> List.map (fun row -> row |> projectRow)

Consider these performance characteristics:

• indexOfColumn is run once per included column, which will be O(n^2) for linear search over the list of columns, which is hopefully small in comparison to number of rows
• selectors are functions to take a whole row to a selected column by index - if index lookup on a list is constant time, then a selector will run in constant time
• the projectRow function projects a whole row to the set of selected columns. This can be parallelized if required, but it will run in O(n) where n is the number of included columns
• projectRow is called exactly once per row in the list