Projecting a list of lists efficiently in F#

by

First of all, try to avoid list concatenation (@) whenever possible, since it’s O(N) instead of O(1) prepend.

I’d start with a (relatively) easy to follow plan of how to compute the cartesian outer product of lists.

  • Prepend each element of the first list to each sublist in the cartesian product of the remaining lists.
  • Take care of the base case.

First version:

let rec cartesian = function
  | [] -> [[]]
  | L::Ls -> [for C in cartesian Ls do yield! [for x in L do yield x::C]]

This is the direct translation of the sentences above to code.

Now speed this up: instead of list comprehensions, use list concatenations and maps:

let rec cartesian2 = function
  | [] -> [[]]
  | L::Ls -> cartesian2 Ls |> List.collect (fun C -> L |> List.map (fun x->x::C))

This can be made faster still by computing the lists on demand via a sequence:

let rec cartesian3 = function
  | [] -> Seq.singleton []
  | L::Ls -> cartesian3 Ls |> Seq.collect (fun C -> L |> Seq.map (fun x->x::C))

This last form is what I use myself, since I most often just need to iterate over the results instead of having them all at once.

Some benchmarks on my machine:
Test code:

let test f N = 
  let fss0 = List.init N (fun i -> List.init (i+1) (fun j -> j+i*i+i))
  f fss0 |> Seq.length

Results in FSI:

> test projection 10;;
Real: 00:00:18.066, CPU: 00:00:18.062, GC gen0: 168, gen1: 157, gen2: 7
val it : int = 3628800
> test cartesian 10;;
Real: 00:00:19.822, CPU: 00:00:19.828, GC gen0: 244, gen1: 121, gen2: 3
val it : int = 3628800
> test cartesian2 10;;
Real: 00:00:09.247, CPU: 00:00:09.250, GC gen0: 94, gen1: 52, gen2: 2
val it : int = 3628800
> test cartesian3 10;;
Real: 00:00:04.254, CPU: 00:00:04.250, GC gen0: 359, gen1: 1, gen2: 0
val it : int = 3628800

More Related Contents:

  1. Why are difference lists more efficient than regular concatenation in Haskell?
  2. preallocate list in R
  3. High-performance merging of ordered sets
  4. Fastest way to check if a value exists in a list
  5. Google app script timeout ~ 5 minutes?
  6. What is the purpose of the EBP frame pointer register?
  7. Algorithm to calculate the number of divisors of a given number
  8. Analyzing Code for Efficiency?
  9. Apache Spark: map vs mapPartitions?
  10. Reading GHC Core
  11. CSS3 Transitions: Is “transition: all” slower than “transition: x”?
  12. Size of store buffers on Intel hardware? What exactly is a store buffer?
  13. Avoid stalling pipeline by calculating conditional early
  14. Append an object to a list in R in amortized constant time, O(1)?
  15. Android studio takes too much memory
  16. What is the fastest way to get the value of π?
  17. Most efficient list to data.frame method?
  18. Tools to measure MPI communication costs [closed]
  19. Has anyone actually implemented a Fibonacci-Heap efficiently?
  20. Entity Framework query slow, but same SQL in SqlQuery is fast
  21. Order of the code and performance
  22. latency vs throughput in intel intrinsics
  23. Is there a way to circumvent Python list.append() becoming progressively slower in a loop as the list grows?
  24. Python List Indexing Efficiency
  25. Linked list partition function and reversed results
  26. how do numactl & perf change memory placement policy of child processes?
  27. What’s a fast way to space-out bits within a word?
  28. Length of longest word in a list
  29. How to analyze golang memory?
  30. How to avoid Query Plan re-compilation when using IEnumerable.Contains in Entity Framework LINQ queries?

Leave a Comment