I have to do projection of a list of lists which returns all combinations with each element from each list. For example:
projection([; [2; 3]]) = [[1; 2]; [1; 3]]. projection([; [2; 3]; [4; 5]]) = [[1; 2; 4]; [1; 2; 5]; [1; 3; 4]; [1; 3; 5]].
I come up with a function:
let projection lss0 = let rec projectionUtil lss accs = match lss with |  -> accs | ls::lss' -> projectionUtil lss' (List.fold (fun accs' l -> accs' @ List.map (fun acc -> acc @ [l]) accs)  ls) match lss0 with |  ->  | ls::lss' -> projectionUtil lss' (List.map (fun l -> [l]) ls)
and a testcase:
#time "on";; let N = 10 let fss0 = List.init N (fun i -> List.init (i+1) (fun j -> j+i*i+i));; let fss1 = projection fss0;;
The function is quite slow now, with
N = 10 it takes more than 10 seconds to complete. Moreover, I think the solution is unnatural because I have to breakdown the same list in two different ways. Any suggestion how I can improve performance and readability of the function?
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.
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:
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
Answered By – cfern
Answer Checked By – Jay B. (BugsFixing Admin)