Performance of List.permute

Question

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

My question is the following:

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

Answer 1

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!).