F#列表优化

Question

从一个无序的int列表中，我希望两个元素之间的差别最小。我有一个代码正在工作，但要慢下来。有人能提出一些改变来提高性能吗？请解释，为什么你做了这个改变，什么将是性能的提高。

let allInt = [ 5; 8; 9 ]

let sortedList = allInt |> List.sort;

let differenceList = [ for a in 0 .. N-2 do yield sortedList.Item a - sortedList.Item a + 1 ]

printfn "%i" (List.min differenceList) // print 1 (because 9-8 smallest difference)

我想我正在做很多列表创建或迭代，但我不知道如何用F#...yet编写不同的列表。

编辑：，我正在用10万项或更多的条目测试列表中的代码。

编辑2:，我相信如果我能一次计算出两者的差异，那么它应该能大大提高perf，但是我不知道怎么做，anay？

提前感谢

Answer 1

List.Item在O(n)时间内执行，可能是代码中的主要性能瓶颈。differenceList的计算通过索引迭代sortedList的元素，这意味着性能在O((N-2)(2(N2))附近)，从而简化为O(N^2)，其中N是sortedList中的元素数。对于较长的列表，这将最终表现糟糕。

我要做的是消除对Item的调用，而使用List.pairwise操作。

let data =
    [ let rnd = System.Random()
      for i in 1..100000 do yield rnd.Next() ]

#time

let result =
    data
    |> List.sort
    |> List.pairwise     // convert list from [a;b;c;...] to [(a,b); (b,c); ...]
    |> List.map (fun (a,b) -> a - b |> abs)  // Calculates the absolute difference
    |> List.min

#time

时间指令允许我在F#互动中测量执行时间，在运行这段代码时得到的输出是：

--> Timing now on

Real: 00:00:00.029, CPU: 00:00:00.031, GC gen0: 1, gen1: 1, gen2: 0
val result : int = 0

--> Timing now off

Answer 2

F#的内建列表类型被实现为一个链接列表，这意味着每次通过索引访问元素都必须枚举到索引。在您的例子中，有两个索引访问重复N-2次，每次迭代都会变得越来越慢，因为索引增长，每次访问都需要遍历列表的更长的部分。

第一种解决方法是使用数组而不是列表，这是一个简单的更改，但授予您更快的索引访问权限。

(*
    [| and |] let you define an array literal,
    alternatively use List.toArray allInt
*)
let allInt = [| 5; 8; 9 |] 
let sortedArray = allInt |> Array.sort;
let differenceList = [ for a in 0 .. N-2 do yield sortedArray.[a] - sortedArray.[a + 1] ]

另一种方法可能是将列表中的邻居配对，减去他们，然后找出一分钟。

let differenceList =
    sortedList
    |> List.pairwise
    |> List.map (fun (x,y) -> x - y)

List.pairwise获取元素列表并返回相邻对的列表。例如，在您的示例List.pairwise [ 5; 8; 9 ] = [ (5, 8); (8, 9) ]中，您可以轻松地在下一步减法映射中处理这两对。

这样做更好，但是List模块中的这些函数以list作为输入并生成一个新的列表作为输出，必须遍历列表3次(1次用于pairwise，1次用于map，1次用于min )。要解决这个问题，您可以使用来自Seq模块的函数，该模块与.NETs IEnumerable<'a>接口一起工作，从而允许延迟计算，通常导致的传递次数较少。

幸运的是，在本例中，Seq为我们在这里使用的所有函数定义了替代方案，因此下一步是微不足道的：

let differenceSeq =
    sortedList
    |> Seq.pairwise
    |> Seq.map (fun (x,y) -> x - y)

let minDiff = Seq.min differenceSeq

这应该只需要一个列表的枚举(当然不包括排序阶段)。

但我不能保证哪种方法会是最快的。我的赌注是简单地使用数组而不是列表，但要找出答案，你必须自己尝试和测量，在你的数据和硬件上。BehchmarkDotNet库可以帮助您做到这一点。

Answer 3

你问题的其余部分都被其他答案充分涵盖了，所以我不会重复它们。但是还没有人回答过你在编辑2中提出的问题。要回答这个问题，如果您正在进行计算，然后希望得到该计算的最小结果，则需要List.minBy。您想要List.minBy的一条线索是，当您发现自己正在执行一个map之后执行一个min操作(其他两个答案都是这样)：这是一个典型的迹象，表明您需要minBy，在一个操作中而不是在两个操作中这样做。

在使用List.minBy时，有一个值得注意的地方:它返回原始值，而不是计算结果。也就是说，如果您执行ints |> List.pairwise |> List.minBy (fun (a,b) -> abs (a - b))，那么List.minBy将返回的是一对项，而不是差异。它是这样写的，因为如果它给了你原来的值，但是你真的想要结果，你总是可以重新计算结果；但是如果它给了你结果，你真的想要原始值，你可能无法得到它。(1的差异是8与9之间的差异，还是4与5之间的差异？)

所以在你的情况下，你可以：

let allInt = [5; 8; 9]
let minPair =
    allInt
    |> List.pairwise
    |> List.minBy (fun (x,y) -> abs (x - y))
let a, b = minPair
let minDifference = abs (a - b)
printfn "The difference between %d and %d was %d" a b minDifference

List.minBy操作也存在于序列上，因此，如果您的列表足够大，需要避免创建一个中间的对列表，那么可以使用Seq.pairwise和Seq.minBy：

let allInt = [5; 8; 9]
let minPair =
    allInt
    |> Seq.pairwise
    |> Seq.minBy (fun (x,y) -> abs (x - y))
let a, b = minPair
let minDifference = abs (a - b)
printfn "The difference between %d and %d was %d" a b minDifference

编辑：是的，我看到你有一个100,000项的列表。所以你肯定想要这个的Seq版本。F# seq类型就是IEnumerable，所以如果您习惯了C#，那么将Seq函数看作LINQ表达式，您就会有正确的想法。

这里有一件事要注意:看到我是怎么做let a, b = minPair的吗？这叫做毁灭作业，它真的很有用。我也可以这样做：

let a, b =
    allInt
    |> Seq.pairwise
    |> Seq.minBy (fun (x,y) -> abs (x - y))

也会给我同样的结果。Seq.minBy返回一个由两个整数组成的元组，而let a, b = (tuple of two integers)表达式接受这个元组，将其与模式a, b匹配，从而指定a具有该元组的第一个项的值，并指定b具有该元组的第二个项的值。注意我是如何使用短语“将其与模式匹配”的:这与使用match表达式时完全相同。解释匹配表达式会使这个答案太长，所以如果您还没有读过，我只会给您提供一个很好的参考：

https://fsharpforfunandprofit.com/posts/match-expression/