data-structures – List.permute的性能

我最近实现了一个 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是正确的数据结构使用？

List.permute converts the list to an array, calls Array.permute, then converts it back to a list.基于此,你可以弄清楚你需要做什么(提示：使用数组！).