5

我最近实现了一个Fisher-Yates shuffle，它使用 List.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 的实现不应该在幕后自动转换为 Array 吗？

2）除了使用数组之外，是否有更适合此类工作的功能性方式/数据结构，即元素的洗牌？或者这仅仅是一个问题，数组是正确的数据结构？

4

2 回答 2

7

List.permute 将 list 转换为数组，调用Array.permute，然后将其转换回 list。基于此，您可能会弄清楚您需要做什么（提示：使用数组！）。

于 2012-04-20T18:47:06.030 回答
2

出于性能原因，应该避免 List.permute 吗？

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

除了使用数组之外，是否有更适合此类工作的功能方式/数据结构，即元素的洗牌？或者这仅仅是一个问题，数组是正确的数据结构？

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

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

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

于 2012-04-22T10:39:08.080 回答