List.permuteのパフォーマンス

Question

私はリストをシャッフルするためにList.permuteを使った最近Fisher-Yates shuffleを実装しました。リストのサイズが大きくなるにつれ、パフォーマンスが大幅に低下しました。私はこれが、アルゴリズムが配列上で動作していると仮定している間、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の実装が自動的にシーンの背後にあるArrayへの変換を行うべきではありませんか？

2）配列を使用する以外に、このタイプの作業、つまり要素のシャッフルに適したより機能的な方法/データ構造がありますか？または、これは単にArrayが使用する正しいデータ構造体であるという問題ですか？

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となります。

アレイを使用する以外に、このタイプの作業、つまり要素のシャッフルに適したより機能的な方法/データ構造がありますか？または、これは単にArrayが使用する正しいデータ構造体であるという問題ですか？

実際には配列の要素を変更することなく配列を機能的に使用することはできません。 permute関数を考える：

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

それがアレイに作用すると、それは純粋に機能的なデータ構造としてアレイを使用しているので、それが何を変異されていないアレイを生成するが。