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 converts the list to an array, calls Array.permute, then converts it back to a list.在此基础上，您可能可以确定需要做什么(提示:使用数组！)。

Answer 2

出于性能原因，是否应该避免使用List.permute？

这里唯一的性能问题是您自己的代码，特别是调用List.length。

除了使用数组之外，有没有更有效的方式/数据结构适合这种类型的工作，也就是元素的混洗？或者这仅仅是一个问题，对于这个问题，使用Array是正确的数据结构？

您假设数组不能在函数上使用，而实际上，它们可以通过不改变其元素来使用。考虑permute函数：

let permute f (xs: _ []) = Array.init xs.Length (fun i -> xs.[f i])

尽管它作用于一个数组并产生一个数组，但它没有改变任何东西，所以它使用一个数组作为纯函数数据结构。