在F#中有效地投射列表列表

Question

我必须对列表列表进行投影,这些列表返回每个列表中每个元素的所有组合.例如:

projection([[1]; [2; 3]]) = [[1; 2]; [1; 3]].
projection([[1]; [2; 3]; [4; 5]]) = [[1; 2; 4]; [1; 2; 5]; [1; 3; 4]; [1; 3; 5]].

我想出了一个功能:

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)

和一个测试用例:

#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;;

该功能现在非常慢,N = 10完成时间超过10秒.此外,我认为解决方案不自然,因为我必须以两种不同的方式细分相同的列表.有什么建议我如何提高功能的性能和可读性？

Answer 1

首先,尽可能避免列表连接(@),因为它是O(N)而不是O(1)前置.

我从一个(相对)容易遵循的计划开始,如何计算列表的笛卡尔外积.

• 将第一个列表的每个元素添加到剩余列表的笛卡尔积中的每个子列表中.
• 照顾基础案例.

第一版:

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

这是将上述句子直接翻译成代码.

现在加快速度:使用列表连接和映射代替列表推导:

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

通过序列按需计算列表,可以更快地完成此操作:

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

最后一种形式是我自己使用的形式,因为我通常只需要迭代结果而不是一次性全部.

我机器上的一些基准测试:测试代码:

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

结果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

Answer 2

这个函数是Haskell的序列(虽然sequence更通用).转换为F#:

let sequence lss =
    let k l ls = [ for x in l do for xs in ls -> x::xs ]
    List.foldBack k lss [[]]

在互动中:

> test projection 10;;
Real: 00:00:12.240, CPU: 00:00:12.807, GC gen0: 163, gen1: 155, gen2: 4
val it : int = 3628800
> test sequence 10;;
Real: 00:00:06.038, CPU: 00:00:06.021, GC gen0: 75, gen1: 74, gen2: 0
val it : int = 3628800

一般想法:避免显式递归,有利于标准组合器(折叠,映射等)