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

编辑:我正在列表中测试此代码,包含10万个或更多项目.

编辑2:我相信如果我可以计算出差异并且一分为二,那么它应该会提高很多,但是我不知道如何做到这一点,一个想法？

提前致谢

Answer 1

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

另一种方法可能是将列表中的邻居配对,减去它们然后找到min.

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

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

这种方式更好,但是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 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