List.permute的性能

Question

我最近实现了Fisher-Yates shuffle,它使用List.permute对列表进行洗牌,并注意到随着列表大小的增加,性能显着降低.我怀疑这是因为虽然算法假定它在数组上运行,但permute必须通过索引访问列表元素,即O(n).

为了确认这一点,我尝试将排列应用于列表以反转其元素,比较直接在列表上工作,并将列表转换为数组并返回到列表:

let permute i max = max - i - 1
let test = [ 0 .. 10000 ]

let rev1 list =
   let perm i = permute i (List.length list)
   List.permute perm list

let rev2 list =
   let array = List.toArray list
   let perm i = permute i (Array.length array)
   Array.permute perm array |> Array.toList 

我得到以下结果,这往往证实了我的假设:

rev1 test;;
Real: 00:00:00.283, CPU: 00:00:00.265, GC gen0: 0, gen1: 0, gen2: 0
rev2 test;;
Real: 00:00:00.003, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0

我的问题如下:

1)出于性能原因,应该避免使用List.permute吗？而且,相关地,List.permute的实现不应该在幕后自动转换为数组吗？

2)除了使用数组之外,是否有更适合这类工作的功能性方式/数据结构,即元素的混乱？或者这只是一个问题,Array是正确的数据结构使用？

Answer 1

List.permute 将列表转换为数组,调用Array.permute,然后将其转换回列表.基于此,您可以找出您需要做的事情(提示:使用数组!).