performance - 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# 中以不同的方式编写它......还没有。

编辑:我正在测试列表中包含 100 000 个或更多项目的代码。

编辑 2:我相信，如果我能计算出差异并一次性获得最小值，它应该会大大提高性能，但我不知道该怎么做，好吗？

提前致谢

Answer 1

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