algorithm - 使用函数式编程 (F#) 将位置列表转换为二维位置数组

Question

如何使以下代码以相同的速度运行？通常，作为输入，我有一个包含位置坐标和其他内容的对象列表，我需要创建一个包含这些对象的二维数组。

let m = Matrix.Generic.create 6 6 []
let pos = [(1.3,4.3); (5.6,5.4); (1.5,4.8)]  
pos |> List.iter (fun (pz,py) ->
  let z, y = int pz, int py
  m.[z,y] <- (pz,py) :: m.[z,y]
)

大概可以这样实现:

let pos = [(1.3,4.3); (5.6,5.4); (1.5,4.8)]
Matrix.generic.init 6 6 (fun z y ->
  pos |> List.fold (fun state (pz,py) ->
    let iz, iy = int pz, int py
    if iz = z && iy = y then (pz,py) :: state else state
  ) []
)

但我猜它会慢得多，因为它循环遍历整个矩阵乘以列表与前一个列表迭代...

PS:代码可能有误，因为我这台电脑上没有F#来检查它。

Answer 1

这取决于“功能性”的定义。我会说“功能性”函数意味着它总是为相同的参数返回相同的结果，并且它不会修改任何全局状态(或者参数的值，如果它们是可变的)。我认为这是对 F# 的合理定义，但它也意味着在本地使用突变不会“破坏功能”。

在我看来，以下函数是“函数式”的，因为它创建并返回一个新矩阵而不是修改现有矩阵，但是当然，该函数的实现使用了变异。

let performStep m =
  let res = Matrix.Generic.create 6 6 [] 
  let pos = [(1.3,4.3); (5.6,5.4); (1.5,4.8)]   
  for pz, py in pos do
    let z, y = int pz, int py 
    res.[z,y] <- (pz,py) :: m.[z,y] 
  res

无突变版本:现在，如果你想让实现功能齐全，那么我会首先创建一个矩阵，在你想要将新列表元素添加到元素的地方包含 Some(pz, py)矩阵和 None 在所有其他地方。我想这可以通过初始化稀疏矩阵来完成。像这样:

let sp = pos |> List.map (fun (pz, py) -> int pz, int py, (pz, py)) 
let elementsToAdd = Matrix.Generic.initSparse 6 6 sp

然后您应该能够将原始矩阵 m 与新创建的 elementsToAdd 组合起来。这当然可以使用 init 来完成(但是，使用 map2 之类的东西可能会更好):

let res = Matrix.init 6 6 (fun i j -> 
  match elementsToAdd.[i, j], m.[i, j] with
  | Some(n), res -> n::res
  | _, res -> res )

F# 库函数(例如 init 和 initSparse)中仍然很可能隐藏了一些突变，但至少它展示了一种使用以下方法实现操作的方法更原始的操作。

编辑:仅当您最多需要向每个矩阵单元格添加单个元素时，此方法才有效。如果你想添加多个元素，你必须先将它们分组(例如使用 Seq.groupBy)