Производительность List.permute

Question

Недавно я внедрил 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 

I получить следующие результаты, которые, как правило, чтобы подтвердить свое предположение:

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) Помимо использования массива, существует ли более функциональная структура/структура данных, подходящая для этого типа работы, т. Е. Перетасовка элементов? Или это просто проблема, для которой массив используется для правильной структуры данных?

Answer 1

List.permuteconverts the list to an array, calls Array.permute, then converts it back to a list. Исходя из этого, вы, вероятно, можете выяснить, что вам нужно сделать (подсказка: работа с массивами!).

Answer 2

Следует ли избегать List.permute по соображениям эффективности?

Единственная проблема с производительностью здесь заключается в вашем собственном коде, в частности, при вызове List.length.

Помимо использования массива, существует ли более функциональная структура/структура данных, подходящая для такого типа работы, т. Е. Перетасовка элементов? Или это просто проблема, для которой массив используется для правильной структуры данных?

Вы предполагаете, что массивы не могут использоваться функционально, если на самом деле они могут не мутировать их элементы. Рассмотрим функцию permute:

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

Хотя он действует на массив и производит массив он ничего не мутирует так он использует массив в качестве чисто функциональной структуры данных.