List.permute的性能 [英] Performance of List.permute

问题描述

我最近实施了 Fisher-Yates随机播放，使用List.permute对列表进行混洗，并注意到随着列表大小的增加，性能会显着下降.我怀疑这是由于以下事实:虽然算法假定它在数组上运行，但置换必须通过索引访问列表元素，即O(n).

I implemented a Fisher-Yates shuffle recently, which used List.permute to shuffle the list, and noted that as the size of the list increased, there was a significant performance decrease. I suspect this is due to the fact that while the algorithm assumes it is operating on an array, permute must be accessing the list elements by index, which is O(n).

为确认这一点，我尝试对列表应用排列以反转其元素，比较直接在列表上工作，然后将列表转换为数组然后返回列表:

To confirm this, I tried out applying a permutation to a list to reverse its element, comparing working directly on the list, and transforming the list into an array and back to a list:

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 

我得到以下结果，这些结果倾向于证实我的假设:

I get the following results, which tend to confirm my assumption:

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吗?

1) Should List.permute be avoided for performance reasons? And, relatedly, shouldn't the implementation of List.permute automatically do the transformation into an Array behind the scenes?

2)除了使用数组外，还有没有更实用的方法/数据结构适合这种类型的工作，即元素改组?还是这仅仅是数组是要使用的正确数据结构的问题?

2) Besides using an Array, is there a more functional way / data structure suitable for this type of work, i.e. shuffling of elements? Or is this simply a problem for which an Array is the right data structure to use?

推荐答案

List.permute

List.permute converts the list to an array, calls Array.permute, then converts it back to a list. Based on that, you can probably figure out what you need to do (hint: work with arrays!).

这篇关于List.permute的性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！