performance - F# list 优化

从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＃...来编写它。

编辑：我正在测试列表中包含10万个或更多项目的代码。

编辑2：我相信，如果我能解决差异并一心一意，它应该可以大大提高性能，但是我不知道该怎么做，知道吗？

提前致谢

最佳答案

List.Item的执行时间为O（n），可能是代码中的主要性能瓶颈。 differenceList的评估通过索引迭代sortedList的元素，这意味着性能约为O（（N-2）（2（N-2））），简化为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

#time指令使我可以测量F＃Interactive中的执行时间，运行此代码时获得的输出为：

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

关于performance - F# list 优化，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45494280/

SortedList

performance - F# list 优化